來自多個集合的最短路徑

我必須在各個集合中找到最短路徑節點，我可以在每個集合中只使用一次節點。每個節點都通過距離連接到每個其他節點。在集合中的節點之間沒有連接的情況是有例外的。該路徑必須包含每個集合中的一個節點。來自多個集合的最短路徑

例如。

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

Ť他posibble路徑可能是：

A1 - > B1 - > C1 - > D1 - > Z1，或C1 - > Z2 - > A3 - > B1 - > D2

的每一個之間的距離節點（集合中的節點除外，沒有連接）可以從0到1.

來源

2013-04-22 Matej

你已經標記爲Dijkstra，所以你已經有一個想法？你到目前爲止編碼了什麼？ – 2013-04-22 15:08:54

聽起來像旅行推銷員問題。 – nhahtdh 2013-04-22 15:16:22

應該至少與tsp一樣硬，除非集合的數量受到節點數量「n」中最大對數函數的限制。想象一下，一些oracle會讓你知道在每個集合中選擇哪個節點。爲每個集合放下所有其他節點。你的問題已經成爲一個tsp實例。 NB：如果你原來的問題允許多次訪問同一組，它不會反映在上述茶匙問題，而它會讓你的搜索更加困難。 – collapsar 2013-04-22 16:47:28

這被稱爲廣義旅行推銷員問題。

從C. Noon & J.Bean, An Efficient Transformation of the Generalized Traveling Salesman Problem：

的廣義TSP問題（GTSP）是涉及選擇和序列的決定的問題的有用模型。問題的不對稱版本定義在有節點N的有向圖上，連接弧A和相應弧成本c的向量。節點被預先分成m個互斥和窮舉節點集。連接弧僅在屬於不同組的節點之間定義，即不存在組內弧。每個定義的弧具有相應的非負成本。 GTSP可以說是找到一個最小代價的m弧週期的問題，其中包括每個節點集恰好有一個節點。

本文解釋如何將您的問題轉換爲標準旅行商問題的案例。

來源

2013-04-22 18:24:49

來自多個集合的最短路徑

回答

相關問題