Курсовая работа: Задача коммивояжера

Оценивая нули в матрице на табл. 10, получаем ветвление по выбору ребра (2,6), отрицательный вариант получает оценку 36+3=39, а для получения оценки положительного варианта вычеркиваем вторую строку и шестой столбец, получая матрицу на табл. 11.

В матрицу надо добавить запрет в клетку (5,3), ибо уже построен фрагмент тура [3,1,2,6,5] и надо запретить преждевременный возврат (5,3). Теперь, когда осталась матрица 2х2 с запретами по диагонали, достраиваем тур ребрами (4,3) и (5,4). Мы не зря ветвились, по положительным вариантам. Сейчас получен тур: 1→2→6→5→4→3→1 стоимостью в 36. При достижении низа по дереву перебора класс туров сузился до одного тура, а оценка снизу превратилась в точную стоимость.

Итак, все классы, имеющие оценку 36 и выше, лучшего тура не содержат. Поэтому соответствующие вершины вычеркиваются. Вычеркиваются также вершины, оба потомка которой вычеркнуты. Мы колоссально сократили полный перебор. Осталось проверить, не содержит ли лучшего тура класс, соответствующий матрице С[Not(1,2)], т.е. приведенной матрице С с запретом в клетке 1,2, приведенной на 1 по столбцу (что дало оценку 34+1=35). Оценка нулей дает 3 для нуля в клетке (1,3), так что оценка отрицательного варианта 35+3 превосходит стоимость уже полученного тура 36 и отрицательный вариант отсекается.

 Для получения оценки положительного варианта исключаем из матрицы первую строку и третий столбец, ставим запрет (3,1) и получаем матрицу. Эта матрица приводится по четвертой строке на 1, оценка класса достигает 36 и кружок зачеркивается. Поскольку у вершины «все» убиты оба потомка, она убивается тоже. Вершин не осталось, перебор окончен. Мы получили тот же минимальный тур, который показан подчеркиванием на табл. 2.

Удовлетворительных теоретических оценок быстродействия алгоритма Литтла и родственных алгоритмов нет, но практика показывает, что на современных ЭВМ они часто позволяют решить ЗК с n = 100. Это огромный прогресс по сравнению с полным перебором. Кроме того, алгоритмы типа ветвей и границ являются, если нет возможности доводить их до конца, эффективными эвристическими процедурами.

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

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

Можно предложить много процедур решения этой задачи, например, физическое моделирование. На плоской доске рисуется карта местности, в города, лежащие на развилке дорог, вбиваются гвозди, на каждый гвоздь надевается кольцо, дороги укладываются верёвками, которые привязываются к соответствующим кольцам. Чтобы найти кратчайшее расстояние между 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, т. е. bj£bk; 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 элементов, т. е. алгоритм Дейкстры имеет квадратичную сложность. Проиллюстрируем работу алгоритма Дейкстры численным примером (для большей сложности, считаем, что некоторые города (вершины)  i,j не соединены между собой, т. е. D[i,j]=∞). Пусть, например, i=3. Требуется найти кратчайшие пути из вершины 3. Содержимое массивов a,b,c после выполнения первого пункта показано на табл. 12:

Очевидно, содержимое таблицы меняется по мере выполнения общего шага. Это видно из следующей таблицы:

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

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