查找覆蓋所有節點的最小遊覽數

Question

我正面臨以下問題。

聲明：

1. 與它們的位置的多個節點被給予
2. 存在其中還提供它的位置的中間的中央節點。
3. 路由被定義爲從中心節點開始並訪問至少一個節點並再次在中心節點中結束的路徑。
4. 路由長度必須短於給定的數字。

如何覆蓋所有具有最少路由數的節點？

我將不勝感激任何幫助，可以提供解決這個或類似的和着名的問題，看起來像這樣，如果有什麼。

Answer 1

這個問題是NP-Hard從TSP簡單減少。

首先，定義了由這個問題

L = { (G,x,i) | graph G, maximum length per path x, minimal number of travels required i } 

這是很容易看到你的問題基本上是存在問題的最優化問題如上定義接受的語言。

TSP：
考慮到的(G,x)形式的TSP的情況下，我們需要確定是否有通過長度的所有點短/等於x進入循環路徑。

減少：
減少如下。給定一個TSP (G,x)的實例，爲您的問題提供實例(G,x,1)。

正確性：

• 如果通過長度x 以下的TSP的解決方案的所有點進入環道，還有一個解決您的 問題1個旅行所需。
• 如果在長度x或更小的問題中需要1次旅行，則這是TSP找到的路線。

我們提出的約簡是三次多項式。

由此我們可以得出結論，您的問題是NP-Hard，因爲TSP是NP-Hard。