Студопедия — Задачи, связанные с поиском гамильтоновых циклов
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Задачи, связанные с поиском гамильтоновых циклов






В ряде отраслей промышленности возникает следующая задача планирования. Нужно произвести n продуктов, используя единственный тип аппаратуры. Аппарат должен быть перенастроен после того как был произведен продукт pi (но до того как начато производство продукта pj), в зависимости от комбинации (pi,pj). Стоимость перенастройки аппаратуры постоянна и не зависит от производимых продуктов. Предположим, что эти продукты производятся в непрерывном цикле, так что после производства последнего из n продуктов снова возобновляется в том же фиксированном цикле производство первого продукта.

Возникает вопрос о том, может ли быть найдена циклическая последовательность производства продуктов pi (i=1,2,…,n), не требующая перенастройки аппаратуры. Если представить эту задачу в виде ориентированного графа, то ответ на поставленный вопрос зависит от того, имеет ли этот ориентированный граф гамильтонов цикл или нет.

Если не существует циклической последовательности продуктов, не требующей перенастройки аппаратуры, то какова должна быть последовательность производства с наименьшими затратами на перенастройку, т.е. требующая наименьшего числа необходимых перенастроек?

Таким образом, мы рассмотрим следующие две задачи.

Задача 1. Дан ориентированный граф G, требуется найти в G гамильтонов цикл (или все циклы), если существует, хотя бы один такой цикл.

Задача 2. Дан полный ориентированный цикл G, дугам которого приписаны произвольные веса C=[cij], найти такой гамильтонов цикл, который имеет наименьший общий вес. Следует отметить, что если ориентированный граф G не полный, то его можно рассматривать как полный ориентированный граф, приписывая отсутствующим дугам бесконечный вес.

Алгоритмы решения задачи коммивояжера и ее вариантов имеют большое число практических приложений в различных областях человеческой деятельности. Рассмотрим, например, задачу в которой грузовик выезжает с центральной базы для доставки товаров данному числу потребителей и возвращается назад на базу. Стоимость перевозки пропорциональна пройденному грузовиком расстоянию, и при заданной матрице расстояний между потребителями маршрут с наименьшими транспортными затратами получается как решение соответствующей задачи коммивояжера. Аналогичные типы задач возникают при сборе почтовых отправлений из почтовых ящиков, составлении графика движения школьных автобусов по заданным остановкам и т.д. Задача очень легко обобщается и на тот случай, когда доставкой (сбором) занимаются несколько грузовиков, хотя эту задачу можно также переформулировать как задачу коммивояжера большей размерности. Другие приложения включают составление расписания выполнения операций на машинах, проектирование электрических сетей, управление автоматическими линиями и т.д.

Очевидно, что сформулированная выше задача (1) является частным случаем задачи (2). В самом деле, приписывая случайным образом дугам заданного ориентированного графа G конечные веса, получаем задачу коммивояжера. Если решение для этой задачи, т.е. кратчайший гамильтонов цикл, имеет конечное значение, то это решение является гамильтоновым циклом ориентированного графа G (т.е. ответом на задачу 1). Если же решение имеет бесконечное значение, то G не имеет гамильтонова цикла.

С другой стороны можно дать еще одну интерпретацию задачи 1). Рассмотрим снова полный ориетированный граф G1с общей матрицей весов дуг [cij] и рассмотрим задачу нахождения такого гамильтонова цикла, в котором самая длинная дуга минимальна. Эту задачу можно назвать минимаксной задачей коммивояжера. Тогда классическую задачу коммивояжера в той же терминологии можно было бы назвать минисуммной задачей коммивояжера. Покажем теперь, что задача (1) действительно эквивалентна минимаксной задаче коммивояжера.

В вышеупомянутом полном ориентированном графе G1 мы можем наверняка найти гамильтонов цикл. Пусть это будет цикл Ф1, и пусть вес самой длинной его дуги равен ĉ1. Удалив из G1 любую дугу, вес которой не меньше ĉ1, получим ориентированный граф G2. Найдем в ориентированном графе G2 гамильтонов цикл Ф2, и пусть вес его самой длинной дуги равен ĉ2. Удалим из G2 любую дугу, вес которой не меньше ĉ2, и так будем продолжать до тех пор, пока не получим ориентированный граф Gm+1, не содержащий никакого гамильтонова цикла. Гамильтонов цикл Фm в Gm (с весом ĉm) является тогда по определению решением минимаксной задачи коммивояжера, так как из отсутствия гамильтонова цикла в Gm+1 следует, что в G1 не существует никакого гамильтонова цикла, не использующего по крайней мере одну дугу с весом, большим или равным ĉm.

Таким образом, алгоритм нахождения гамильтонова цикла в ориентированном графе решает также минимаксную задачу коммивояжера. Наоборот, если мы располагаем алгоритмом решения последней задачи, то гамильтонов цикл в произвольном ориентированном графе G может быть найден с помощью построения полного ориентированного графа G1 с тем же самым множеством вершин, что и в G, дугам которого, соответствующим дугам из G, приписаны единичные веса, а остальным дугам — бесконечные веса. Если решение минимаксной задачи коммивояжера для G1 имеет конечный вес (на самом деле равный единице), то в графе G может быть найден соответствующий гамильтонов цикл. Если же решение имеет бесконечный вес, то в графе G не существует никакого гамильтонова цикла. Следовательно, две указанные задачи можно рассматривать как эквивалентные, поскольку было продемонстрировано, что алгоритм нахождения гамильтонова цикла позволяет решать минимаксную задачу коммивояжера и наоборот.

Ввиду того, что обе сформулированные выше задачи (1) и (2) часто встречаются в практических ситуациях и (как мы увидим позже) задачу (1) саму по себе решить намного проще, чем как подзадачу задачи (2), мы обе эти задачи рассмотрим по отдельности.

 







Дата добавления: 2015-10-01; просмотров: 732. Нарушение авторских прав; Мы поможем в написании вашей работы!



Картограммы и картодиаграммы Картограммы и картодиаграммы применяются для изображения географической характеристики изучаемых явлений...

Практические расчеты на срез и смятие При изучении темы обратите внимание на основные расчетные предпосылки и условности расчета...

Функция спроса населения на данный товар Функция спроса населения на данный товар: Qd=7-Р. Функция предложения: Qs= -5+2Р,где...

Аальтернативная стоимость. Кривая производственных возможностей В экономике Буридании есть 100 ед. труда с производительностью 4 м ткани или 2 кг мяса...

Правила наложения мягкой бинтовой повязки 1. Во время наложения повязки больному (раненому) следует придать удобное положение: он должен удобно сидеть или лежать...

ТЕХНИКА ПОСЕВА, МЕТОДЫ ВЫДЕЛЕНИЯ ЧИСТЫХ КУЛЬТУР И КУЛЬТУРАЛЬНЫЕ СВОЙСТВА МИКРООРГАНИЗМОВ. ОПРЕДЕЛЕНИЕ КОЛИЧЕСТВА БАКТЕРИЙ Цель занятия. Освоить технику посева микроорганизмов на плотные и жидкие питательные среды и методы выделения чис­тых бактериальных культур. Ознакомить студентов с основными культуральными характеристиками микроорганизмов и методами определения...

САНИТАРНО-МИКРОБИОЛОГИЧЕСКОЕ ИССЛЕДОВАНИЕ ВОДЫ, ВОЗДУХА И ПОЧВЫ Цель занятия.Ознакомить студентов с основными методами и показателями...

Сосудистый шов (ручной Карреля, механический шов). Операции при ранениях крупных сосудов 1912 г., Каррель – впервые предложил методику сосудистого шва. Сосудистый шов применяется для восстановления магистрального кровотока при лечении...

Трамадол (Маброн, Плазадол, Трамал, Трамалин) Групповая принадлежность · Наркотический анальгетик со смешанным механизмом действия, агонист опиоидных рецепторов...

Мелоксикам (Мовалис) Групповая принадлежность · Нестероидное противовоспалительное средство, преимущественно селективный обратимый ингибитор циклооксигеназы (ЦОГ-2)...

Studopedia.info - Студопедия - 2014-2024 год . (0.009 сек.) русская версия | украинская версия