Задача коммивояжера

При реализации надо уметь на каждом шаге быстро выбирать безопасное ребро. Для этого удобно воспользоваться очередью с приоритетами (кучей). Алгоритм получает на вход граф G и его корень r – вершина, на которой  будет наращиваться минимальный  остов. Все вершины G, еще не попавшие в дерево, хранятся в очереди с  приоритетом Ω. Приоритет вершины v определяется значением key[v], которое  равно минимальному весу ребер, соединяющих v с вершинами минимального остова. Поле p[v] для вершин дерева указывает  на родителя, а для вершин из очереди, указывает на остов дерева, в которою  ведет ребро с весом key[v] (одно из таких ребер, если их несколько).  
 

2.4 ВЫВОД 

  

В завершение рассказа о жадных алгоритмах приведу пример. Рассмотрим небольшую «детскую»  задачу. Допустим, что у нас есть монеты достоинством 25, 10, 5 копеек и 1 копейка  и нужно вернуть сдачу 63 копейки. Почти не раздумывая, мы преобразуем  эту величину в две монеты по 25 копеек, одну монету в 10 копеек и три  монеты по одной копейке. Нам не только удалось быстро определить перечень монет нуясного достоинства, но и, по сути, мы составили самый короткий список монет требуемого достоинства. 

Алгоритм, которым  мы в этом случае воспользовались, заключался в выборе монеты самого большого достоинства (25 копеек), но не больще 63 копеек, добавлению ее в список сдачи и вычитанию  ее стоимости из 63 (получается 38 копеек). Затем снова выбираем монету самого больщого достоинства, но не больще остатка (38 копеек): этой монетой опять оказывается  монета в 25 копеек. Эту монету мы опять  добавляем в список сдачи, вычитаем ее стоимость из остатка и т.д. 

Этот метод внесения изменений называется «жадным» алгоритмом. На каждой отдельной стадии «жадный» алгоритм выбирает тот вариант, который  является локально оптимальным в  том или ином смысле. Обратите внимание, что алгоритм для определения  сдачи обеспечивает в целом оптимальное  рещение лищь вследствие особых свойств  монет. Если бы у нас были монеты достоинством 1 копейка, 5 и 11 копеек и  нужно было бы дать сдачу 15 копеек, то «жадный» алгоритм выбрал бы сначала  монету достоинством 11 копеек, а затем  четыре монеты по одной копейке, т.е. всего пять монет. Однако в данном случае можно было бы обойтись тремя  монетами по 5 копеек.  

И все приведенные  выше алгоритмы являются «жадными». 

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

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

3. ГЕНЕТИЧЕСКИЙ АЛГОРИТМ 

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

Задача кодируется таким образом, чтобы её решение  могло быть представлено в виде вектора («хромосома»). Случайным образом  создаётся некоторое количество начальных векторов («начальная популяция»). Они оцениваются с использованием «функции приспособленности», в результате чего каждому вектору присваивается  определённое значение («приспособленность»), которое определяет вероятность  выживания организма, представленного  данным вектором. После этого с  использованием полученных значений приспособленности  выбираются вектора (селекция), допущенные к «скрещиванию». К этим векторам применяются «генетические операторы» (в большинстве случаев «скрещивание» - crossover и «мутация» - mutation), создавая таким образом следующее «поколение». Особи следующего поколения также  оцениваются, затем производится селекция, применяются генетические операторы  и т. Д. Так моделируется «эволюционный  процесс», продолжающийся несколько  жизненных циклов (поколений), пока не будет выполнен критерий останова алгоритма. Таким критерием может  быть: нахождение глобального, либо субоптимального  решения; исчерпание числа поколений, отпущенных на эволюцию; исчерпание времени, отпущенного на эволюцию. Генетические алгоритмы служат, главным образом, для поиска решений в очень  больших, сложных пространствах  поиска. 

Таким образом, можно  выделить следующие этапы генетического  алгоритма: 

создание начальной  популяции; 

вычисление функций  полезности для особей популяции (оценивание); 

выбор индивидов  из текущей популяции (селекция); 

скрещивание и\или  мутация; 

вычисление функций  полезности для всех особей; 

формирование нового поколения; 

если условия совпали, то решение найдено (конец цикла), если нет, то цикл повторяется. 

Применяются генетические алгоритмы для решения следующих  задач: 

оптимизация функций, разнообразные задачи на графах (задача коммивояжера, раскраска, нахождение паросочетаний), настройка и обучение искусственной  нейронной сети, задачи компоновки, составление расписаний, игровые  стратегии, аппроксимация функций, искусственная жизнь, биоинформатика (свёртывание белков). 
 

4. NP-ПОЛНАЯ ЗАДАЧА 

  

Все эффективные (сокращающие  полный перебор) методы решения задачи коммивояжёра — методы эвристические («жадные алгоритмы»). В большинстве  эвристических методов находится  не самый эффективный маршрут, а  приближённое решение. Зачастую востребованы так называемые any-time алгоритмы, то есть постепенно улучшающие некоторое текущее  приближенное решение. 

Задача коммивояжёра есть NP-полная задача. Часто на ней  проводят обкатку новых подходов к эвристическому сокращению полного  перебора. 

В теории алгоритмов NP-полные задачи — это класс задач, лежащих в классе NP (то есть для  которых пока не найдено быстрых  алгоритмов решения, но проверка того, является ли данное решение правильным, проходит быстро), к которым сводятся все задачи класса NP. 

Назовём языком множество  слов над алфавитом Σ. Задачей  здесь является определение того, принадлежит данное слово языку  или нет. Язык L1 называется сводимым (по Карпу) к языку L2, если существует функция, вычислимая за полиномиальное время, обладающая следующим свойством: f(x) принадлежит L2 тогда и только тогда, когда x принадлежит L1. Язык L2 называется NP-трудным, если любой язык из класса NP сводится к нему. Язык называют NP-полным, если он NP-труден и при этом сам  лежит в классе NP. Таким образом, если будет найден алгоритм, решающий хоть одну NP-полную задачу за полиномиальное время, все NP-задачи будут лежать в  классе P. 

Равенство классов P и NP уже более 30 лет является открытой проблемой. Научное сообщество склоняется к отрицательному решению этого  вопроса — в этом случае за полиномиальное время решать NP-полные задачи не удастся. 
 

5. МЕТОД ВЕТВЕЙ  И ГРАНИЦ 
 
 

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

Основа этого, ныне широко распространенного метода состоит  в построении нижних оценок решения, которые затем используются для  отбраковки неконкурентоспособных  вариантов. 

Функция f(xi, xj) принимает  конечное число значений сij, которые  мы можем представить в виде таблицы (Рисунок 5.1). Предположим, что мы выбрали  некоторый путь Ss. Его длина будет  равна 

(5.1) 

причем сумма (5.1) распространена по i, j так, что каждый из индексов встречается в ней  один и только один раз. Величины сij с двумя одинаковыми индексами  мы приняли равными ∞. 

Так как в каждый из вариантов s входит только один элемент  из каждой строки и столбца, то мы можем  проделать следующую операцию, которая  здесь называется приведением матрицы. Обозначим через hi наименьший элемент  из строки номера i и построим новую  матрицу С(1) с элементами 
 

  

Матрица С(1) определяет новую задачу коммивояжера, которая, однако, в качестве оптимальной будет  иметь ту же последовательность городов. Между величинами ls и ls(1) будет существовать, очевидно, следующая связь: 
 
 

Заметим, что в  каждой из строк матрицы С(1) будет  теперь, по крайней мере, один нулевой  элемент. Далее обозначим через gj наименьший элемент матрицы С(1), лежащий в столбце номера j, и  построим новую матрицу С(2) с элементами 

  

Величины hi и gj называются константами приведения. Оптимальная  последовательность городов для  задачи коммивояжера с матрицей С(2) будет, очевидно, такой же, как и  для исходной задачи, а длины пути для варианта номера s в обоих  задачах будут связаны между  собой равенством 

                                        (5.2) 

где 

                        (5. 3) 

т. Е. d0 равна сумме  констант приведения. 

Обозначим через l* решение  задачи коммивояжера, т.е. 
 
 
 

где минимум берется  по всем вариантам s, удовлетворяющим  условию (α) Тогда величина d0 будет  простейшей нижней оценкой решения: 

                                                (5.4) 

Будем рассматривать  теперь задачу коммивояжера с матрицей С(2) которую мы будем называть приведенной  матрицей. 

Рассмотрим путь, содержащий непосредственный переход  из города номера i в город номера j, тогда для пути s, содержащего  этот переход, мы будем иметь, очевидно, следующую нижнюю оценку: 

  

Следовательно, для  тех переходов, для которых  = 0, мы будем иметь снова оценку (5.4). Естественно ожидать, что кратчайший путь содержит один из таких переходов  — примем это соображение в  качестве рабочей гипотезы. Рассмотрим один из переходов, для которого  =0, и обозначим через  множество  всех тех путей, которые не содержат перехода из i в j.  

Так как из города i мы должны куда-то выйти, то множество  содержит один из переходов i→k, где k ≠ j; так как в город номера j мы должны прийти, то множество  содержит переход m→j, где т ≠ i.  

Следовательно, некоторый  путь ls из множества (ij), содержащий переходы i→k и m→j, будет иметь следующую  нижнюю оценку: 

  

Обозначим через 
 

  

Тогда очевидно, что  для любого ls из множества путей  мы будем иметь оценку  

(5.5) 

Мы предполагаем исключить некоторое множество  вариантов , поэтому мы заинтересованы выбрать такой переход i → j, для  которого оценка (5.5) была бы самой высокой. Другими словами, среди нулевых  элементов матрицы С(2) выберем  тот, для которого максимально. Это  число обозначим через  Таким  образом, все множество возможных  вариантов мы разбили на два множества I1 и I2. Для путей из множества I1, мы имеем оценку (5.4). Для путей из множества I2 оценка будет следующей: 

(5.6) 

Рассмотрим теперь множество I1 и матрицу С(2). Так  как все пути, принадлежащие этому  множеству, содержат переход i → j , то для  его исследования нам достаточно рассмотреть задачу коммивояжера, в  которой города номеров i и j совпадают. Размерность этой задачи будет уже  равна N – 1, а ее матрица получится  из матрицы С(2) вычеркиванием столбца  номера j и строки но мера i. 

Поскольку i → j невозможен, то элемент  принимаем равным бесконечности. 
 
 
 

Рассмотрим случай N=3 (Рисунок 5.2, а), и предположим, что  мы рассматриваем тот вариант, который  содержит переход 3 → 2. Тогда задача коммивояжера после вычеркивания третьей  строки и второго столбца вырождается в тривиальную. Ее матрица изображена на рисунке 5.2, в. В этом случае мы имеем единственный путь, и его длина будет, очевидно, равна сумме