Проверка маршрута / проблема китайского почтальона через TSP

Question

Я пытаюсь решить задачу проверки маршрута / китайского почтальона через TSP, решая линейный график L (G) графика маршрута G.

1. График G описывается списком линий с координатами начальной / конечной точки.
2. Линейный график L (G) описывается как список центральных точек линий.
3. Решить L (G) через TSP.
4. Рассчитать порядок строк в G из # 3.

Как видно из прикрепленного изображения , существует множество одинаково дорогих решений для L (G). Однако при преобразовании решения обратно в G некоторые из этих решений создают перекрывающиеся линии / переходы, которые увеличивают стоимость.

Как я могу убедиться, что всегда найду самое дешевое решение G, когда решаю для L (G)? Есть ли ошибка в моей логике / исполнении?

Answer 1

Если в вашем графе не более 2 узлов с нечетной степенью, скажем, s и t, как в вашем примере, то вы, безусловно, хотите, чтобы путешествие почтальона начиналось с s и заканчивалось в t (или наоборот). В этом случае существует эйлерова тропа, которая проходит каждый край ровно один раз, что, конечно, должно быть минимальным китайским почтальоном. Таким образом, вы можете использовать любой алгоритм для построения эйлерова траектории от s до t, и это будет оптимальным решением.

Когда еще много узлов имеют нечетную степень, я не уверен, что подход с использованием линейного графа является правильным. Но позвольте мне заметить, что использование алгоритма TSP для решения проблемы китайского почтальона - это все равно, что пытаться ударить комара из пушки: TSP является NP-сложным, в то время как китайский почтальон, как известно, допускает алгоритмы полиномиального времени.