algorithm - 来自多个集合的最短路径

Question

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

例如。

    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, or c1 -> z2 -> a3 -> b1 -> d2

每个节点之间的距离(集合中的节点除外，没有连接)可以是从0到1。

Answer 1

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

来自 C. Noon & J.Bean, An Efficient Transformation of the Generalized Traveling Salesman Problem :

The Generalized Traveling Salesman Problem (GTSP) is a useful model for problems involving decisions of selection and sequence. The asymmetric version of the problem is defined on a directed graph with nodes N, connecting arcs A and a vector of corresponding arc costs c. The nodes are pregrouped into m mutually exclusive and exhaustive nodesets. Connecting arcs are defined only between nodes belonging to different sets, that is, there are no intraset arcs. Each defined arc has a corresponding non-negative cost. The GTSP can be stated as the problem of finding a minimum cost m-arc cycle which includes exactly one node from each nodeset.

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