задача коми-вояжора любым способом решить в ручную

Метод аналогии плох тем, что полный перебор, как оптимальный метод решения, отбрасывается полностью и полностью заменяется каким-то другим методом. Я считаю, что так пренебрежительно поступать с полным перебором нельзя, потому что это единственный метод, который гарантированно даёт правильное решение задачи.

Для обхода этого препятствия люди просто отказываются от получения оптимального решения для больших N и вместо задачи коммивояжёра решают какую-то другую, очень похожую, аналогичную задачу. Такой метод подмены задачи получил название «эвристического решения», хотя эвристика в каждом случае это не более чем случайно выбранная аналогия. Например, отжиг это решение задачи путём имитации охлаждения кристаллизующихся веществ, жадный алгоритм это имитация поведения жадного человека, существуют методы, построенные по аналогии с поведением муравьёв, надувающимся воздушным шариком и т.п.

Оптимальное решение задачи коммивояжёра на десктопах возможно. Однако с ростом количества узлов время, затрачиваемое на полный перебор, растёт экспоненциально. Таким образом, на машине с четырёхядерным процессором 2,67 ГГц 10 узлов обсчитывается в среднем за 5 миллисекунд, 20 узлов за 15 минут, а на расчёт оптимального пути для 60 узлов уйдёт более 6 триллионов лет

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

2. Если следующее выбранное ребро пересекает одно из ранее построенных рёбер пропустить этот вариант и все те, которые он порождает.

1. При построении очередного варианта пути, подсчитывать его длину и если эта длина превышает уже найденный локальный минимум длины пропускать этот вариант и все те, которые он порождает.

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

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

Поэтому мы остановимся на первоначальной формулировке, и будем решать задачу в общем виде.

Формулировка 2 подразумевает, что входной узел задан, а выходным узлом может быть любой. Что требует полного перебора всех выходных узлов с последующим выбором кратчайшего пути из всех кратчайших.

Формулировка 1 подразумевает, что входным узлом может быть любой узел, а выходным один из ближайших к нему. Что требует полного перебора всех ближайших узлов к произвольно выбранному узлу.

Однако обе эти формулировки при ближайшем рассмотрении оказываются частными случаями первоначальной формулировки.

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

1. Необходимо обнаружить кратчайший гамильтонов цикл.

Есть мнения, что задача коммивояжёра может формулироваться ещё двумя способами:

Дано N узлов, расположенных на плоскости. Задан входной узел (Вх) и выходной узел (Вых). Необходимо обнаружить кратчайший путь, охватывающий все узлы, начинающийся во входном узле, заканчивающийся в выходном узле и проходящий через каждый узел только один раз.

Сформулируем задачу.

Решение задачи коммивояжёра рекурсивным полным перебором

10 сентября 2012 в 13:13

Решение задачи коммивояжёра рекурсивным полным перебором / Хабрахабр