Полный перебор перестановок

Метод полного перебора заключается в том, что выполняется перебор всех возможных комбинаций точек (пунктов назначения). Как известно из математики, число таких перестановок равно n!, где n – количество точек. Так как в задаче коммивояжера исходный пункт обычно принимается одним и тем же (первая точка), то нам достаточно перебрать оставшиеся, т.е. количество перестановок будет равно (n–1)!. Этот алгоритм почти всегда дает точное решение задачи коммивояжера, однако продолжительность таких вычислений может занять непозволительно много времени. Известно, что при значениях n > 12, современный компьютер не смог бы решить задачу коммивояжера даже за все время существования вселенной.
А теперь рассмотрим пример (см. рис.3). На рис. 3а показан граф с шестью вершинами (их часто называют "городами"), который может служить основой для задачи коммивояжера. Заданы координаты каждой вершины, а весом каждого ребра считается его длина. Мы предполагаем (и такое предположение характерно для задачи коммивояжера), что существуют все ребра графа, т.е. граф является полным. В более общих случаях, когда вес ребер не основывается на евклидовом расстоянии, у ребра может оказаться бесконечный вес, чего в действительности, конечно, не бывает.
На рис. 3 b,c,d,e показаны четыре маршрута по шести "городам". Протяженности этих четырех маршрутов равняются 50.00, 49.73, 48.39 и 49.78 соответственно. Маршрут на рис. 3d является кратчайшим из всех возможных маршрутов. Результат, показанный на рис. 3b, можно получить с помощью жадного алгоритма. Как видим, от кратчайшего маршрута этот результат отличается всего на 3,22%. Такая погрешность вполне допустима, если скорость выполнения алгоритма имеет значение (а при решении сложных задач так всегда и бывает). В данном примере можно было бы применить и полный перебор – современный компьютер справился бы довольно быстро.
Как уже упоминалось, существуют и другие алгоритмы для решения задачи коммивояжера, которые значительно точнее жадного алгоритма и значительно быстрее метода полного перебора. Однако дисциплина называется «Программирование и основы алгоритмизации», из чего следует, что на первом месте у нас все-таки программирование, а уж потом можно и с алгоритмами разбираться. Поэтому в данной курсовой работе другие алгоритмы не рассматриваются в виду относительной сложности. Да и пора бы нам уже написать какую-нибудь программу…

Полный перебор

Метод полного перебора (иногда говорят Метод перебора, подразумевая при этом полный перебор - это не совсем правильно, так как перебор может быть и не полным) заключается в том, что выполняется перебор всех возможных комбинаций точек (пунктов назначения). Как известно из математики, число таких перестановок равно n!, где n – количество точек. Так как в задаче коммивояжера исходный пункт обычно принимается одним и тем же (первая точка), то нам достаточно перебрать оставшиеся, т.е. количество перестановок будет равно (n–1)!. Этот алгоритм почти всегда дает точное решение задачи коммивояжера, однако продолжительность таких вычислений может занять непозволительно много времени. Известно, что при значениях n > 12, современный компьютер не смог бы решить задачу коммивояжера даже за все время существования вселенной.

Как уже упоминалось, существуют и другие алгоритмы для решения задачи коммивояжера, которые значительно точнее жадного алгоритма и значительно быстрее метода полного перебора. Однако дисциплина называется «Программирование и основы алгоритмизации», из чего следует, что на первом месте у нас все-таки программирование, а уж потом можно и с алгоритмами разбираться. Поэтому в данной курсовой работе другие алгоритмы не рассматриваются в виду относительной сложности. Да и пора бы нам уже написать какую-нибудь программу в любимой нами Delphi.

Метод полного перебора

Перестановочные приемы обеспечивают эффективный поиск оптимального решения задачи 2-х машин, т.к. вычислительная сложность реализующих их алгоритмов полиномиально зависит от об'ема партии работ. Однако, правило Джонсона, которое лежит в основе перестановочных приемов, устанавливает только достаточное условие получения оптимального расписания, которое не является необходимым. Поэтому, в общем случае, класс оптимальных расписаний для задачи 2-х машин может включать достаточно большое число расписаний, которые не удовлетворяют правилу Джонсона и, следовательно, недостижимы с помощью перестановочных приемов. Воэможность перечисления всех расписаний в классе оптимальных обеспечивает полный перебор всех n! перестановок работ партии.Существуют различные способы организации полного перебора перестановок: лексиграфическое упорядочивание, циклический сдвиг, транспозиция смежных элементов. Для задачи 2-х машин удобно использовать вариант полного перебора, который порождает перестановки циклическим сдвигом, известный также как алгоритм вращения. Естественный способ перечисления перестановок циклическим сдвигом состоит в том, что начав с некоторой произвольной перестановки, последовательно сдвигать по циклу на одно место влево все n работ партии. При каждом сдвиге 1-я работа текущей перестановки перемещается на последнее место без изменения взаимного расположения остальных, образуя новую перестановку. Такая организация циклического сдвига называется вращением. Вращение всех работ нужно продолжать, пока оно порождает новые перестановки, не встречавшиеся ранее. Перестановка считается оригинальной, когда после сдвига позиция последнего вращаемой части не равна его позиции в исходной перестановке. Если в результате очередного вращения получается ранее порожденная перестановка, нужно исследовать возможность построить оригинальную перестановку, применяя процедуру локального вращения последовательно для k = n-1, n-2,..., 2 начальных работ при фиксированном положении остальных n - k хвостовых работ партии. Если локальное вращение первых 1 < k < n работ порождает оригинальнуюперестановку, следует продолжить вращение циклическим сдвигом всех n работ партии. В противном случае (k = 1), перебор считается завершенным, т.к. перечислены все n! перестановок. Для каждой оригинальной перестановки, порождаемой рассмотренным алгоритмом вращения, определяется продолжительность соответствующего расписания процесса обслуживания. Сравнительная оценка длительности позволяет отобрать в качестве оптимальных все перестановки с минимальной продолжительность процесса обслуживания. Следует отметить, что полный перебор всех оптимальных решений задачи 2-х машин не может быть практически реализован для достаточно представительных партий работ по ресурсным соображениям, всвязи с тем, что мощность перебора возрастает неполиномиально при увеличении об'ема партии и быстро превосходит возможности современных вычислительных систем.