如何訂購圖的節點，以便兩個相鄰節點之間的距離最小

Question

我想知道這個問題在圖論中是否已​​知： 我有一個沒有權重的無向圖G =（V，A），我想將此圖的節點放置在一個字符串中，以便將有向節點放置得儘可能靠近。因此，例如：

鑑於這種圖表：

a,b;a,d;b,e;c,f;c,h;f,h;e,g;e,h. 

其中弧被 ';' 分隔

我需要找到這個解決方案： a，b，d，e，g，h，c，f = 2 其中2是串a，b，d，e，g， h，c，f在兩個有向節點之間。

形式上：

• 令d（V，U）根據該圖是兩個節點之間的距離。
• 查找v階 _1，，V _2，，V _N，，使得最大{d（V _I，，V _{+ 1，}）}是最小

Answer 1

好吧，看來您正面臨Hamiltonian Path Problem的變化。

在這個問題中，給定一個圖 - 你正在尋找一條通過所有頂點而不重複任何節點兩次的路徑。

請注意，哈密爾頓路徑是您的問題的完美解決方案，因此如果您的問題可以得到有效解決 - 哈密頓路徑問題也是如此。

不幸的是，沒有已知的哈密爾頓路徑問題的多項式解決方案，問題是NP-Complete（所以一般的看法是這樣的（高效的）解決方案不存在）。

一個蠻力解決方案將是O（n！） - 檢查所有可能的排列，並選擇最佳的一個。這可以使用branch and bound techniques進行優化。