Содержание
- 1 Аннотация научной статьи по математике, автор научной работы — Канцедал Сергей Андреевич, Костикова Марина Владимировна
- 2 Похожие темы научных работ по математике , автор научной работы — Канцедал Сергей Андреевич, Костикова Марина Владимировна
- 3 Dynamic programming for travelling salesman problem
- 4 Текст научной работы на тему «Динамическое программирование для задачи коммивояжера»
Классическая задача коммивояжера (ЗК) формулируется следующим образом: имеется полный взвешенный ориентированный граф без петель G с множеством вершин N = <1, 2,…, n>; веса всех дуг неотрицательны; в этом графе требуется найти гамильтонов цикл минимального веса.
Исходную информацию по ЗК считаем представленной в виде матрицы размера nxn. S =
В типовой интерпретации вершины 1, 2,…, n графа G – это города. Дуги отображают возможные элементарные переходы. Коммивояжеру, изначально находящемуся в городе 1, необходимо обойти все остальные города, побывав в каждом из них ровно по одному разу, и затем вернуться в город 1. Веса дуг графа трактуются как длины соответствующих элементарных переходов. Требуется найти имеющий минимальную длину допустимый (т.е. удовлетворяющий наложенным требованиям) маршрут коммивояжера. С учетом других возможных интерпретаций, на матрицу S требование симметричности не налагается, не считается обязательным и выполнение неравенства треугольника.
Под методом ветвей и границ понимается алгоритм решения задачи, имеющий древовидную структуру поиска оптимального решения и использующий результаты решения оценочных задач. Древовидная структура называется обычно деревом ветвления.
Один из основных алгоритмов решения ЗК основан на принципе динамического программирования. При изложении этого алгоритма будем придерживаться терминологии, соответствующей приведенной типовой интерпретации задачи.
Пусть i – произвольный город (i N), а V – любое подмножество городов, не содержащее города 1 и города i. Через М(i, V ) обозначим совокупность путей, каждый из которых начинается в городе i, завершается в городе 1 и проходит в качестве промежуточных только через города множества V, заходя в каждый из них ровно по одному разу. Через В(i, V ) обозначим длину кратчайшего пути множества М(i, V ). Для решаемой задачи В(i, V) – функция Беллмана. Как очевидно, В(1, <2, 3, …, n>) – искомая минимальная длина простого (без самопересечений) замкнутого пути, проходящего через все города.
Если V – одноэлементное множество, V =
Предположим, что значения функции В(i, V ) для всех i N <1>и всех возможных k-элементных (k 0), n – число городов.
Пример 1.1 Решить задачу коммивояжера, определяемую матрицей:
Сначала, пользуясь формулой (1.1), определяем значения В(i,
В(2, <3>) = 5 + 6 = 11; В(3, <2>) = 2 + 2 = 4; В(4, <2>) = 5 + 2 = 7;
В(2, <4>) = 2 + 1 = 3; В(3, <4>) = 1 + 1 = 2; В(4, <3>) = 4 + 6 = 10.
Далее по формуле (1.2) последовательно получаем (в левой части каждого из ниже записанных равенств выделены те значения параметра j, на которых при подсчете реализуется указанный в правой части (1.2) минимум):
В(2, <3, 4>) = min [s23 + B(3,<4>); s24 + B(4,<3>)] = min(5 + 2; 2 + 10)=7;
В(3, <2, 4>) = min [s32 +B(2,< 4>); s34 + B(4,< 2>)] = min(2 + 3; 1 + 7 )=5;
В(4, <2, 3>) = min [s42 + B(2,< 3>); s43 + B(3,< 2>)] = min(5 + 11; 4 +4)=8;
= min (4 +7; 3 +5; 4 + 8 ) = 8.
Итак, оптимальное значение критерия в рассматриваемом примере равно 8.
Выполненные выделения позволяют определить оптимальный маршрут. Он следующий:
Для записи соотношений, по которым реализуется прямой метод Беллмана, введем новые обозначения. Пусть М'(V, i) – совокупность путей, каждый из которых начинается в городе 1, проходит в качестве промежуточных только через города подмножества V, заходя в каждый из них ровно по одному разу, и завершается в городе i; здесь, как и ранее, i – произвольный город (i N ), а V – любое подмножество N, не содержащее городов 1 и i. Длину кратчайшего пути множества М'(V, i) обозначим В*(V, i). Как очевидно, В*(<2, 3, …, n>, 1) – искомая минимальная длина простого (без самопересечений) замкнутого пути, проходящего через все города. Если V – одноэлементное множество, V =
Предположим, что значения функции В*(V, i) для всех i N и всех возможных k-элементных (k
Аннотация научной статьи по математике, автор научной работы — Канцедал Сергей Андреевич, Костикова Марина Владимировна
Описывается методика применения динамического программирования для решения задачи коммивояжера. Излагается алгоритм, а также приводятся теоретические и экспериментальные оценки его временной сложности и требований к памяти ЭВМ.
Похожие темы научных работ по математике , автор научной работы — Канцедал Сергей Андреевич, Костикова Марина Владимировна
Dynamic programming for travelling salesman problem
Technology of dynamic programming method application to solve travelling salesman problem is described. Algorithm labor intensiveness and requirements to computer memory are evaluated.
Текст научной работы на тему «Динамическое программирование для задачи коммивояжера»
С.А. КАНЦЕДАЛ, М.В. КОСТИКОВА
ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ ДЛЯ ЗАДАЧИ КОММИВОЯЖЕРА
Описывается методика применения динамического программирования для решения задачи коммивояжера. Излагается алгоритм, а также приводятся теоретические и экспериментальные оценки его временной сложности и требований к памяти ЭВМ.
1. Постановка задачи
Метод динамического программирования как способ глобальной оптимизации аддитивных и сводящихся к ним функционалов, автором которого является американский математик Р. Беллман, для решения задачи коммивояжера практически одновременно был предложен Р. Беллманом и М. Хелдом и Р. Карпом [1]. В дальнейшем мы следуем изложению Р. Беллмана.
Как известно, идея динамического программирования, опирающаяся на принцип оптимальности, состоит в том, что процесс оптимизации функционала рассматривается как последовательный n-шаговый процесс принятия решений, на каждом шаге которого принимается оптимальное решение. Для этого в рассмотрение вводится понятие состояний системы (задачи), относительно каждого из которых вычисляется оптимальное значение функционала, часто называемое значением функции Беллмана.
Смысл задачи коммивояжера состоит в том, что коммивояжер, выезжая из города
n, в определенной последовательности посещает остальные 1, 2, . n-1 городов и возвращается в пункт выезда n. При этом требуется определить такой маршрут, который дает наименьшую стоимость объезда городов при условии, что коммивояжер не заезжает ни в один из них более одного раза, что в терминологии графов означает найти гамильтонов цикл наименьшей длины.
Применительно к этой задаче метод динамического программирования интерпретируется как n-шаговый процесс принятия решений, на каждом шаге которого коммивояжер должен определить оптимальный маршрут объезда оставшихся городов в зависимости от того, в каком из них он находится.
Предположим, коммивояжеру по пути наименьшей стоимости удалось достичь города i и до возвращения в город n осталось посетить k городов: j1, j2, . jk. Путь наименьшей стоимости из города i в город n через оставшиеся города j1, j2, . j
обозначим B(n;j1, j2. jk) . Иными словами, так определим функцию Беллмана, значение которой устанавливается городом i и оптимальным порядком объезда оставшихся городов j1, j2, . jk. Следовательно, если будет найдено значение B(n; j1, j2. jn-1), т. е. наименьшая стоимость объезда всех городов, задача коммивояжера будет решена. При этом очевидно, что состояниями в n-шаговом процессе принятия решений будут города 1, 2, ., n -1 . Например, в задаче с 5-ю городами коммивояжер из города 5 может выехать в любой из оставшихся 1, 2, ., 4 городов, для которых и должны быть вычислены функции Беллмана.
Цель исследования – выяснение возможности использования на современных компьютерах метода динамического программирования для решения задачи коммивояжера.
Задача для достижения цели – представление функции Беллмана для решения указанной задачи.
2. Алгоритм решения
Действия алгоритма продемонстрируем на примере задачи с 5-ю городами и матрицей
стоимости переездов из города в город: C =
Согласно концепции Р. Беллмана минимальная стоимость объезда городов окажется найденной, если на последнем 5-м шаге будет вычислено значение B(5;jbj2,j3,j4), т. е. определено направление наилучшего выезда из города 5. Так как из этого города коммивояжер может поехать в города 1, 2, 3, 4, а затем из каждого из них по оптимальному маршруту вернуться в город выезда, для 4-го шага принятия решений, рассматривая процедуру в обратном порядке (от 5-го к 1-му шагу), необходимо определить функции Беллмана для городов (состояний) 1, 2, 3, 4.
В связи с тем, что из города 1 коммивояжер в оптимальной последовательности должен проехать города j2 , j3 , j4 , из города 2 города j1 , j3 , j4 , из города 3 города j1 , j2 , j4 и из
города 4 города j1, j2, j3, функции Беллмана согласно B(i;j1,j2, . ,jk) для этих состояний будут иметь вид B(1;j2, j3, j4^ B(2;j1, j3, j4), B(3;jb j2, j4^ B(4;jb j2, j3). На этом основании, учитывая, что B(5; j1, j2, j3, j4) – минимальная стоимость объезда, для вычисления функции Беллмана на 5-м шаге процесса принятия решений получаем выражение
B(5; ь j2 , j3 , j4) =
= min <[+B(1; j2 , j3 , j4)l>[c52 +B(2; jl, j3 , j4)], [c53 +B(3; j1, j2 , j4)] [c54 +B(4; j1, j2, j3)]>,(1)
в котором c51, c52, c53, c54 – стоимость переездов из города 5 в города 1, 2, 3, 4, взятые из матрицы C.
В свою очередьзначения функдийБеллмана B(1;j2,jз,j4), B(2;j1,j3,j4), B(3;j1,j2,j4), B(4; j1, j 2, 3), которые должны вычисляться на 4-м шаге принятия решений, с учетом того, что коммивояжер, выезжая из городов 1, 2, 3, 4, по оптимальному пути должен проехать три остальные города, определяются по выражениям:
Очевидно, что вычислить эти выражения можно в том случае, если на 3-м шаге
принятия решений найти значения функций Беллмана B(1;j2,j3), B(1;j2,j4), B(1;j3,j4);
B(2;j1,j3), B(2; j1, j4 ) , B(2;j3,j4); B(3; j1, j2 ) , B(3; j1, j4 ) , B(3;j2,j4);
B(4; j1, 3), B(4; j2, 3). Так как приведенные записи этих функций означают, что, например, для города 1 они должны вычисляться на основании вариантов посещения коммивояжером городов в последовательности 2, 3 или 3, 2, городов 2, 4 или 4, 2 и, наконец, городов 3, 4 или 4, 3, выбор предпочтительного маршрута для каждого варианта определяется соответствующим выражением:
B(1;j3,j4) = min^13 +B(3;j4)], [c14 + B(4;j3)]
Рассуждая аналогично, получаем формулы (4), по которым вычисляются значения функций Беллмана для состояний 2, 3, 4:
B(2; ji,із) = тіпЦс21 + B(i;j3)], + В(3;
Из приведенных выражений следует, что их значения могут быть найдены, если на 2-м шаге принятия решений будут вычислены значения функций B(i;j2), B(i;j3), B(i;j4); B(2; ji), B(2;j3), B(2;j4); B(3;ji), B(3;j2), B(3;j4); B(4;ji), B(4;j2), B(4;j3). В свою очередь эти функции могут быть найдены, если учесть, что, например, B(i;j2),
B(i;j3), B(i;j4) определяют оптимальные значения переезда коммивояжера из города i в города 2, 3, 4 и дальше из них в город 5, так как рассматривается 2-й шаг обратного процесса принятия решений.
B(i; j2) =Ci2 + B(2;j5), B(2; ji) =C2i +B(i;j5), B(3; ji) =C3i +B(i;j5), B(4; ji) =C4i +B(i;j5),
B(i; j3) =Ci3 +B(3;j5)» B(2; j3) =C 23 + B(3;j5),
B(3; j2) =C32 + B(2;j5), B(4; j2) =C42 + B(2;j5),
B(2; j4) =C24 + B(4;j5); B(3; j4) =C34 + B(4;j5);
B(4; j3) =C 43 + B(3;j5)-
В связи с тем, что функции B(i;j5), B(2;j5), B(3;j5), B(4;j5), фигурирующие в этих
выражениях, представляют собой стоимость переездов Ci5 , C25, C35, C45, содержащихся в матрице C, процесс попятного принятия решений может быть начат с i-го шага, сводящегося к перенесению указанных стоимостей в специальную таблицу, строки которой интерпретируются как номера шагов, а колонки определяют значения функций Беллмана.
На основании данных первой строки и выражений (5) получаем значения функций Беллмана для второй строки, по которым, используя выражения (3), (4), вычисляем значения функций третьей строки и т. д. Процесс вычислений и заполнения строк таблицы заканчиваем получением значения функции Беллмана для 5-го шага. Принятые обозначения и найденные значения приведены в табл. i.
Из нее следует, что наименьшая стоимость объезда 5-и городов равна 62, что совпадает с результатом, полученным в [2] методом ветвей и границ, а также методом прямого перебора.
Для определения маршрута, обеспечивающего найденную стоимость, поступаем следующим образом. В выражении B(5;ji,j2,j3,j4) найдем элемент, минимизирующий это
выражение. Таким является элемент C54 + B(4; ji, j2, j3) = i0 + 52 = 62. Это означает, что
из города 5 коммивояжер выезжает в город 4 (показывают индексы компоненты C 54 ). Для того, чтобы определить, в какой город он направляется из города 4, необходимо в выражении для B(4;ji, j2 ,j3 ) найти элемент, доставляющий минимум этому выражению. Так как
это элемент C4i + B(i; j2, j3) = 9 + 43 = 52, то из города 4 коммивояжер направляется в
город i. Минимум выражению B(i;j2,j3) доставляет элемент Ci2 + B(2; j3) = 25 + i8 = 43, из чего следует, что из города i коммивояжер выезжает в город 2. В свою очередь минимум B(2; j3) = C23 + B(3; j5) = i7 + i = i8. Следовательно, из города 2 коммивояжер
направляется в город 3, а из него возвращается в город 5. В результате получаем оптимальный маршрут объезда городов 5, 4, 1, 2, 3, 5, легко представляемый последовательностью дуг (5, 4), (4, 1), (1, 2), (2, 3), (3, 5) для удобной интерпретации на матрице стоимости переездов C. Дерево поиска решений и оптимальный маршрут на нем, выделенный жирными линиями со стрелками, показаны на рисунке.
Подводя итог изложенному выше, отметим, что алгоритм решения задачи коммивояжера методом динамического программирования, как и в большинстве случаев применения этого метода, состоит из двух этапов: вычисления оптимального значения функционала и на его основе определения последовательности оптимальных решений.
3. Оценки временной сложности алгоритма и требований к памяти ЭВМ
Теоретическую временную сложность алгоритма, т. е. зависимость времени решения задачи от ее размера n, определим традиционным путем: подсчитаем количество основных
вычислительных операций Hn, которые должен выполнить алгоритм при решении задачи. Согласно совокупности его действий такими операциями являются операции сложения и сравнения. Подсчет суммарного количества этих операций выполним для каждого шага алгоритма отдельно.
На 2-м его шаге для получения значений функций Беллмана необходимо выполнить лишь операции сложения. Поэтому, поскольку число состояний задачи равно n -1, всего согласно выражениям (5) для 2-го шага требуется выполнить (n -1) • (n – 2) сложения.
На 3-м шаге алгоритма для вычисления значений функций Беллмана по каждому из n -1 состояний согласно выражениям (3), (4) требуется вычислить последовательность минимальных значений для пар городов. При этом для каждой пары необходимо выполнить два сложения и одно сравнение. Общее же число операций, которое требуется выполнить для каждого состояния, определяется количеством пар городов, которое, как очевидно, зависит от размера задачи. Для определения этого числа, как функции n, обратимся к примерам.
В задаче из пяти городов 1, 2, 3, 4, 5, предполагая, что коммивояжер находится в городе 1, он может посетить города (2, 3) или (3, 2), города (2, 4) или (4, 2), города (3, 4) или (4, 3). Значения функций Беллмана для этого случая вычисляются по выражениям (3). Таким образом, размерность n = 5 определяет три пары (2, 3), (2, 4), (3, 4), т.е. общее количество пар S = 1 + 2 = 3 .
Рассмотрим теперь задачу с шестью городами 1, 2, 3, 4, 5, 6. В этом случае пары городов, которые может посетить коммивояжер, находясь в городе 1, такие: (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5). В результате S = 1 + 2 + 3 = 6. По аналогии для задачи с семью городами получим такую последовательность пар: (2, 3), (2, 4), (2, 5), (2, 6), (3, 4), (3, 5), (3, 6), (4, 5), (4, 6), (5, 6), т. е. S = 1 + 2 + 3 + 4 = 10.
Как известно, общая формула для вычисления суммы ряда 1 + 2 +. + n такая:
. Учитывая, что в задаче n интерпретируется как число состояний, равное
n -1, и отсчет пар начинается со второго элемента последовательностей городов, для
* с [(n -1) – 2] • [(n -1) -1] (n – 3) • (n – 2) v
числа пар по общей формуле получаем S = —–—^–—± = –—–. Учиты-
вая, что каждая пара требует выполнения трех основных операций и количество городов, для которых определяется S, равно n -1, для числа основных операций третьего шага
H 3 S ( 1) 3 • (n – 3) • (n – 2) • (n-1)
Как следует из примера, на четвертом шаге алгоритма по выражениям (2) требуется найти минимальные значения для последовательности троек городов, которые может посетить коммивояжер, находясь в каком-либо другом городе. Число таких троек, как и число пар, зависит от размера задачи.
Таблица 1. Обозначения и значения функции Беллмана
Обозначения и значения функции Беллмана
B(1;j5) B(2;j5) B(3;j5) B(4;j5)
B(1;j2) B(1;j3) B(1;j4) B(2;j1) B(2;j3) B(2;j4) B(3;j1) B(3;j2) B(3;j4) B(4;j1) B(4;j2) B(4;j3)
37 32 18 36 46 40 12 36 75 25
B(1;j2, j3) B(1;j2, j4 ) B(1;j3, j4) B(2;j1, j3) Ж2^ j4) Ж2;^ j4) B(3;j1, j2) B(3;j1, j4) Жйй, j4) B(4;j1, j2) B(4;j1, j3) B(4;j2, j3)
52 46 42 29 47 42 51 59 50 64
B(1;j2> j3, j4) B(2;j1, j3> j4) B(3;j1, j2 ’ j4) B(4;j1, j2,j3)
Легко убедиться в том, что число пар городов определяется числом сочетаний Сn_2 • Тогда по аналогии число их троек равно Сn_2, число четверок С4_2 и т. д. Учитывая, что на последнем шаге алгоритма ищется минимальное значение стоимости маршрута для последовательности из n -1 городов, а на предпоследнем шаге – для последовательности
из n – 2 городов, получаем, что для этого шага число сочетаний равно С П _2 = 1. С другой стороны, так как на 3-м шаге алгоритма при минимизации необходимо выполнить два сложения и одно сравнение, на четвертом – три сложения и два сравнения, получаем, что для С m_2 потребуется выполнить 2 • m-1 основных операций. На этом основании для С П _2 число таких операций равно 2 • (n – 2) -1 = 2 • n-5. Принимая во внимание, что на последнем шаге алгоритма необходимо найти минимум из n -1 элементов, в каждом из которых имеется операция сложения, получаем, что для этого шага необходимо выполнить (n-2) + (n-1) = 2 • n-3 основные операции.
Таким образом, на основании приведенных выкладок получаем, что общее число основных операций, которые должен выполнить алгоритм, решая задачу для n городов, может быть найдено по выражению:
Hn = (n-1) • (n-2) + (n-1) • [(2 • m-1) • сП-2 + (2 • m-1) • сП_2 +. +
+ (2 • m-1) • Cn-2 + 2 • n-5] + 2 • n-3 = (n-1) • [(2 • m-1) • CL + (2 • m-1) • CL +. + (6) + (2 • m-1) • CJL + 3 • n – 7] + 2 • n-3,
в котором m = 2, 3, . n-3. К этому числу основных операций необходимо прибавить то их количество, которое потребуется выполнить при определении оптимального маршрута объезда городов на основе найденного значения функционала. Оно равно сумме, получаемой сложением числа операций каждого шага, заканчивая 2-м шагом и исключая n-й шаг, так как на этом шаге индекс элемента, доставляющий минимальное значение функционалу, легко фиксируется. Поэтому выражение для указанного числа операций имеет вид [(n-2) + (n-3)] + [(n-3) + (n – 4)] +. + 3 +1 = (2 • n-5) + (2 • n – 7) + . + 4 .
Таким образом, при двухэтапном процессе реализации алгоритма потребуется выполнить Hn = (n-1)• [(2• m-1) • C2-2+(2 • m-1) • C3n-2 +. + (2 • m-1) • C^-l + 3 • n-7] + 2 • n-3 +
+ (2• n-5) + (2• n-7) +. + 4 основных операций.
Полученное выражение позволяет экспериментальным путем определить вычислительную сложность алгоритма. С этой целью для ряда размеров задачи n = 5, 10, 15, 20, 25 были вычислены значения H n , представленные в табл. 2.
Таблица 2. Число основных вычислительных операций
n = 5 n = 10 n = 15 n = 20 n = 25
107 16190 1376803 106717205 4429186681
Данные табл. 2 приближены эмпирической формулой Hn(n) = 4,0282e0,3912n, которая
показывает, что при увеличении размера задачи число основных вычислительных операций, которые выполняет алгоритм, растет экспоненциально. При этом показатель экспоненты равен 0,3912 • n, а постоянный множитель – 4,0282. Поэтому согласно этой формуле, например, при n = 60 число операций окажется примерно таким Hn (60) = 4,0282 • e0,3912*60 = 4,0282 • e23,472 = 62931937743 , с которым компьютер с тактовой частотой центрального процессора 4 ГГц справится не более, чем за 20 с.
Память ЭВМ при увеличении размера задачи растет как количество столбцов табл. 1, умноженное на количество ее строк n -1, предназначенных для хранения значений функций Беллмана при условии, что для этих целей в простейшем случае используется матрица. В свою очередь количество столбцов определяется числом состояний n – 1 , умноженным на „ _ (n – 2) • (n – 3)
число пар операций S = , которые необходимо выполнить на 3-м шаге алгоритма. Таким образом, требуемая память определяется формулой
(n-1)2 • (n – 2) • (n – 3)
из которой следует, что при увеличении
размера задачи n она растет как полином четвертой степени n.
Для n = 60 значение этого полинома равно 5754093. Умножив его на 4, получим число байт памяти ЭВМ, равное 23016372, т. е. около 22 МБ, которые необходимы для хранения значений функции Беллмана при решении задачи указанного размера. Очевидно, что для компьютеров, располагающих оперативной памятью, например, 4 ГБ, указанное число достаточно просто помещается в этой памяти.
Таким образом, на основании анализа и расчетов получены новые результаты, показывающие объективную возможность решения задачи коммивояжера с числом городов 60 -65 методом динамического программирования на современных персональных компьютерах за практически приемлемое время (не более 30 с).
Научная новизна работы – сконструирован алгоритм, получены оценки его временной сложности, которые показывают возможность его применения на современных компьютерах. Практическая значимость – алгоритм легко программируем, после чего он может быть применен на практике.
Список литературы: 1. Беллман Р. Применение динамического программирования к задаче о коммивояжере // Кибернетический сборник. М.: Мир, 1964. Т. 9. С. 219 – 228. 2. Гудман С., Хиднетиеми С. Введение в разработку и анализ алгоритмов. М.: Мир, 1981. 368 с.
Поступила в редколлегию 04.03.2014 Канцедал Сергей Андреевич, д-р техн. наук, профессор кафедры прикладной математики Западнодонбасского института Межрегиональной академии управления персоналом. Научные интересы: математическое моделирование, теория расписаний и ее применение. Адрес: Украина, 51400, Днепропетровская обл., Павлоград, ул. Днепровская, 400/1. Костикова Марина Владимировна, канд. техн. наук, доцент кафедры информационных технологий и мехатроники Харьковского национального автомобильно-дорожного университета. Научные интересы: математическое моделирование, теория расписаний и ее применение. Адрес: Украина, 61002, Харьков, ул. Петровского, 25, тел. 707-37-74.
Задача коммивояжера (TSP): учитывая набор городов и расстояние между каждой парой городов, проблема состоит в том, чтобы найти кратчайшее Возможный маршрут, который посещает каждый город ровно один раз и возвращается в исходную точку.
Обратите внимание на разницу между гамильтоновым циклом и TSP. Задача цикла Гамильтонина – найти тур, который посещает каждый город ровно один раз. Здесь мы знаем, что гамильтонов тур существует (так как граф полон), и на самом деле существует много таких туров, проблема состоит в том, чтобы найти гамильтонов цикл с минимальным весом.
Например, рассмотрим график, показанный на рисунке справа. Тур TSP на графике 1-2-4-3-1. Стоимость тура 10 + 25 + 30 + 15, что составляет 80.
Проблема известная NP трудная проблема. Не существует полиномиального времени для решения этой проблемы.
Ниже приведены различные решения проблемы коммивояжера.
Наивное решение:
1) Рассмотрите город 1 как начальную и конечную точку.
2) Генерировать все (n-1)! Перестановки городов.
3) Рассчитать стоимость каждой перестановки и отслеживать минимальную перестановку затрат.
4) Вернуть перестановку с минимальными затратами.
Сложность времени: Θ (n!)
Динамическое программирование:
Пусть заданным набором вершин будет <1, 2, 3, 4,… .n>. Давайте рассмотрим 1 как начальную и конечную точку вывода. Для каждой другой вершины i (кроме 1) мы находим путь минимальной стоимости с 1 в качестве начальной точки, i в качестве конечной точки и всех вершин, которые появляются ровно один раз. Пусть стоимость этого пути будет стоить (i), стоимость соответствующего цикла будет стоить (i) + dist (i, 1), где dist (i, 1) – это расстояние от i до 1. Наконец, мы возвращаем минимум всех значений [cost (i) + dist (i, 1)]. Это выглядит просто пока. Теперь вопрос, как получить стоимость (я)?
Чтобы рассчитать стоимость (i) с использованием динамического программирования, нам нужно иметь рекурсивное отношение с точки зрения подзадач. Определим термин C (S, i) как стоимость пути минимальной стоимости, посещающего каждую вершину в множестве S ровно один раз, начиная с 1 и заканчивая на i .
Мы начнем со всех подмножеств размера 2 и вычислим C (S, i) для всех подмножеств, где S – это подмножество, затем вычислим C (S, i) для всех подмножеств S размера 3 и так далее. Обратите внимание, что 1 должен присутствовать в каждом подмножестве.
Для набора размера n мы рассматриваем n-2 подмножества каждого размера n-1, так что все подмножества не имеют nth в них.
Используя вышеупомянутое рекуррентное отношение, мы можем написать решение на основе динамического программирования. Есть максимум O (n * 2 n ) подзадач, и для решения каждой из них требуется линейное время. Таким образом, общее время работы составляет O (n 2 * 2 n ). Временная сложность намного меньше, чем O (n!), Но все же экспоненциальная. Требуемое пространство также экспоненциально. Так что этот подход также невозможен даже для немного большего числа вершин.
Вскоре мы обсудим приближенные алгоритмы задачи коммивояжера.
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме
