資源描述：
《深度搜索法求解不定期最短路徑問(wèn)題》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、深度搜索法求解不定期最短路徑問(wèn)題問(wèn)題的提出所謂不定期最短路徑問(wèn)題是指如何從不同的節(jié)點(diǎn)處通過(guò)有限次到達(dá)終點(diǎn)，求解到達(dá)的最短路徑。此類(lèi)問(wèn)題形式上屬于網(wǎng)絡(luò)和圖，但是我們完全可以通過(guò)動(dòng)態(tài)規(guī)劃方法來(lái)求出最優(yōu)解。求解方法的弊端通常求解此類(lèi)問(wèn)題的方法是運(yùn)籌學(xué)中的函數(shù)迭代法和策略迭代法。這兩種辦法都不同程度地存在著浪費(fèi)計(jì)算的問(wèn)題：有些節(jié)點(diǎn)顯然不可能是最優(yōu)路徑，但是為了求解的完整性，我們必須求出許多冗余數(shù)據(jù)。而且隨著節(jié)點(diǎn)數(shù)的增多，計(jì)算量會(huì)以平方級(jí)數(shù)大大增加。新的求解思路我們發(fā)現(xiàn)，人來(lái)求解此類(lèi)問(wèn)題并不是從一個(gè)一個(gè)節(jié)點(diǎn)地遍歷計(jì)算每一個(gè)結(jié)果，最后來(lái)比較的，而是先有選擇地找到一些感覺(jué)上比較好的路徑，在
2、計(jì)算一些簡(jiǎn)單的數(shù)，最后比較的個(gè)數(shù)就少多了。而且人經(jīng)常不自覺(jué)地會(huì)順著一些“捷徑”來(lái)找最短路徑，往往幾個(gè)節(jié)點(diǎn)的最短路徑都在一條路上。所以通過(guò)模擬人類(lèi)求解此類(lèi)問(wèn)題的方式，我采用了一個(gè)樹(shù)形結(jié)構(gòu)來(lái)求解最終值，這種辦法就形象地被稱(chēng)為深度搜索法。它可以使用計(jì)算機(jī)來(lái)求解，而且通過(guò)層層篩選后，實(shí)際的計(jì)算量少得多。當(dāng)節(jié)點(diǎn)數(shù)增加的時(shí)候，這種辦法的優(yōu)越性就體現(xiàn)出來(lái)了，他的計(jì)算量增長(zhǎng)是線(xiàn)性遞增的。下面我一個(gè)例子來(lái)闡述這個(gè)方法。例題[選自《運(yùn)籌學(xué)基礎(chǔ)》（張瑩編著）第221頁(yè)]設(shè)總共有N個(gè)城市，是任兩城城i與城j之間的距離，有。求：各城市到第5個(gè)城市之間的最短路徑和最短距離(不限定步數(shù))。圖圖1路線(xiàn)圖例題
3、分析求解這道題書(shū)上用了兩種思路——函數(shù)迭代法和策略迭代法。7但是求解的出發(fā)點(diǎn)都是把這個(gè)系統(tǒng)模型化，盡量算出可能的解，最后經(jīng)過(guò)比較，得出最小路徑。我們可以清楚地看到，包含了這么少信息的一道題，書(shū)上用了兩頁(yè)的篇幅來(lái)闡述解法，而且其中只羅列出了每一步的最優(yōu)結(jié)果；而我們其實(shí)自己來(lái)做的話(huà)，可能通過(guò)心算就可以解決了，這就是為什么我看到這個(gè)解法有些干著急的原因。新的求解思路：為了更清楚地闡述深度搜索法的求解步驟，我想先讓大家跟我一起了解我是如何想出這個(gè)辦法的。一般以人的思路來(lái)說(shuō)，我們首先先找到每個(gè)節(jié)點(diǎn)到5節(jié)點(diǎn)的步數(shù)；其次從第1點(diǎn)開(kāi)始，我們看到除了直接到5節(jié)點(diǎn)外，其他的方法的步長(zhǎng)都不是最優(yōu)的
4、。當(dāng)然我們看到2點(diǎn)的時(shí)候，總是自然而然地先找最小步長(zhǎng)的出路（2-）3），在一步步地沿著最小步長(zhǎng)的路找到5點(diǎn)，由于步數(shù)最多有4步，所以很容易地找到最優(yōu)的解，于是我們按照這種方法就很快地得出最優(yōu)解：節(jié)點(diǎn)名稱(chēng)路徑方式->->->->->->->路徑長(zhǎng)度2543總結(jié)上面的方法，我們發(fā)現(xiàn)，這種思路與先前的思路截然不同的地方是：這種方法是面向節(jié)點(diǎn)的，而不是面向步長(zhǎng)的，由于節(jié)點(diǎn)的有限性，決定了這類(lèi)方法的步數(shù)的有限性，在求解中，我們可以從一個(gè)節(jié)點(diǎn)走向另一個(gè)節(jié)點(diǎn)，當(dāng)發(fā)現(xiàn)不行的時(shí)候再退回來(lái)，選擇其他節(jié)點(diǎn)，這種解題的思路有些像計(jì)算機(jī)算法里的樹(shù)形結(jié)構(gòu)，樹(shù)的深度只有有限層，到了葉子后再退回來(lái)走其他分支
5、，最后找到最優(yōu)的路徑。所以我將這種算法叫做深度搜索法。具體求解方法：?第一步，找出圖中的起始點(diǎn)和目標(biāo)點(diǎn)。本例中起始點(diǎn)是，，，；目標(biāo)點(diǎn)是。?第二步，找出起始點(diǎn)到目標(biāo)點(diǎn)最短距離，作為參考點(diǎn)。選擇這個(gè)參考點(diǎn)的意義在于，不管步長(zhǎng)如何，我們總是直接或間接地通過(guò)起始節(jié)點(diǎn)（，，，）中的一個(gè)到達(dá)目標(biāo)點(diǎn)，所有起始點(diǎn)到目標(biāo)點(diǎn)的最短步長(zhǎng)肯定是起始點(diǎn)到目標(biāo)點(diǎn)的最短直接距離，我把這個(gè)點(diǎn)稱(chēng)為參考點(diǎn)。本例中，直接距離分別是的距離是2；的距離是7；的距離是5；的距離是3。所以取點(diǎn)為參考點(diǎn)。?第三步，建立初始約束條件，p0(k),k=(1,N)，約束條件是個(gè)各自節(jié)點(diǎn)到目標(biāo)點(diǎn)的直接距離，最優(yōu)解不可能超過(guò)直接距離
6、。本例中的約束條件是?第四步，迭代約束條件，由于環(huán)狀結(jié)構(gòu)不可能是最優(yōu)的解，所以迭代的步數(shù)是N-1。7?第五步，作圖，畫(huà)出樹(shù)形結(jié)構(gòu)圖的第一層，目標(biāo)點(diǎn)為樹(shù)的根結(jié)點(diǎn)，除了起始點(diǎn)和直接步長(zhǎng)最長(zhǎng)的節(jié)點(diǎn)外，把其他節(jié)點(diǎn)作為樹(shù)的第一層葉子（如圖2）。本例中，第一層葉子為節(jié)點(diǎn)1，3，4。約束條件：圖2第一層搜索?第六步，分別以第一層節(jié)點(diǎn)為子根，繼續(xù)向下搜索，不滿(mǎn)足約束條件的葉子就去掉。如果搜索到的路徑比約束條件好，就把該路徑定義為下一級(jí)節(jié)點(diǎn)的約束條件，前面到過(guò)的節(jié)點(diǎn)就不要在下層的葉子中出現(xiàn)了。停止搜索的條件：路徑長(zhǎng)度比所有的約束長(zhǎng)度都大。本例中，->->，->->，->->，->->的步長(zhǎng)超過(guò)
7、了所有的約束步長(zhǎng)，刪除該路徑，并且的約束條件改為，改為。約束條件：圖3第二層搜索第七步，重復(fù)執(zhí)行第六步，停止的條件：1.所有的葉子都不可往下搜索；2.已經(jīng)搜索到了第N-1層。7約束條件：圖4第三層搜索約束條件：圖5第四層搜索第八步，刪除所有的無(wú)用節(jié)點(diǎn)，從中尋找最佳的路徑。根據(jù)約束條件找到最短路徑的實(shí)現(xiàn)方法。本例中，最佳的路徑被選為下表所示：節(jié)點(diǎn)名稱(chēng)路徑方式->->->->->->->路徑長(zhǎng)度2543圖6搜索結(jié)果7結(jié)果分析按照深度搜索的方法，我們可以很快的得到所需要的解，與先前按照迭代法得出的結(jié)論完全一致
