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