1

我必须找到各种集合中节点之间的最短路径，我只能从每个集合中使用节点一次。每个节点都通过距离连接到其他所有节点。集合中的节点之间没有连接的例外情况。路径必须包含每个集合中的一个节点。

例如。

    Set A - [a1, a2, a3]
    Set B - [b1, b2]
    Set C - [c1]
    Set D - [d1, d2, d3]
    Set Z - [z1, z2, z3]

节点是 a1,a2,a3,b1,b2...

例如。节点a1与

b1,b2,c1,d1,d2,d3,z1,z2,z3

或节点c1与

a1,a2,a3,b1,b2,d1,d2,d3,z1,z2,z3

可能的路径可能是：

a1 -> b1 -> c1 -> d1 -> z1，或 c1 -> z2 -> a3 -> b1 -> d2

每个节点之间的距离（除了集合中的节点，没有连接）可以从 0 到 1。

4

1 回答 1

1

这被称为广义旅行商问题。

来自C. Noon 和 J.Bean，广义旅行推销员问题的有效转换：

广义旅行商问题(GTSP) 是一个有用的模型，用于解决涉及选择和顺序决策的问题。该问题的非对称版本是在一个有向图上定义的，该有向图具有节点 N、连接弧 A 和相应弧成本 c 的向量。节点被预先分组为 m 个互斥且详尽的节点集。连接弧只在属于不同集合的节点之间定义，即没有集合内弧。每个定义的弧都有相应的非负成本。GTSP 可以说是找到一个最小成本 m-arc 循环的问题，该循环恰好包括每个节点集中的一个节点。

本文解释了如何将您的问题转化为标准旅行商问题的案例。

于 2013-04-22T18:24:49.123 回答