Анализ методов решения задачи

Стр 1 из 3Следующая ⇒

Метод прямого перебора для задачи коммивояжера с n городами основан на генерации n перестановок, определении на каждой перестановке суммарной длины пути и выборе в качестве оптимальной - перестановки с минимальной длиной пути. Для генерации перестановок целесообразно использовать алгоритм реупорядочения перестановочного хвоста (алгоритм – 1) /9/. К положительным сторонам этого метода следует отнести его простоту, обозримость, а также принципиальную возможность получения на гипотетической ЭВМ решение для задачи любой размерности. Основным недостатком рассматриваемого метода является стремительное возрастание количества перестановок при возрастании n. Так, при n = 10, количество перестановок равно 8628800. Этот недостаток существенно ограничивает использование данного метода для решения практических задач на реальных ЭВМ.

Существенно уменьшить количество вариантов при определенных исходных данных позволяет алгоритм Литтла, являющийся развитием метода ветвей и границ применительно к задаче коммивояжера /1/. Сущность метода состоит в том, что множество всех планов разбивается на два подмножества, первое из которых, содержит планы с непосредственным переходом из n - го города в l - й, а второе подмножество содержит планы с переходом из n-го города в l - й через промежуточные города. Для каждого подмножества вводится нижняя оценка и в качестве перспективного выбирается подмножество с минимальной оценкой. Перспективное подмножество аналогично разбивается на два подмножества, и для выбора нового перспективного подмножества сравниваются нижние оценки вновь сконструированных подмножеств с нижней оценкой подмножества, отброшенного на первом этапе. Процесс ветвления продолжается до тех пор, пока не будет получена совокупность перспективных пар, образующих замкнутый цикл длиной n. Основной недостаток данного метода – зависимость количества выполняемых операций не только от размерности матрицы расстояний, но и от значений элементов этой матрицы. Следует отметить, что при некоторых значениях элементов матрицы расстояний метод ветвей и границ по количеству операций совпадает с методом прямого перебора. Кроме того, при машинной реализации этого метода необходимо хранить преобразованные матрицы расстояний для всех конкурирующих подмножеств, что значительно повышает требования к объему памяти ЭВМ. В то же время на современном этапе развития теории дискретного программирования метод ветвей и границ является наиболее приемлемым для точного решения задачи коммивояжера при небольших значениях n. Подробное описание этого метода приведено в /1/.

Описание метода ветвей и границ

Решение задачи предварительный этап и итерации.

Предварительный этап.

На предварительном этапе происходит переход от матрицы С к матрице С₀ – характеризующуюся тем что в каждой строке и в каждом столбце существует нулевое значение, эти элементы являются претендентами включения в оптимальный маршрут, для получения матрицы С₀ выполняют следующие шаги:

Шаг 1. В каждой i-й строке матрицы С находят минимальный элемент h_i= min c_ij и

образуют ||c’_ij||, у которой c’_ij= c_ij - h_i, таким образом, в каждой строке присутствует хотя бы один нулевой элемент.

Шаг 2. В матрице C' для каждого столбца находят минимальный элемент, и происходит переход к матрице ||C₀|| => c_ij=c’_ij-h_j. Константы h_i, h_j называют константами приведения.

Шаг 3. Вычисляется сумма констант приведения Hо = . Процесс перехода от матрицы С к матрице C₀ называют процессом приведения.

Этап 1.

На этом этапе формируется исходное множество Gо и находиться матрица Со, нижняя оценка x (Gо) и два подмножества Р и .

Шаг 1. Исходное множество Gо или множество решений задачи коммивояжера представляет собой множества всех возможных решений, перестановок из n чисел. Общее количество таких перестановок равно n!. В качестве характеристики используют матрицу C₀, которая была получена на предварительном этапе при реализации процедуры приведения.

Шаг 2. Вычисляется нижняя оценка исходное множество Gо. Она равна сумме

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

Шаг 3. Исходное множество G₀ делится на два непересекающихся подмножества G и G (рис.1.). Подмножество G содержит все маршруты с переходом из r-го города в m-й, а подмножества G - все остальные переходы. Пара (r, m) называется перспективной.

(r, m) (r, m)

рис. 1. Деление исходного множества

Концепция выбора перспективной пары:

Шаг 1. Длина непосредственного перехода между городами, входящими в перспективную пару, должна быть минимальной, т.е. элемент с`о (r, m) = 0;

Шаг 2. Длина опосредованного пути стремится к максимуму. Опосредованный путь между r и m – путь проходящий из r в m через другие города.

Этап 2.

На втором этапе определяется характеристики подмножества G₂, а именно матрица С , и нижняя оценка подмножества G ,

Шаг 1. Подмножество G содержит все перестановки, в которых отсутствует переход (r, m) очевидно, что матрица C должна отображать это свойство подмножества. C - получается путем преобразования C₀, для этого элемент с координатами r, m приравнивают к бесконечности.

К этой матрице применяется процедура приведения, и значение суммы приводящих констант равно Н . В результате получается матрица С .

Шаг 2. Определяется нижняя оценка множества G , x( G ) = x(Go) + H = x(Go) + Q(r, m).

Этап 3.

Определение характеристики множества G , матрица C и нижняя оценка.

Шаг 1. Для получения матрицы С необходимо:

1) В матрице Со вычеркнуть r-ю строку и m-й столбец. Вычеркивание r-й строки означает, что коммивояжер больше не должен выезжать из r-го города не в какой другой город, а вычеркивание m-го столбца указывает на то, что коммивояжер не должен выезжать в m-й город не из какого другого города;

2) Необходимо элемент с координатами (m, r) приравнять к бесконечности для исключения образования локальных циклов типа (r, m, r). В дальнейшем такие замкнутые подциклы называются короткими.

В результате этих преобразований получаем матрицу в результате преобразований получается матрица C =||c (i, j) ||, для получения окончательной матрицы необходимо выполнить процедуру приведения.

Шаг 2. Вычисляется нижняя оценка множества G , ξ (G )= ξ (G₀) + H .

Этап 4.

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