Скажем, у нас есть круговой список, представляющий решение задачи о коммивояжере. Этот список изначально пуст.
Если пользователю разрешено вводить город и его координаты одну за другой, какую эвристику можно использовать для вставки этих координат в уже существующий тур?
В примере используется эвристика ближайшего соседа: новая координата вставляется после ближайшей координаты, уже находящейся в туре.
Какие еще есть варианты (псевдокод, если возможно).
Вы, конечно, можете обобщить идею, которую вы упомянули:
Определить k'th_path(v) = minimum weight of a path including max{k,not_visited cities} cities
Обратите внимание, что вычисление k-го пути равно O(|V|^k) [эта граница не точна]
Особые случаи:
k=1 вы получаете ближайшего соседа, как вы предложили.k=|V| вы получите оптимальное решение [обратите внимание, что его будет очень сложно вычислить].Существует множество эвристик построения, которые вы можете использовать, такие как «Первое соответствие», «Уменьшение первого соответствия», «Наилучшее соответствие», «Уменьшение наилучшего соответствия» и «Самая дешевая вставка». Эти эвристики построения обычно применяются при упаковке контейнеров, но их также можно преобразовать в TSP. Документация об этих эвристиках здесь.
Поскольку вы вставляете только 1 неназначенный объект за раз, все они в основном возвращаются к тому, что вы называете эвристикой ближайшего соседа (с небольшим изменением связей), но обратите внимание, что это не то, что они обычно делают. вызов ближайшего соседа. Ближайший сосед всегда добавляет в конец строки ближайшего соседа всех неназначенных объектов.
Теперь то, что вам действительно нужно, — это достойное решение без необходимости перезапуска всей эвристики построения. Это сложнее: добро пожаловать в повторяющееся планирование и в реальном времени планирование (и эту документацию). Я работаю над примером с открытым исходным кодом для TSP и маршрутизации транспортных средств, который выполняет планирование в реальном времени.
Других эвристик нет, потому что TSP всегда стремится найти ближайшую координату. По крайней мере, я не знаю алгоритма, который может вставить координату и знает ближайшую координату, но есть много алгоритмов, чтобы найти хороший тур. Хорошей эвристикой является, например, алгоритм Кристофидеса, он работает только в евклидовом пространстве, но гарантирует, что решение будет в пределах 3/2 от оптимального. Кодить не очень легко. В частности, алгоритм Эдмонда Блума v предназначен для экспертных навыков. Важность гарантии недостаточно высока, потому что как бы вы объяснили, что ваш метод может привести к абсурду в какой-то редкой ситуации?
