java - 数据结构的图要求经过指定一些边，求最优解？

Question

数据结构的图要求经过指定一些边，求最优解？
能帮忙指点一下应该怎么去网上找资料吗，比如和哪个问题类似，应该用什么算法？这个问题是这样的,货运公司必须经过某一些城市,题目给出各个城市之间的花费,让用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

Answer 1

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

Answer 2

我覺得這題不太像是有多項式解法。 （歡迎打臉）
設點數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的邊，但是好像會有些問題,還沒有想清楚。

Answer 3

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