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

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

Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по одному разу в неизвестном порядке города 2,3,4..n и вернуться в первый город. Расстояния между городами известны. В каком порядке следует обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?

Методы решения:

1.     Жадный алгоритм

Жадный алгоритм – алгоритм нахождения наикратчайшего расстояния путём выбора самого короткого, ещё не выбранного ребра, при условии, что оно не образует цикла с уже выбранными рёбрами. «Жадным» этот алгоритм назван потому, что на последних шагах приходится жестоко расплачиваться за жадность.

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

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

3.     Метод ветвей и границ

Метод, известный как метод ветвей и границ, похож на методы с отходами назад тем, что он исследует древовидную модель пространства решений и применим для широкого круга дискретных комбинаторных задач. Алгоритмы с отходами назад нацелены на то, чтобы найти одну или все конфигурации, моделируемые N-векторами, которые удовлетворяют определенным свойствам. В решаемой задаче определена числовая функция стоимости для каждой из вершин, появляющихся в дереве поиска. Цель - найти конфигурацию, на которой функция стоимости достигает максимального или минимального значения.

Задача: Задача о деревенском почтальоне

Почта расположена в деревне 1. Почтальон, выйдя из этой деревни, должен разнести корреспонденцию жителям деревней 2, 3, 4 и вернуться обратно. Под стоимостью ребра будем понимать количество километров, которые почтальон вынужден пройти пешком. Из всех замкнутых маршрутов надо выбрать такой, в котором пройденное пешком расстояние минимально.

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

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

Находим минимальное значение в каждой строке (di) и выписываем его в отдельный столбец.

Производим редукцию строк – из каждого элемента в строке вычитаем соответствующее значение найденного минимума (di).

В итоге в каждой строке будет хотя бы одна нулевая клетка.

Далее находим минимальные значения в каждом столбце (dj). Эти минимумы выписываем в отдельную строку.

Вычитаем из каждого элемента матрицы соответствующее ему dj.

В итоге в каждом столбце будет хотя бы одна нулевая клетка.

Для каждой нулевой клетки получившейся преобразованной матрицы находим «оценку». Ею будет сумма минимального элемента по строке и минимального элемента по столбцу, в которых размещена данная нулевая клетка. Сама она при этом не учитывается. Найденные ранее di и dj не учитываются. Полученную оценку записываем рядом с нулем, в скобках.

И так по всем нулевым клеткам:

Редукция матрицы

Выбираем нулевую клетку с наибольшей оценкой. Заменяем ее на «М». Мы нашли один из отрезков пути. Выписываем его (от какой деревни к какой движемся, в нашем примере от 4-й ко 2-й).

Ту строку и тот столбец, где образовалось две «М» полностью вычеркиваем. В клетку соответствующую обратному пути ставим еще одну букву «М» (т.к. мы уже не будем возвращаться обратно).

Если полный путь еще не найден, переходим к пункту 2, если найден к пункту 9.

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

Если все отрезки пути найдены (или найдены еще не все отрезков, но оставшаяся часть пути очевидна) – переходим к пункту 9.

Вычисление итоговой длины пути и построение маршрута:

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

В нашем примере маршрут получился следующий: 4 → 2 → 3 → 1 → 4.

Общая длина пути: L = 30.

Задача для самостоятельной работы:

Краткое описание документа:

Материал к уроку содержит готовое руководство по решению Задачи коммивояжера с подробным описанием этапов решения.Материал можно предложить в качестве самостоятельного изучения после объяснения типа такого рода задач и их использования.

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