Коммивояжер по конструктивной эвристике

Question

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

Если пользователю разрешено вводить город и его координаты одна за другой, какую эвристику можно использовать для вставки этих координат в уже существующий тур?

---

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

Какие есть другие опции (если возможно, псевдокод).

Answer 1

Можно, конечно, обобщить идею, которую вы упомянули:

Определить k'th_path(v) = minimum weight of a path including max{k,not_visited cities} cities

Обратите внимание, что вычисление k-го пути составляет O(|V|^k) [эта граница не является жесткой]

Особые случаи :

• Для k=1 вы получаете ближайшего соседа, как вы и предлагали.
• для k=|V| вы получите оптимальное решение [обратите внимание, что оно будет очень обширным для расчета].

Answer 2

Существует множество строительных эвристик, которые вы можете использовать, таких как First Fit, First Fit Decreasing, Best Fit, Best Fit Decreasing и Cheap Insertion.Эвристика этих конструкций обычно применяется для упаковки бункеров, но они также могут быть преобразованы в TSP. Документация об этих эвристиках находится здесь.

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

Теперь то, что вы действительно хотите, - это достойное решение, без необходимости перезапускать всю строительную эвристику.Это сложнее: добро пожаловать на повторное планирование и планирование в реальном времени (и эта документация ).Я работаю над примером с открытым исходным кодом для TSP и маршрутизации транспортных средств, который выполняет планирование в реальном времени.

Answer 3

Нет другой эвристики, потому что TSP всегда собирается найти ближайшую координату. По крайней мере, я не знаю алгоритм, который может вставить координату и знает ближайшую координату, но существует множество алгоритмов, чтобы найти хороший тур. Хорошей эвристикой является, например, алгоритм Christofides, он работает только в евклидовом пространстве, но дает вам гарантию того, что решение будет в пределах 3/2 от оптимального. Это не очень легко кодировать. Особенно алгоритм Эдмонда Блосса v предназначен для эксперта. Важность гарантии недостаточно высока, потому что, как бы вы объяснили, что в некоторых редких случаях ваш метод может дать бессмысленный смысл?