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 中的一系列边和节点。要将其简化为常规图，我们只需为每对节点选择最短的边，因为任何其他边显然都不是答案的一部分。现在我们要为缩减图解决由此产生的旅行商问题，然后在原图中重建相应的路径——我们已经记下了缩减图中每条边对应的原图中的实际路径。