java - 數(shù)據(jù)結(jié)構(gòu)的圖要求經(jīng)過指定一些邊,求最優(yōu)解?
問題描述
數(shù)據(jù)結(jié)構(gòu)的圖要求經(jīng)過指定一些邊,求最優(yōu)解?能幫忙指點(diǎn)一下應(yīng)該怎么去網(wǎng)上找資料嗎,比如和哪個問題類似,應(yīng)該用什么算法?這個問題是這樣的,貨運(yùn)公司必須經(jīng)過某一些城市,題目給出各個城市之間的花費(fèi),讓用A*算法求最優(yōu)解.
這是輸入:花費(fèi) 360 Sydney 到 Wagga 花費(fèi) 200 Sydney 到 Bathurst 花費(fèi) 200 Dubbo 到 Grafton 花費(fèi) 240 Dubbo 到 Bathurst 花費(fèi) 480 Grafton 到 Wagga 花費(fèi) 440 Grafton 到 Bathurst 花費(fèi) 400 Wagga 到 Bathurst
要求必須經(jīng)過: Grafton 到 Wagga Dubbo 到 Grafton Sydney 到 Wagga Sydney 到 Bathurst
結(jié)果是: Sydney 到 Bathurst Bathurst 到 Dubbo Dubbo 到 Grafton Grafton 到 Wagga Wagga 到 Sydney Sydney 到 Wagga總花費(fèi) 1840
問題解答
回答1:這個是一類比較開放的問題,個人認(rèn)為還是屬于圖論的一個部分,但是他不能用現(xiàn)有的最短路徑的相關(guān)算法比如SPFA,dijkstra算法來解決。曾今好像一個朋友問過我,是華為的一個什么比賽題目。這個題目用A*算法肯定可以,關(guān)鍵是在于如何去設(shè)計(jì)這個啟發(fā)式函數(shù)?相關(guān)知識你可以搜索1.經(jīng)過指定的中間節(jié)點(diǎn)集的最短路徑算法2.啟發(fā)式搜索算法 A*
回答2:我覺得這題不太像是有多項(xiàng)式解法。(歡迎打臉)設(shè)點(diǎn)數(shù)n,邊數(shù)m,必須經(jīng)過的邊數(shù)k,n<=500,m<=5000,k<=500??紤]暴力做法,O(n^3)預(yù)處理任意兩點(diǎn)之間的最短路(當(dāng)然也可以n次堆優(yōu)化dijkstra,但這不是瓶頸),O(k!)枚舉經(jīng)過的k條邊的排列并計(jì)算答案,總復(fù)雜度O(k!*k),顯然不能接受。注意到最優(yōu)解并不一定需要枚舉全部排列才能得到,可以使用模擬退火等隨機(jī)化算法獲得較優(yōu)解,使用合適的參數(shù)應(yīng)該可以在大多數(shù)時候得到最優(yōu)解。我想嘗試證明這個問題是NPC或NPH。將原問題的m條邊記為從from[i]至to[i]。新建一個k個點(diǎn)的圖,對k條指定邊中的第i條和第j條,如果to[i]可達(dá)到from[j],則在新建的圖中從i向j連一條dis[to[i]][from[j]]的邊。于是原問題問題在多項(xiàng)式時間內(nèi)規(guī)約成新問題:在k個點(diǎn)的圖中找出一條經(jīng)過所有點(diǎn)的可重復(fù)路徑,使路徑長度最小。這個新問題看起來就很像NPC或NPH。(滑稽)但是我還沒有想好怎么把新問題規(guī)約回原問題。目前的想法是對新問題的每個點(diǎn)i,在原問題的i<<1到(i<<1)|1之間連一條+inf的邊,對新問題的每條邊i->j,在原問題的(i<<1)|1到j(luò)<<1之間連一條disi的邊,但是好像會有些問題,還沒有想清楚。
回答3:算法不懂,但是我知道一個通用的解決此類CSP問題的框架,你可以看一下:Optaplanner
