Т.е. 2fB>fA, т.е. fA/fB>1+; =1.

Теорема доказана.

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

Известно еще несколько простых алгоритмов, гарантирующих в худшем случае =1. Для того, чтобы найти среди них алгоритм поточнее, зайдем с другого конца и для начала опишем “brute-force enumeration” - “перебор животной силой”, как его называют в англоязычной литературе. Понятно, что полный перебор практически применим только в задачах малого размера. Напомним, что ЗК с n городами требует при полном переборе рассмотрения (n-1)!/2 туров в симметричной задаче и (n-1)! Туров в несимметричной, а факториал, как показано в следующей таблице, растет удручающе быстро:

Чтобы проводить полный перебор в ЗК, нужно научиться (разумеется, без повторений) генерировать все перестановки заданного числа m элементов. Это можно сделать несколькими способами, но самый распространенный (т.е. приложимый для переборных алгоритмов решения других задач) - это перебор в лексикографическом порядке.

Пусть имеется некоторый алфавит и наборы символов алфавита (букв), называемые словами. Буквы в алфавите упорядочены: например, в русском алфавите порядок букв абя (символ читается “предшествует)”. Если задан порядок букв, можно упорядочить и слова. Скажем, дано слово u=(u1,u2,..,um) - состоящее из букв u1,u2,..,um - и слово v =(v1,v2,..,vb). Тогда если u1v1, то и uv, если же u1=v1, то сравнивают вторые буквы и т.д. Этот порядок слов и называется лексикографическим. Поэтому в русских словарях (лексиконах) слово “абажур” стоит раньше слова “абака”. Слово “бур” стоит раньше слова “бура”, потому что пробел считается предшествующим любой букве алфавита.

Рассмотрим, скажем, перестановки из пяти элементов, обозначенных цифрами 1..5. Лексикографически первой перестановкой является 1-2-3-4-5, второй - 1-2-3-5-4, …, последней - 5-4-3-2-1. Нужно осознать общий алгоритм преобразования любой перестановки в непосредственно следующую.

Правило такое: скажем, дана перестановка 1-3-5-4-2. Нужно двигаться по перестановке справа налево, пока впервые не увидим число, меньшее, чем предыдущее (в примере это 3 после 5). Это число, Pi-1 надо увеличить, поставив вместо него какое-то число из расположенных правее, от Pi до Pn. Число большее, чем Pi-1, несомненно, найдется, так как Pi-1< Pi . Если есть несколько больших чисел, то, очевидно, надо ставить меньшее из них. Пусть это будет Pj,j>i-1. Затем число Pi-1 и все числа от Pi до Pn, не считая Pj нужно упорядочить по возрастанию. В результате получится непосредственно следующая перестановка, в примере - 1-4-2-3-5. Потом получится 1-4-2-5-3 (тот же алгоритм, но упрощенный случай) и т.д.

Нужно понимать, что в ЗК с n городами не нужны все перестановки из n элементов. Потому что перестановки, скажем, 1-3-5-4-2 и 3-5-4-2-1 (последний элемент соединен с первым) задают один и тот же тур, считанный сперва с города 1, а потом с города 3. Поэтому нужно зафиксировать начальный город 1 и присоединять к нему все перестановки из остальных элементов. Этот перебор даст (n-1)! разных туров, т.е. полный перебор в несимметричной ЗК (мы по-прежнему будем различать туры 1-3-5-4-2 и 1-2-4-5-3).

Данный алгоритм описан на языке Паскаль (см. Приложения).

Пример 2. Решим ЗК, поставленную в Примере 1 лексикографическим перебором. Приведенная выше программа напечатает города, составляющие лучший тур: 1-2-6-5-4-3 и его длину 36.

Желательно усовершенствовать перебор, применив разум. В следующем пункте описан алгоритм, который реализует простую, но широко применимую и очень полезную идею.

Алгоритм Дейкстры

Одним из вариантов решения ЗК является вариант нахождения кратчайшей цепи, содержащей все города. Затем полученная цепь дополняется начальным городом - получается искомый тур.

Можно предложить много процедур решения этой задачи, например, физическое моделирование. На плоской доске рисуется карта местности, в города, лежащие на развилке дорог, вбиваются гвозди, на каждый гвоздь надевается кольцо, дороги укладываются верёвками, которые привязываются к соответствующим кольцам. Чтобы найти кратчайшее расстояние между i и k, нужно взять I в одну руку и k в другую и растянуть. Те верёвки, которые натянутся и не дадут разводить руки шире и образуют кратчайший путь между i и k. Однако математическая процедура, которая промоделирует эту физическую, выглядит очень сложно. Известны алгоритмы попроще. Один из них - алгоритм Дейкстры, предложенный Дейкстрой ещё в 1959г. Этот алгоритм решает общую задачу:

В ориентированной, неориентированной или смешанной (т. е. такой, где часть дорог имеет одностороннее движение) сети найти кратчайший путь между двумя заданными вершинами.

Алгоритм использует три массива из n (= числу вершин сети) чисел каждый. Первый массив a содержит метки с двумя значениями: 0 (вершина ещё не рассмотрена) и 1 (вершина уже рассмотрена); второй массив b содержит расстояния - текущие кратчайшие расстояния от vi до соответствующей вершины; третий массив c содержит номера вершин - k-й элемент ck есть номер предпоследней вершины на текущем кратчайшем пути из vi в vk. Матрица расстояний Dik задаёт длины дуг dik; если такой дуги нет, то dik присваивается большое число Б, равное “машинной бесконечности”.

Теперь можно описать:

Алгоритм Дейкстры

1. Инициализация.

В цикле от одного до n заполнить нулями массив а; заполнить числом i массив с: перенести i-тую строку матрицы D в массив b;

a[i]:=1; c[i]:=0; {i-номер стартовой вершины}

2. Общий шаг.

Найти минимум среди неотмеченных (т. е. тех k, для которых a[k]=0); пусть минимум достигается на индексе j, т. е. bjbk; a[j]:=1;

если bk>bj+djk то (bk:=bj+djk; ck:=j) {Условие означает, что путь vi..vk длиннее, чем путь vi..vj,vk . Если все a[k] отмечены, то длина пути vi..vk равна b[k]. Теперь надо перечислить вершины, входящие в кратчайший путь}

3. Выдача ответа.

{Путь vi..vk выдаётся в обратном порядке следующей процедурой:}

3.1. z:=c[k];

3.2. Выдать z;

3.3. z:=c[z]; Если z = 0, то конец, иначе перейти к 3.2.

Для выполнения алгоритма нужно n раз просмотреть массив b из n элементов, т. е. алгоритм Дейкстры имеет квадратичную сложность.

Таким образом, для решения ЗК нужно n раз применить алгоритм Дейкстры следующим образом.

Возьмём произвольную пару вершин

j,k. Исключим непосредственное ребро C[j,k]. С помощью алгоритма Дейкстры найдём кратчайшее расстояние между городами j..k. Пусть это расстояние включает некоторый город m. Имеем часть тура j,m,k. Теперь для каждой пары соседних городов (в данном примере - для j,m и m,k) удалим соответственное ребро и найдём кратчайшее расстояние. При этом в кратчайшее расстояние не должен входить уже использованный город.

Далее аналогично находим кратчайшее расстояние между парами вершин алгоритмом Дейкстры, до тех пор, пока все вершины не будут задействованы. Соединим последнюю вершину с первой и получим тур. Чаще всего это последнее ребро оказывается очень большим, и тур получается с погрешностью, однако алгоритм Дейкстры можно отнести к приближённым алгоритмам.

Практическое применение задачи коммивояжера

Кроме очевидного применения ЗК на практике, существует ещё ряд задач, сводимых к решению ЗК.

Задача о производстве красок. Имеется производственная линия для производства n красок разного цвета; обозначим эти краски номерами 1,2… n. Всю производственную линию будем считать одним процессором.. Будем считать также, что единовременно процессор производит только одну краску, поэтому краски нужно производить в некотором порядке Поскольку производство циклическое, то краски надо производить в циклическом порядке =(j1,j2,..,jn,j1). После окончания производства краски i и перед началом производства краски j надо отмыть оборудование от краски i. Для этого требуется время C[i,j]. Очевидно, что C[i,j] зависит как от i, так и от j, и что, вообще говоря,C[i,j]?C[j,i]. При некотором выбранном порядке придется на цикл производства красок потратить время

Где tk - чистое время производства k-ой краски (не считая переналадок). Однако вторая сумма в правой части постоянна, поэтому полное время на цикл производства минимизируется вместе с общим временем на переналадку.

Таким образом, ЗК и задача о минимизации времени переналадки - это просто одна задача, только варианты ее описаны разными словами.

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

Операция пробивки j-того отверстия характеризуется четверкой чисел (xj,yj,zj,tj),, где xj,yj- координаты нужного положения стола, zj - координата нужного положения диска и tj - время пробивки j-того отверстия.

Производство панелей носит циклический характер: в начале и конце обработки каждого листа стол должен находиться в положениях (x0, y0) диск в положении z0 причем в этом положении отверстие не пробивается. Это начальное состояние системы можно считать пробивкой фиктивного нулевого отверстия. С параметрами (x0,y0,z0,0).

Чтобы пробить j-тое отверстие непосредственно после i-того необходимо произвести следующие действия:

1. Переместить стол по оси x из положения xi в положение xj, затрачивая при этом время t(x)(|xi-xj|)=ti,j(x)

1. Проделать то же самое по оси y, затратив время ti,j(y)

2. Повернуть головку по кратчайшей из двух дуг из положения zi в положение zj, затратив время ti,j(z) .

3. Пробить j-тое отверстие, затратив время tj.

Конкретный вид функций t(x), t(y), t(z) зависит от механических свойств пресса и достаточно громоздок. Явно выписывать эти функции нет необходимости

Действия 1-3 (переналадка с i-того отверстия j-тое) происходит одновременно, и пробивка происходит немедленно после завершения самого длительного из этих действий. Поэтому

С[i,j] = max(t(x), t(y), t(z))

Теперь, как и в предыдущем случае, задача составления оптимальной программы для дыропробивного пресса сводится к ЗК (здесь - симметричной).

3 АЛГОРИТМ МЕТОДА ВЕТВЕЙ И ГРАНИЦ

Запишем алгоритм:

1. Положим k == 1.

2. Осуществим приведение матрицы С по строкам и столбцам образуя приведенную матрицу Сk.

3. Вычислим сумму приводящих констант h(k)--это оценка для множества X, обозначим ее .

4. Выберем претендентов для включении и множество Y, т. е. все те (i,j), i=1. 2, ..., j==1, 2, ..., , для которых .

5. Для выделенных претендентов на включение в Y подсчитаем:

.

6. Выберем по всем i,j, у которых . Пара (k,l) включается в множество Y и является запретной для множества .

7. Подсчитаем оценку для множества Y, она равна ранее произведенным затратам для множества Х и , т. е.

.

8. Так как из каждого города можно выезжать только один раз, то естественно k-ю строку из дальнейшего рассмотрения исключить Так как в каждый город можно въезжать только один раз, то l-й столбец исключается.

Чтобы избежать образования замкнутых подциклов, естественно запретить переезд из l в k, т. е. клетку (l,k).

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

Итак, момент образования матрицы 2х2 является особым, поэтому в п.9 проверяем, имеет ли полученная усеченная матрица размерность 2х2. Если «да», то переходим к п. 11. Если «нет», то к п. 10.

10. Является ли полученная матрица приведенной? Если «да», то оценка для множества Y равна оценке того множества, из которого Y получено, т. е. . Если «нет», то осуществляется приведение только что полученной матрицы и подсчитывается , после чего

,

и переходим к п. 4.

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

Блок-схема метода приведена на рисунке 3. Некоторые замечания: блок «матрица 2х2» определяет момент получения замыкающих пар городов для образования замкнутого маршрута; к блоку «восстановление» осуществляется переход и том случае, когда перспективным для дальнейшего ветвления оказалось множество, принадлежащее к совокупности. В этом случае процесс выбора претендентов для дальнейшего ветвления требует восстановления исходной матрицы С. подсчета затрат q, необходимых для выполнение ранее построенного маршрута для множества Х, из которого построено, т. е.

.

После этого необходимо вычеркнуть строки и столбцы для пар, входящих в Х (аналогично п. 8), и привести полученную матрицу для выбора претендентов для ветвления.

4 РЕШЕНИЕ ПОСТАВЛЕННОЙ ЗАДАЧИ

4.1 Условие задачи

Задача

Определить оптимальную последовательность запуска деталей в производство, если задана матрица затрат на переналадку оборудования:

Сделать анализ решенной задачи.

ВЫВОДЫ

В результате выполненной работы были изичуны эврестический, приближенный и точный алгоритмы решения задач коммивояжера. Точные алгоритмы решения задач коммивояжера - это полный перебор или усовершенствованный перебор. Оба они, особенно первый, не эффективны при большом числе вершин графа.

Для малого числа вершин наиболее эффективный точный метод лексического перебора, для большого числа вершин рациональнее применять метод ветвей и границ. Изучены практические применения задач коммиявожера и задачи n станков.

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

Также прилагается программана решающая задачу о коммивояжере методом ветвей и границ. Для разработки данной программы была использованя среда разработки Delphi версии 6.0.

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

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

ЛИТЕРАТУРА:

1 Балашевич В.А., Алгоритмизация математических методов планирования и управления. - Минск: Вышэйшая школа,1979.-286с

2 Дегтярев Ю.И., Исследование операций.- Москва: Высшая школа,1986.-270с.

3 Ляшенко И.Н. Линейное и нелинейное программирование - Киев: Вища школа,1975.-370с.

ПРИЛОЖЕНИЕ А

(обязательное)

Текст программы

Схема программы

Описание программы

Инструкция пользователю

ПРИЛОЖЕНИЕ Б

(обязательное)

Входная информация

ПРИЛОЖЕНИЕ В

(обязательное)

Выходная информация

Страницы: 1, 2, 3, 4