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

Question

Я ищу советы или ресурсы для решения проблемы, аналогичной TSP, но где:

• вилки разрешены, т.е.продавец может дублировать себя в каждом городе;
• начальные и конечные местоположения не имеют значения и могут отличаться.

Это означает, что для этих городов (где x - городаи визуальное пространство между каждым x пропорционально расстоянию между городами):

x

  x x

x 

Обычное решение TSP может быть:

x
|\
| x-x
|  /
x-/ 

Но я бы хотел такого рода решение, что лучше по новым правилам:

x
 \ 
  x-x
 /
x 

Есть ли у этой проблемы имя и есть ли публикации об оптимизированном решении?

Answer 1

Вы описываете проблему минимального связующего дерева (MST).Тебе повезло!Потому что, хотя TSP является NP-сложным, MST является одной из самых простых задач комбинаторной оптимизации, которую можно решить в вычислительном отношении.Это может быть решено за O (m log n) за счет простой реализации алгоритма Прима или Крускала (и оба эти алгоритма также довольно легко кодировать).Существуют также другие алгоритмы и другие структуры данных, которые могут сделать сложность еще ниже, но если у вас есть 30 узлов, любой из этих алгоритмов решит ее за доли секунды.

Answer 2

Я не уверен, что цель здесь, но это звучит как проблема для алгоритма поиска A *.