algorithm - 旅行推销员变体，规划旅行路线

Question

我正在寻找问题的名称和解决方案的算法。

我有一个连接节点图（A..Z），其中每个节点都连接到其他每个节点。我想绘制通过这些节点访问给定节点子集（A，D，K，W）的最短路径。路径可能包括不在子集中的节点，即 A->C->W->D->K 是可以接受的。在节点之间旅行的成本是非负的，但不一定是线性的。因此，从 A->B->C 的路径段可能比 A->C“更短”

我认为这是旅行销售员的变体。

Answer 1

我不知道这个问题是否有一个特殊的名称，但它很容易简化为选定节点的原始旅行商问题。

让所有节点的集合为V和选定的节点W。我将首先折叠不在 中的节点W以获得多重图（就像一个图，但在同一对节点之间可以有多个边）。这里的每条边可能是一个简单的边或来自 的边和节点序列V\W。要将其简化为常规图，我们只需选择每对节点可用的最短边，因为任何其他节点显然都不会成为答案的一部分。现在我们必须为简化图解决由此产生的旅行商问题，然后在原始图中重建相应的路径——我们已经在原始图中写下了简化图中每条边对应的实际路径。