問題描述

數(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

問題解答

這個是一類比較開放的問題，個人認(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*

我覺得這題不太像是有多項(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的邊，但是好像會有些問題,還沒有想清楚。

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