數據結構的圖要求經過指定一些邊，求最優解？
能幫忙指點一下應該怎麼去網上找資料嗎，比如和哪個問題類似，應該用什麼算法？這個問題是這樣的,貨運公司必須經過某一些城市,題目給出各個城市之間的花費,讓用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考慮暴力做法，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，在原問題的ij，在原問題的(i
演算法不懂，但是我知道一個通用的解決這類CSP問題的框架，你可以看一下：Optaplanner