城市軌道交通客流誘導(dǎo)系統(tǒng)理論基礎(chǔ)

1、城市軌道交通客流誘導(dǎo)系統(tǒng)理論基礎(chǔ)一、城市軌道交通客流誘導(dǎo)系統(tǒng)的研究背景隨著全球經(jīng)濟(jì)的騰飛、社會(huì)的進(jìn)步以及城市化進(jìn)程的加快，交通運(yùn)輸在人們 的日常生活中起著越來越重要的作用，對(duì)交通的需求日益增長，交通運(yùn)輸已然成 為了社會(huì)經(jīng)濟(jì)生活的重要組成部分。為了適應(yīng)城市發(fā)展的要求，目前，主要大城 市都在加快軌道交通網(wǎng)絡(luò)的建設(shè)。隨著軌道交通網(wǎng)絡(luò)的日趨完善，未來的軌道交 通網(wǎng)絡(luò)將會(huì)出現(xiàn)一些前所未有的新的特點(diǎn)，其中主要表現(xiàn)在路網(wǎng)的結(jié)構(gòu)和規(guī)模將 更加復(fù)雜，客流需求將有大幅度增長。由于軌道交通網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜，線路間相互 連通，這就使得出行者出行時(shí)將會(huì)有更加多樣的路徑選擇。隨著軌道交通系統(tǒng)規(guī) 模的不斷擴(kuò)大，沿線小區(qū)的不斷開

2、發(fā)，越來越多的出行者出行時(shí)將趨向于選擇軌 道交通。這樣，軌道交通將會(huì)涌現(xiàn)大量的客流，對(duì)人們?nèi)粘３鲂泻蛙壍澜煌ㄖ锌?流的誘導(dǎo)逐漸成為大家關(guān)注的焦點(diǎn)，其需求的迫切程度也越發(fā)明顯。所以急需開 發(fā)關(guān)于城市軌道交通客流誘導(dǎo)的系統(tǒng)。在軌道交通路網(wǎng)結(jié)構(gòu)相對(duì)簡單的情況下，由于考慮時(shí)間最短或距離最短因素 得到的有效路徑比較少，也就是說在每一個(gè)0D對(duì)間，出行者路徑選擇比較單一， 客流誘導(dǎo)系統(tǒng)的作用并不明顯。隨著路網(wǎng)規(guī)模的不斷擴(kuò)大，人們出行時(shí)的路徑選 擇不再單一，而是逐漸趨于多樣化，在這種情況下，如果沒有合適的客流誘導(dǎo)系 統(tǒng)對(duì)出行者的路徑選擇進(jìn)行誘導(dǎo)，將會(huì)導(dǎo)致過多的客流聚集在0D間旅行時(shí)間最 短或者距離最短的路徑上

3、，容易造成客流擁擠、換乘擁堵等等很多問題?；谏?述考慮，本文提出城市軌道交通客流誘導(dǎo)系統(tǒng)的理論基礎(chǔ)。二、城市軌道交通客流誘導(dǎo)系統(tǒng)的研究意義城市軌道交通客流誘導(dǎo)根據(jù)軌道交通路網(wǎng)結(jié)構(gòu)、站點(diǎn)和斷面的客流信息等， 利用改進(jìn)的最優(yōu)路徑選擇算法和交通分配模型，對(duì)軌道交通的客流進(jìn)行統(tǒng)計(jì)分析 與誘導(dǎo)?？土髡T導(dǎo)系統(tǒng)能夠根據(jù)出行者的個(gè)人情況和軌道中實(shí)時(shí)的客流分布信息， 為出行者提供可供選擇的出行路徑，有效地避免軌道中的客流聚集，有助于提高 軌道交通的利用率，也能夠緩解道路交通的壓力。三、軌道交通出行最優(yōu)路徑選擇模型的研究最短路徑是運(yùn)籌學(xué)、圖論等領(lǐng)域中的概念。所謂最短路徑，即由起點(diǎn)至終點(diǎn) 間的路徑代價(jià)最小的路徑。

4、它既要求能求得一條總路徑代價(jià)最小的路徑，又要求1 / 9采用具有較小的時(shí)空復(fù)雜度的求解算法。經(jīng)過多年的研究，在圖論的基礎(chǔ)上結(jié)合 數(shù)據(jù)結(jié)構(gòu)和算法，大量的在使用范圍與時(shí)空復(fù)雜度上擁有各自優(yōu)勢(shì)的最短路徑求 解算法被提出。最優(yōu)路徑問題，通俗的說，即求解道路中兩點(diǎn)間的最短路徑的問題。最優(yōu)路 徑算法因?yàn)榫哂鞋F(xiàn)實(shí)背景，所以不像傳統(tǒng)的最短路徑算法那么簡單，它需要考慮 實(shí)際的影響因素和約束條件，但它們的本質(zhì)是一樣的。在圖論中，最短路徑指的 是圖中某一結(jié)點(diǎn)到其余任一結(jié)點(diǎn)的總權(quán)值最小的連接初始結(jié)點(diǎn)和目標(biāo)結(jié)點(diǎn)的邊 的序列；而與此對(duì)應(yīng)的，在交通路網(wǎng)中，最短路徑指的是一個(gè)站點(diǎn)到另一站點(diǎn)間 總路徑阻抗最小的一系列依次連接的

5、路段的序列。最優(yōu)路徑選擇算法一般也叫做最短路徑算法，指的是尋找圖中給定結(jié)點(diǎn)到其 余任意一個(gè)結(jié)點(diǎn)的一條最短路徑的算法。本文主要介紹3種常用的最優(yōu)路徑選擇 算法：Dijkstra算法、Floyd算法和A*算法。Dijkstra算法Dijkstra算法是在1959年由荷蘭的一位數(shù)學(xué)家E.W.Dijkstra提出的，用來尋找 單源點(diǎn)的最短路徑的算法，適用于圖中所有的邊的權(quán)值均為非負(fù)的情況，并且最 短路徑是依據(jù)路徑的長度非遞減的順序搜索得到的。Dijkstra算法是迄今為止研 究最深入、運(yùn)用最普遍的尋找最短路徑的算法，用于求圖中一個(gè)給定結(jié)點(diǎn)到其余 任意結(jié)點(diǎn)間的最短路徑。Dijkstra算法的基本思想：給

6、定賦權(quán)圖G = (V,E)，其中V表示結(jié)點(diǎn)的集合，E 表示弧的集合。初始時(shí)，設(shè)D為輔助向量，其各分量Di的含義是當(dāng)前得到的由 起點(diǎn)v至各終點(diǎn)，間的最短路徑的長度。其初態(tài)可以設(shè)置為：如果v和 連通， 那么Di的值就為弧上的權(quán)值；否則，將Di的值設(shè)置為。很明顯，長度為的路徑即為以v為起點(diǎn)，且具有最小長度的路徑，表示為 。假定S為已計(jì)算得到的最短路徑所有終點(diǎn)的集合，那么能夠得出的結(jié)論是： 下一條終點(diǎn)為x的最短路徑可能為弧(v,x)，或僅途經(jīng)S中結(jié)點(diǎn)并且最終到達(dá)x的 路徑。可以用反證法來證明。假設(shè)該路徑上的某一結(jié)點(diǎn)未包含于S中，那么說明 存在這樣的一條路徑，其終點(diǎn)不在5中但長度小于該路徑的長度。然而，

7、這種假設(shè)是不可能的。因?yàn)樽疃搪窂降乃阉魇且罁?jù)路徑的長度非遞減的順序?qū)崿F(xiàn)的， 所以，比該路徑的長度小的路徑已全部求出，其終點(diǎn)一定包含于S中，由此得出， 假設(shè)不成立。通常情況下，搜索的下一條為長度次短路徑，其長度為-2 / 9其中，Di的值可能為弧 的權(quán)值，也可能為Dk()與弧的權(quán)值之和。Floyd算法Floyd算法是Floyd在1962年提出的，它是用來搜索圖中各個(gè)結(jié)點(diǎn)對(duì)間的最短路徑的算法。Floyd算法能夠一次性搜索得到圖中任意結(jié)點(diǎn)對(duì)間的最短 路徑及其長度。Floyd算法的基本思想：假設(shè)一個(gè)nxn的方陣 ，它的對(duì)角線元素均為0， 其余元素為由 到 的路徑的長度(其中 為運(yùn)算步驟)。初始時(shí)，任意

8、兩結(jié)點(diǎn)間的弧的權(quán)值作為其路徑長度，表示為；然后在每次計(jì)算時(shí)，逐漸在原路徑中依次添加其它結(jié)點(diǎn)作為中間結(jié)點(diǎn)(添加結(jié)點(diǎn)時(shí)可依結(jié)點(diǎn)在 圖中的序號(hào)依次加入)。若在第k步將 添加到路徑中作為中間結(jié)點(diǎn)，那么需要 計(jì)算是否成立，若成立，就將新的路徑長度作為 的值，反之，路徑長度仍為原值，即：,k=1,2, n按照上述步驟類推，n次計(jì)算和比較后，得到的結(jié)果即為從到的最短路 徑，其中，所求得的長度為 的值。由上述公式可得， 為圖的鄰接矩陣， 為 中間結(jié)點(diǎn)序號(hào)不超過k的、由 到 的最短路徑的長度。A*算法啟發(fā)式搜索(Heuristic Search)算法是指在搜索過程中，根據(jù)一個(gè)估價(jià)函數(shù)來 搜索下一個(gè)結(jié)點(diǎn)。其中最常

9、用的是A*算法。A*算法最初由Hart、Nilsson、Raphael等人提出。它的獨(dú)特之處表現(xiàn)在，當(dāng) 對(duì)下一個(gè)結(jié)點(diǎn)進(jìn)行檢查時(shí)，會(huì)根據(jù)已經(jīng)獲得的信息，估算出當(dāng)前點(diǎn)到終點(diǎn)的長度， 以此來判斷該檢查的結(jié)點(diǎn)是否有可能處在最優(yōu)路徑上。它一般用已經(jīng)付出的代價(jià) 與即將付出的代價(jià)之和作為其評(píng)價(jià)的標(biāo)準(zhǔn)，按照這種計(jì)算方法，可以大大節(jié)約搜 索時(shí)間，提高搜索效率，因?yàn)樗偸莾?yōu)先搜索最有可能處于最優(yōu)路徑上的結(jié)點(diǎn)。 A*算法以Dijkstra算法為基礎(chǔ)，而且也是啟發(fā)式搜索中最重要、最常用的算法之 一。A*算法利用估價(jià)函數(shù)，搜索最有可能處于最優(yōu)路徑上的結(jié)點(diǎn)，算法中引進(jìn)了 結(jié)點(diǎn)j的估價(jià)函數(shù)。其定義如下：其中， 表示由起始點(diǎn)

10、至j的實(shí)際費(fèi)用值，表示由至終止點(diǎn)的最小費(fèi)3 / 9用估量值。當(dāng)時(shí)，A*算法退化為Dijkstra算法。A*算法適用于對(duì)路網(wǎng)的最佳優(yōu)先搜索，它的前提條件是選擇的估價(jià)函數(shù)必須滿足某一特性，并且最優(yōu)路 徑是存在的，那么A*算法就一定可以搜索到此最佳路徑。A*算法的估價(jià)函數(shù)隨著問題的不同而不盡相同，使用者可以根據(jù)實(shí)際的情況 來選擇的類型，在不大于j到終點(diǎn)的最小花費(fèi)的情況下，就必然會(huì)有最優(yōu)解，這時(shí)A*算法就可以求得最短路徑。四、軌道交通客流分配模型的研究交通分配，即根據(jù)某種特定的方法將道路網(wǎng)中各0D間的交通量分配到各線 路上。其本質(zhì)是模擬出行者選擇路徑的行為，以了解各OD間交通量的動(dòng)態(tài)，從 而得出各路段

11、上的交通量。進(jìn)行交通分配理論研究時(shí)，一般的做法是把城市系統(tǒng) 抽象為網(wǎng)絡(luò)。如果討論的對(duì)象為一個(gè)城市的話，那么所抽象的網(wǎng)絡(luò)的結(jié)點(diǎn)就對(duì)應(yīng) 著現(xiàn)實(shí)中的道路交叉點(diǎn)，連接兩個(gè)結(jié)點(diǎn)的邊對(duì)應(yīng)著現(xiàn)實(shí)中的交叉點(diǎn)間的路段；而 如果討論的對(duì)象為一個(gè)區(qū)域的話，那么所抽象的網(wǎng)絡(luò)的結(jié)點(diǎn)就對(duì)應(yīng)著區(qū)域中的一 個(gè)城市，連接兩個(gè)結(jié)點(diǎn)的邊對(duì)應(yīng)著現(xiàn)實(shí)中的城市間的道路。簡而言之，交通分配的問題實(shí)際上就是在起訖點(diǎn)間的交通量、道路交通網(wǎng)絡(luò) 圖、路徑選擇時(shí)的綜合路徑阻抗函數(shù)已知的前提下，將路網(wǎng)中的交通量按一定比 例分配，求解各路段的交通量。其中，起訖點(diǎn)間的交通量通常稱為OD量，它是 指由Original （起始點(diǎn)）至Destination （

12、目的地）間的交通量?？土鞣峙淠Ｐ褪浅鞘熊壍澜煌土髡T導(dǎo)系統(tǒng)的主要技術(shù)基礎(chǔ)，它為誘導(dǎo)決策 提供依據(jù)。城市軌道交通客流分配模型以交通分配理論為依托，以乘客為交通出 行實(shí)體展開研究。交通分配準(zhǔn)則交通分配準(zhǔn)則，是對(duì)道路使用者選擇路徑的行為的描述。其一，OD間所有 可供選擇的路徑彼此制約；其二，網(wǎng)絡(luò)中各路段均有其相應(yīng)的路阻函數(shù)。路網(wǎng)中 的平衡交通流模式正是由二者的相互作用，以及道路使用者選擇路徑的原則所決 定的。J.GWardrop于1952年提出與出行路徑選擇相關(guān)的第一、第二原理48。 內(nèi)容如下：第一原理：網(wǎng)絡(luò)上的交通需求以這樣一種方式分配，就是任一 OD對(duì)間所有 使用者的路徑的出行費(fèi)用都相等，且比未

13、使用的路徑費(fèi)用小。第二原理：網(wǎng)絡(luò)上的交通分配，使得網(wǎng)絡(luò)上所有出行的總費(fèi)用最小。通常情 況，人們的出行符合Wardrop第一原理，相應(yīng)的平衡狀態(tài)是用戶最優(yōu)平衡（User4 / 9Equilibrium,即UE）；符合Wardrop第二原理所描述的平衡狀態(tài)是系統(tǒng)最優(yōu)平衡 （System Optimum，艮口 SO ）。UE的前提是出行者都想使自己在OD間所花費(fèi)的時(shí)間最短，但是最短路徑 上花費(fèi)的時(shí)間會(huì)隨著交通量而發(fā)生變化，當(dāng)時(shí)間增加達(dá)到某個(gè)臨界值時(shí)，由于擁 擠而使最短路徑降為次短路徑。此時(shí)，一些出行者就開始選擇新的最短路徑。以 此類推，新的最短路徑也會(huì)變成次短路徑。當(dāng)只利用選擇路徑的方法不能減少出

14、行時(shí)間的時(shí)候，就達(dá)到了一種平衡的狀態(tài)。這便是用戶平衡分配的特征。與用戶 最優(yōu)平衡狀態(tài)相對(duì)應(yīng)的交通流稱為用戶最優(yōu)平衡流。SO是系統(tǒng)規(guī)劃者理想中的一種平衡狀態(tài)，前提條件為所有出行者要彼此協(xié) 作，聽從管理者的調(diào)度安排，使得系統(tǒng)的總費(fèi)用最低。與系統(tǒng)最優(yōu)平衡狀態(tài)相對(duì) 應(yīng)的交通流稱為系統(tǒng)最優(yōu)平衡流。通常認(rèn)為，出行者獨(dú)立選擇路徑的行為形成了路網(wǎng)中交通流的分布。在SO 模式下，出行者選擇不同的路徑能降低所花費(fèi)的時(shí)間，所以，出行者趨于選擇時(shí) 間最短的路徑。最終，路網(wǎng)上交通量會(huì)達(dá)到UE狀態(tài)的分布。UE狀態(tài)相對(duì)于SO 狀態(tài)可以更好地反映現(xiàn)實(shí)的交通狀態(tài)。其分配準(zhǔn)則是交通平衡分配模型的基礎(chǔ)。 前提假設(shè)為：出行者了解整個(gè)

15、交通網(wǎng)當(dāng)前狀態(tài)下的全部信息，而且能夠持續(xù)做出正確選 擇；所有出行者的路徑選擇準(zhǔn)則相同。根據(jù)Wardrop第一、第二原理，交通分配方法可以分成平衡模型和非平衡模 型。交通分配模型如果符合Wardrop第一、第二原理，那么就是平衡模型，否則， 就是非平衡模型。平衡分配的方法有很多種，一般都能夠轉(zhuǎn)化成一個(gè)有很大維數(shù) 的非線性的或凸規(guī)劃的問題。理論上，此類模型的思路清晰，結(jié)構(gòu)嚴(yán)謹(jǐn)，在宏觀 研究中比較常用。然而，該類模型維數(shù)大，限制多，難以求解，雖然有近似的方 法，但是計(jì)算繁瑣，難以用于實(shí)際的工程項(xiàng)目中。非平衡分配模型的結(jié)構(gòu)簡單， 概念清晰，計(jì)算簡潔，普遍應(yīng)用于實(shí)際的工程項(xiàng)目中。非平衡分配模型非平衡分配

16、模型依據(jù)不同的標(biāo)準(zhǔn)有不同的分類。一般可以按照分配手段和分 配形態(tài)劃分。將非平衡模型分類組合，可得到：最短路徑分配最短路徑分配是靜態(tài)交通分配的一種方法。計(jì)算時(shí)，假設(shè)路段上花費(fèi)的時(shí)間 為一個(gè)不變的值，所有0D對(duì)間的OD量都分配到其間的最短路上，其它路徑上 的交通量為零，即全有全無分配。最短路徑分配計(jì)算過程簡單，但由于0D量 都聚集在最短路中，導(dǎo)致某些路段上交通量過大，不符合實(shí)際交通流的狀態(tài)。通 常，該方法不適合單獨(dú)用于路網(wǎng)的交通量分配中。容量限制分配容量限制分配是動(dòng)態(tài)分配的一種方法，由于考慮了路段出行時(shí)間和交通最大 容量間的關(guān)系，接近實(shí)際，因而被廣泛應(yīng)用。可以細(xì)分為容量限制一一增量加載 分配和容量

17、限制t迭代平衡分配這兩種方式。容量限制一一增量加載分配，是一種使用啟發(fā)式算法的近似平衡分配方法。 基本思想為：將路網(wǎng)中的0D量分成若干部分，然后依次把每一部分的OD量分 到各個(gè)路段上。每次都根據(jù)最短路方法分配，之后重新對(duì)各個(gè)路段的費(fèi)用進(jìn)行計(jì) 算，然后按照新的費(fèi)用值再次進(jìn)行分配，直至所有OD量分配完為止。此方法運(yùn) 算簡單、容易實(shí)現(xiàn)，可根據(jù)分配次數(shù)調(diào)整精度，比較實(shí)用，但也存在著隱患，可 能出現(xiàn)大量的客流被分配到容量較小的路段上，難以求出平衡解。容量限制一一迭代平衡分配是一種循環(huán)的分配方法，它處于增量分配和平衡 分配之間。基本思想為：首先假設(shè)所有路段上的流量均為零，并且根據(jù)流量計(jì)算 路徑費(fèi)用，通過不

18、斷調(diào)整已分配到路段上的客流量，使各路段交通流近似或達(dá)到 平衡。每次分配，都依據(jù)路段已得到的交通量求出路徑費(fèi)用，然后按最短路方法 分配，如果兩次相鄰分配的交通流量相差不多，計(jì)算就可以終止。最后一次計(jì)算 求出的分配量就是最終的交通量。否則，就需要重復(fù)進(jìn)行分配。此方法在理論上 存在不足，因?yàn)樗荒茴A(yù)先估算迭代的次數(shù)，且無法確定算法最后是否收斂。靜態(tài)多路徑分配靜態(tài)多路徑分配，即Logit分配。由于交通環(huán)境復(fù)雜以及存在的不確定狀況， 出行者可以使用概率分配方法來選擇出行路徑，綜合各種影響因素確定每條路徑 被選擇的概率，之后，按照各路段的概率將交通量合理分配。此方法恰當(dāng)?shù)伢w現(xiàn) 了路徑選擇時(shí)的最短路因素和隨

19、機(jī)因素。動(dòng)態(tài)多路徑分配動(dòng)態(tài)多路徑分配類似于容量限制分配，也分為動(dòng)態(tài)多路徑一一增量加載分配 和動(dòng)態(tài)多路徑一一迭代平衡分配這兩種方式。動(dòng)態(tài)多路徑分配的步驟、路徑費(fèi)用 更新和參數(shù)確定的方法與容量限制分配是一樣的，唯一的區(qū)別為：容量限制分配 方法每次使用最短路方法進(jìn)行分配，而動(dòng)態(tài)多路徑分配方法，每次使用靜態(tài)多路 徑方法進(jìn)行分配。有效路徑搜索算法城市軌道交通中的有效路徑的搜索結(jié)果對(duì)路網(wǎng)中的配流有直接的影響。目前， 常用的有效路徑的搜索算法包括K條漸短路徑搜索算法、Dial算法以及基于圖的 遍歷算法。K條漸短路徑搜索算法由于預(yù)測(cè)時(shí)會(huì)有誤差，所以誘導(dǎo)系統(tǒng)中得到的最短路徑可能并非實(shí)際的最短 路徑。而出行者出行

20、時(shí)也并不是非要只選擇最短路徑，也可能考慮其它因素選擇 次短路徑、漸短路徑。況且，如果僅向出行者提供唯一的最短路徑，很容易造成 車流積聚。所以誘導(dǎo)系統(tǒng)需要同時(shí)提供目標(biāo)值從小到大的K條最短路徑，供出行 者選擇。同時(shí)計(jì)算出某范圍內(nèi)的若干條最短路徑的問題在學(xué)術(shù)上稱為K條漸短路 徑問題。i最短路徑(FSP)算法根據(jù)Dijkstra算法可以計(jì)算出路網(wǎng)中任意兩站之間的最短路徑。ii次短路徑(SSP)算法次短路徑算法的實(shí)質(zhì)：計(jì)算出起訖站點(diǎn)間的最短路徑后，依次刪去原圖中屬 于最短路徑的一條邊，然后根據(jù)算法(1)計(jì)算新圖的最短路徑，即得出次短路徑， 不斷循環(huán)該過程，直至最短路徑中所有邊均被刪除過為止。iii漸短路

21、徑(TSP)算法漸短路徑算法是以算法(2)為基礎(chǔ)計(jì)算的。首先判斷最短路徑和次短路徑中 是否存在相同邊，如果存在，那么刪除該相同邊，并用算法(1)進(jìn)行搜索，重復(fù) 此過程直至最短路徑與次短路徑中不存在相同的邊為止；然后把最短路徑和次短 路徑中剩余的不同的邊進(jìn)行匹配，依次刪除邊對(duì)，再用算法(1)進(jìn)行搜索。Dial算法有效路徑在Dial算法中的定義如下：路徑中的各路段均使出行者到起點(diǎn)的路 徑費(fèi)用逐漸增大，而到終點(diǎn)的路徑費(fèi)用逐漸減小，滿足該要求的路徑稱為有效路 徑。Dial算法在路網(wǎng)中各路段的兩端點(diǎn)(i,j)，引入兩個(gè)變量：r(i)：結(jié)點(diǎn)i至起點(diǎn)r的最小路徑費(fèi)用；s(j)：結(jié)點(diǎn)j至終點(diǎn)s的最小路徑費(fèi)用。

22、當(dāng)且僅當(dāng)滿足條件r(i)s(j)時(shí)，路段(i,j)可以稱為0D對(duì)(r,s)間的一條 有效路徑。基于圖的遍歷搜索算法該算法搜索有效路徑時(shí)有一個(gè)前提條件，它假設(shè)每一條路徑中都不存在重復(fù) 的結(jié)點(diǎn)，也就是說所有的路徑中均沒有回路存在的現(xiàn)象。這個(gè)假設(shè)前提在現(xiàn)實(shí)的 軌道交通路網(wǎng)中是符合實(shí)際情況的，因?yàn)樵谡Ｇ闆r下，沒有人出行的起點(diǎn)和終 點(diǎn)是一樣的，走一圈又回到原點(diǎn)的事情是不存在的。該算法的基本思想：根據(jù)圖的遍歷算法，在圖中搜索由指定起點(diǎn)至終點(diǎn)的有 效路徑，即相互連通并滿足約束條件的路徑，若滿足約束條件，那么就將此路徑 記下來，否則，就要向上一層結(jié)點(diǎn)回溯，然后再重新進(jìn)行遍歷。如此循環(huán)選擇和 回溯，直至搜索到圖中全部有效路徑。進(jìn)行該算法時(shí)，遍歷到任何一個(gè)結(jié)點(diǎn)，該 結(jié)點(diǎn)都有多個(gè)后繼結(jié)點(diǎn)可以選擇，至于要選擇哪個(gè)結(jié)點(diǎn)可以順利找到有效路徑并 沒有任何明確的暗示或是確定信息，只能嘗試選擇某一結(jié)點(diǎn)繼續(xù)向下搜索，直至 終點(diǎn)。如果搜索過程中不滿足約束條件的話，就需要向上一層結(jié)點(diǎn)返回，之后重 新遍歷。該算法利用深度優(yōu)先搜索進(jìn)行圖