Главная

Комми

Главная
Комми
Алгоритм
Быстрый
Средний
Точный
Эксперимент

Карта

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



По этой теме у меня только здесь было более десятка страниц, были материалы и в других местах - даже в моей книге есть раздел, посвящённый TSP! Однако все эти тексты в значительной мере устарели, так что я попробую переписать этот раздел, оставив только "свежатинку".

Современное состояние задачи

  • Размер графов, для которых к настоящему времени найдено точное решение, не превышает нескольких десятков тысяч узлов (максимально - 85900 узлов).
  • Процессорное время (в пересчёте на 500 MHz Alpha processor) для решения этих задач составляет десятки лет (максимально - 136 лет для "графа-чемпиона" на 85900 узлов).
  • Ни одно из известных на сегодняшний момент точных решений, строго говоря, нельзя считать таковым, поскольку расстояния между узлами округляются до целых, т.е. вычисляются приближённо. Например, для графа lrb744710 при средней длине ребра best-known тура менее 2.2 (!) ошибка определения длины тура составляет почти 6%! О каком же "точном" решении можно вообще говорить?
  • Практически все известные графы "геометрические" (заданы точками на плоскости или на шаре) и практически все известные алгоритмы решения TSP используют это обстоятельство для ускорения поиска.

Итого: а) точных решений задачи коммивояжёра нет вообще и б) алгоритмов решения таких задач нет вообще. А всё это "мелкое жульничество" с округлением до целых лишь маскирует тот факт, что поиск действительно точных решений задач для таких графов потребовал бы уже не десятилетий, а многих тысячелетий процессорного времени.

Сложность задачи (жульничество наоборот)

Задача коммивояжёра относится к числу трансвычислительных: уже при относительно небольшом числе городов (66 и более) она не может быть решена методом перебора вариантов никакими теоретически мыслимыми компьютерами за время, меньшее нескольких миллиардов лет. Трансвычислительная задача (англ. Transcomputational problem) - в теории сложности вычислений задача, для решения которой требуется обработка более чем 1093 бит информации. Число 1093, называемое "пределом Бремерманна", представляет собой общее число бит, обрабатываемых гипотетическим компьютером размером с Землю за период времени, равный общему времени существования Земли.

На мой взгляд, все эти "страшилки" есть полная чушь. Да, печально знаменитый brute force действительно имеет экспоненциальную (даже факториальную) сложность - и что с того? С какой стати экспоненциальность метода (тем более, столь дурацкого метода) является основанием говорить про NP-полноту задачи? Кто сказал, что даже полный перебор всех вариантов не может быть выполнен за полиномиальное время? Вспомним, например, про ветви с границами. Это ведь считается разновидностью полного перебора - не так ли? Несмотря на то, что варианты смотрятся отнюдь не все, ибо какой же идиот станет искать решение, если уже доказано, что его там нет, и быть не может? Понятно, что ветви с границами экспоненциальны, но у меня вопрос, господа: кто посмеет отвергнуть гипотезу, что может существовать другой алгоритм, который будет отсекать заведомо бесперспективные варианты ещё лучше, чем ветви с границами? Например, так хорошо отсекать, что количество туров-кандидатов после отсечения будет полиномиально по отношению к числу узлов графа? Ну, а если кто осмелится, помните: именно про такой алгоритм я здесь сейчас и пишу. И называется он именно "полный перебор" - не brute force, а очень умный, тонкий, сложный и (как я свято убеждн) полиномиальный алгоритм. Точнее, даже набор алгоритмов, которые передают друг другу задачу "по цепочке".

Постановка задачи

  • Алгоритм должен уметь находить как точные, так и "жульническо-точные" решения: поскольку буквально все существующие TSP-задачи считаются с округлением до целых (т.е. минимизируют вовсе не длину тура, а ошибки округления), нам придётся продемонстрировать, что мы умеем их решать и в таком режиме тоже. Скорость и качество работы алгоритма не должны сколько-нибудь заметно зависеть от точности вычислений.
  • Алгоритм не должен быть слишком требовательным к ресурсам: он должен работать на обычной персоналке и позволять при этом обсчитывать очень большие графы, с миллионами узлов.
  • Поскольку TSP-задачи обычно многодневные, должна быть предусмотрена возможность отложить расчёт в любой момент с тем, чтобы возобновить его с момента откладывания в любое время.
  • Несмотря на то, что подавляющее большинство существующих TSP-графов заданы, как точки на плоскости или на шаре, использовать их геометрические особенности мы принципиально не хотим. Это противоречит постановке задачи и, по сути, является таким же жульничеством, как и округление. Конечно, для реальных практических задач можно и нужно использовать все возможности, но нас интересует не разработка конкретного приложения, а решение задачи в общем виде. Поэтому мы не будем использовать, например, такой очевидный (и весьма эффективный) метод разбиения исходного графа на подзадачи путём группировки узлов по близости их координат. Алгоритму должно быть безразлично, считается ли длина по координатам узлов, задана ли она таблично, выполняется или нет так называемое "неравенство треугольника". Отметим, кстати, что никаких приближённых алгоритмов, гарантирующих получение туров с погрешностью, не превышающей некоторой фиксированной величины, не существует: при несоблюдении неравенства треугольника ни алгоритм Эйлера, ни Кристофидеса, ни какой-либо другой не гарантируют (и не могут гарантировать) ничего - ни нескольких процентов ошибки, ни сотен миллионов.
  • Рассматривать будем только симметричную задачу коммивояжёра: если симметричная решается за полином, то и асимметричная гарантированно потребует лишь полиномиального времени.

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

18.08.2019 10:38
 
`