穿越所有城市但允许分岔路口（可以自己分叉的旅行商）
Pass through all cities but allowing forks (traveling salesman who can split himself)
我正在寻找建议或资源来解决与 TSP 类似的问题，但是：
- 允许分叉，即。销售员可以在每个城市复制自己；
- 开始和结束位置无关紧要，可以不同。
这意味着，给定这些城市（其中 x 是城市，每个 x 之间的视觉 space 与城市之间的距离成正比）：
x
x x
x
常规 TSP 解决方案可以是：
x
|\
| x-x
| /
x-/
但我想要这样的解决方案，根据新规则更好：
x
\
x-x
/
x
这个问题有名字吗？是否有一些关于优化解决方案的出版物？
我不确定这里的目标是什么，但这听起来像是 A* 搜索算法的问题。
您描述的是 minimum spanning tree (MST) 问题。你真是幸运！因为虽然 TSP 是 NP-hard，但 MST 是计算上最容易解决的组合优化问题之一。它可以通过直接实施 Prim 或 Kruskal 算法（而且，这两种算法也很容易编写代码）在 O(m log n) 时间内解决。还有其他算法和其他数据结构可以使复杂度更低，但如果你有 30 个节点，这些算法中的任何一个都将在几分之一秒内解决它。
我正在寻找建议或资源来解决与 TSP 类似的问题，但是：
- 允许分叉，即。销售员可以在每个城市复制自己；
- 开始和结束位置无关紧要，可以不同。
这意味着，给定这些城市（其中 x 是城市，每个 x 之间的视觉 space 与城市之间的距离成正比）：
x
x x
x
常规 TSP 解决方案可以是：
x
|\
| x-x
| /
x-/
但我想要这样的解决方案，根据新规则更好：
x
\
x-x
/
x
这个问题有名字吗？是否有一些关于优化解决方案的出版物？
我不确定这里的目标是什么，但这听起来像是 A* 搜索算法的问题。
您描述的是 minimum spanning tree (MST) 问题。你真是幸运！因为虽然 TSP 是 NP-hard，但 MST 是计算上最容易解决的组合优化问题之一。它可以通过直接实施 Prim 或 Kruskal 算法（而且，这两种算法也很容易编写代码）在 O(m log n) 时间内解决。还有其他算法和其他数据结构可以使复杂度更低，但如果你有 30 个节点，这些算法中的任何一个都将在几分之一秒内解决它。