国产成人精品久久免费动漫-国产成人精品天堂-国产成人精品区在线观看-国产成人精品日本-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
主站蜘蛛池模板: 亚洲厕拍| 欧美视频免费一区二区三区 | 亚洲国产三级 | 国产精品热久久毛片 | 免费看一区二区三区 | 久久精品国产欧美 | 亚洲成a人片在线网站 | 日韩精品麻豆 | 国产黄三级三·级三级 | 最新色网址| 成人午夜大片免费7777 | 欧美色视频日本片高清在线观看 | 国产成人微拍精品 | 一本色道久久88亚洲精品综合 | 日韩美女一级视频 | 中国一级特黄剌激爽毛片 | 日韩一区二区中文字幕 | 99这里只有精品66视频 | 中文字幕一区二区在线观看 | 三级网站免费 | 在线aaa| 日韩精品一区二区三区乱码 | 久综合| 日本在线毛片视频免费看 | 国产成人免费高清视频 | 国产第一区二区三区在线观看 | 国产成人综合网在线观看 | 色老头老太做爰视频在线观看 | 扒开两腿猛进入爽爽视频 | 成人免费在线视频 | 精品丝袜国产自在线拍亚洲 | 欧美视频精品一区二区三区 | 欧美一级欧美一级在线播放 | 亚洲一区二区成人 | 成人在线中文字幕 | 中文字幕一级毛片 | 亚洲国产日韩欧美一区二区三区 | 男的操美女 | 手机看片久久青草福利盒子 | 一级毛片免费观看 | 国产成人18黄网站免费 |