問題描述

數據結構的圖要求經過指定一些邊，求最優解？能幫忙指點一下應該怎么去網上找資料嗎，比如和哪個問題類似，應該用什么算法？這個問題是這樣的,貨運公司必須經過某一些城市,題目給出各個城市之間的花費,讓用A*算法求最優解.

這是輸入:花費 360 Sydney 到 Wagga 花費 200 Sydney 到 Bathurst 花費 200 Dubbo 到 Grafton 花費 240 Dubbo 到 Bathurst 花費 480 Grafton 到 Wagga 花費 440 Grafton 到 Bathurst 花費 400 Wagga 到 Bathurst

要求必須經過: Grafton 到 Wagga Dubbo 到 Grafton Sydney 到 Wagga Sydney 到 Bathurst

結果是: Sydney 到 Bathurst Bathurst 到 Dubbo Dubbo 到 Grafton Grafton 到 Wagga Wagga 到 Sydney Sydney 到 Wagga總花費 1840

問題解答

這個是一類比較開放的問題，個人認為還是屬于圖論的一個部分，但是他不能用現有的最短路徑的相關算法比如SPFA，dijkstra算法來解決。曾今好像一個朋友問過我，是華為的一個什么比賽題目。這個題目用A*算法肯定可以，關鍵是在于如何去設計這個啟發式函數？相關知識你可以搜索1.經過指定的中間節點集的最短路徑算法2.啟發式搜索算法 A*

我覺得這題不太像是有多項式解法。（歡迎打臉）設點數n，邊數m，必須經過的邊數k，n<=500,m<=5000,k<=500。考慮暴力做法，O(n^3)預處理任意兩點之間的最短路（當然也可以n次堆優化dijkstra，但這不是瓶頸），O(k!)枚舉經過的k條邊的排列并計算答案，總復雜度O(k!*k)，顯然不能接受。注意到最優解并不一定需要枚舉全部排列才能得到，可以使用模擬退火等隨機化算法獲得較優解，使用合適的參數應該可以在大多數時候得到最優解。我想嘗試證明這個問題是NPC或NPH。將原問題的m條邊記為從from[i]至to[i]。新建一個k個點的圖，對k條指定邊中的第i條和第j條，如果to[i]可達到from[j]，則在新建的圖中從i向j連一條dis[to[i]][from[j]]的邊。于是原問題問題在多項式時間內規約成新問題：在k個點的圖中找出一條經過所有點的可重復路徑，使路徑長度最小。這個新問題看起來就很像NPC或NPH。（滑稽）但是我還沒有想好怎么把新問題規約回原問題。目前的想法是對新問題的每個點i，在原問題的i<<1到(i<<1)|1之間連一條+inf的邊，對新問題的每條邊i->j，在原問題的(i<<1)|1到j<<1之間連一條disi的邊，但是好像會有些問題,還沒有想清楚。

算法不懂，但是我知道一個通用的解決此類CSP問題的框架，你可以看一下：Optaplanner