国产成人精品久久免费动漫-国产成人精品天堂-国产成人精品区在线观看-国产成人精品日本-a级毛片无码免费真人-a级毛片毛片免费观看久潮喷

您的位置:首頁技術(shù)文章
文章詳情頁

java - 數(shù)據(jù)結(jié)構(gòu)的圖要求經(jīng)過指定一些邊,求最優(yōu)解?

瀏覽:87日期:2023-12-24 18:43:56

問題描述

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

標(biāo)簽: java
主站蜘蛛池模板: 99九九国产精品免费视频 | 一级毛片观看 | 毛片在线免费播放 | 欧美人与zoxxxx另类9 | 亚洲国产老鸭窝一区二区三区 | 亚洲美女aⅴ久久久91 | 成 人 在 线 免费 8888 www | 国产日韩一区二区三区在线播放 | 国产特级全黄一级毛片不卡 | 一本色道久久88加勒比—综合 | 国产a级特黄的片子视频 | 欧美91精品久久久久网免费 | 午夜欧美在线 | 成人全黄三级视频在线观看 | 免费视频久久 | 中文字幕亚洲不卡在线亚瑟 | 香港经典a毛片免费观看爽爽影院 | 新版天堂资源中文在线 | 久久久久久综合七次郎 | 久久精品视频6 | 日韩精品久久一区二区三区 | 日本欧美久久久久免费播放网 | 91精品久久久久久久久网影视 | 美国免费高清一级毛片 | 日本一级特黄啪啪片 | 久久99综合国产精品亚洲首页 | 99视频国产在线 | 国产欧美精品午夜在线播放 | 中文字幕或区 | 一级啊片| 日本韩国一级 | 亚洲欧美日本在线观看 | 综合久| 日本欧美亚洲 | 久久草在线视频播放 | 午夜无遮挡怕怕怕免费视频 | 国产a∨一区二区三区香蕉小说 | 亚洲国产精品a在线 | 成人午夜免费观看 | 欧美国产成人一区二区三区 | 真人一级一级特黄高清毛片 |