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

Простейшие[править | править код]

• 
  полный перебор
  
• 
  случайный перебор
  
• 
  жадные алгоритмы
  
  • 
    метод ближайшего соседа
    
  • 
    метод включения ближайшего города
    
  • 
    метод самого дешёвого включения
    
• 
  метод минимального остовного дерева
  
• 
  метод имитации отжига
  

Все эффективные (сокращающие полный перебор) методы решения задачи коммивояжёра — методы эвристические. В большинстве эвристических методов находится не самый эффективный маршрут, а приближённое решение. Зачастую востребованы так называемые any-time-алгоритмы^{[уточнить]}, то есть, постепенно улучшающие некоторое текущее приближенное решение.
Существуют также постановки, в которых задача коммивояжёра становится NP-полной. Обычно такие постановки выглядят следующим образом: существует ли на заданном графе G такой обход, что его стоимость не превышает x. Часто на ней проводят обкатку новых подходов к эвристическому сокращению полного перебора.
На практике применяются различные модификации более эффективных методов: метод ветвей и границ и метод генетических алгоритмов, а также алгоритм муравьиной колонии.
Метод ветвей и границ[править | править код]
Основная статья: Метод ветвей и границ
Можно найти точное решение задачи коммивояжёра, то есть «вручную» вычислить длины всех возможных маршрутов и выбрать маршрут с наименьшей длиной. Однако даже для небольшого количества городов решать задачу таким способом практически невозможно. Для простого варианта, симметричной задачи с {\displaystyle n}  городами, существует {\displaystyle (n-1)!/2}  возможных маршрутов, то есть для 15 городов существует 43 миллиарда маршрутов и для 18 городов уже 177 триллионов. То, как стремительно растет продолжительность вычислений, можно показать на следующем примере. Если бы существовало устройство, находящее решение для 30 городов за час, то для двух дополнительных городов требуется в тысячу раз больше времени; то есть, более чем 40 суток.

Задача коммивояжёра для трех городов: красная пунктирная плоскость {\displaystyle x_{1}+x_{2}+x_{3}\geqslant 2}  отсекает все недопустимые решения с максимум одним ребром. Все точки в красном политопе удовлетворяют этому неравенству, и единственная допустимая точка это (1, 1, 1).
Методы дискретной оптимизации, в частности ветвей и границ, позволяют находить оптимальные или приблизительные решения для достаточно больших задач.
В геометрической интерпретации эти методы рассматривают задачу как выпуклый политоп, то есть многомерный многоугольник в {\displaystyle m} -мерном единичном кубе {\displaystyle [0,1]^{m}} , где {\displaystyle m}  равно количеству ребер в графе. Каждая вершина этого единичного куба соответствует маршруту, то есть вектору с элементами 0/1, что удовлетворяет описанным выше линейным неравенствам. Гиперплоскости, описываемые этими неравенствами, отсекают такие ребра единичного куба, которые не соответствуют ни одному маршруту.
На рисунке рядом показано применение метода для задачи с тремя узлами. В соответствие трем возможным ребрам между вершинами сопоставляются бинарные переменные {\displaystyle x_{1},\,x_{2}}  и {\displaystyle x_{3}} . В этом случае существует лишь один возможный маршрут, а именно тот, что проходит через три вершины. Этот маршрут удовлетворяет неравенству {\displaystyle x_{1}+x_{2}+x_{3}\geqslant 2} , которое утверждает, что маршрут должен проходить через минимум две вершины. Кроме этого маршрута, что соответствует вектору (1,1,1), неравенству удовлетворяют также все точки в отмеченной красным части этого неравенства. Плоскости, проходящие через красные линии, отсекают все углы, отвечающие несуществующим маршрутам с максимум одним ребром, а именно, ноль-вектор (0, 0, 0), единичные векторы (1, 0, 0), (0, 1, 0) и (0, 0, 1). Сильное неравенство {\displaystyle x_{1}+x_{2}+x_{3}\geqslant 3}  отсечет от единичного куба все, кроме единственной допустимой точки (1, 1, 1). В этом отдельном случае тот же эффект можно получить тремя неравенствами типа (1).
Для определения допустимого ребра с наименьшей длиной следует решить наборы задач линейной оптимизации, отсекающие секущими плоскостями ненужные части единичного куба и попытаться разделить единичный куб на меньшие политопы методом ветвей и границ.
Однако этого метода для быстрого поиска маршрутов обычно недостаточно. Основное преимущество точных методов заключается в том, что имея достаточно времени, они вычисляют кратчайший маршрут. Имея нижнюю границу для оптимальных решений, можно оценить то, насколько отличается найденный маршрут от оптимального. Например, имея нижнюю границу на уровне 100, и после нахождения маршрута длиной 102, оптимальный маршрут может находиться в пределах от 100 до 102. Так называемый интервал оптимальности, или максимальное относительное расстояние между длиной оптимального маршрута и кратчайшим известным маршрутом составит (102—100)/100 = 2 %, то есть длина найденного маршрута 102 максимум на 2 % отличается от оптимальной. Когда длина вычисленного маршрута равна длине предыдущего, считается, что найденное решение является оптимальным. Для поиска маршрутов приемлемой длины точные методы могут комбинироваться с эвристическими.
Метод ветвей и границ для решения задачи коммивояжёра был предложен в 1963 году группой авторов (Дж. Литл, К. Мурти, Д. Суини, К. Кэрол)^[3].