最短路徑算法

算法的思想 算法的描述 算法的舉例 TOC\o"1-5"\h\zA*算法 2原理簡介 2詳細(xì)內(nèi)容 2A*算法誤區(qū) 17\o"CurrentDocument"A*算法總結(jié)SummaryoftheA*Method) 17\o"CurrentDocument"Floyd算法 17\o"CurrentDocument"定義 17\o"CurrentDocument"核心思路 18\o"CurrentDocument"算法過程 18\o"CurrentDocument"優(yōu)缺點(diǎn)分析 18\o"CurrentDocument"Johnson算法 23\o"CurrentDocument"Johnson算法要求 23Johnson算法結(jié)構(gòu)要求 23Johnson算法數(shù)據(jù)結(jié)構(gòu). 23\o"CurrentDocument"Johnson算法的內(nèi)容 23\o"CurrentDocument"Johnson算法源程序 23\o"CurrentDocument"DIJKSTRA算法 27\o"CurrentDocument"算法簡介 27\o"CurrentDocument"算法描述 27\o"CurrentDocument"復(fù)雜度分析 27\o"CurrentDocument"算法實現(xiàn) 28測試樣例 30\o"CurrentDocument"算法應(yīng)用的實例 34算法的思想設(shè)圖中有n個結(jié)點(diǎn)，設(shè)置一個集會u,存放已經(jīng)求出最短路徑的結(jié)點(diǎn)(初始時u中的元素是源點(diǎn))，v-u是尚未確定最短路徑的頂點(diǎn)的集合。每次從v-u集合中找這樣一個結(jié)點(diǎn)best_j：best_j是u集合中結(jié)點(diǎn)的鄰接點(diǎn)，到源點(diǎn)的距離最短(等于到父結(jié)點(diǎn)的距離加上父結(jié)點(diǎn)到源點(diǎn)的距離)。然后把該best_j置入u集合中，直到u=v。算法的描述最短路經(jīng)計算分靜態(tài)最短路計算和動態(tài)最短路計算。靜態(tài)路徑最短路徑算法是外界環(huán)境不變，計算最短路徑。主要有Dijkstra算法，A*算法。動態(tài)路徑最短路是外界環(huán)境不斷發(fā)生變化，即不能計算預(yù)測的情況下計算最短路。典型的有D*算法。算法的舉例A*算法原理簡介A*(A-Star)算法是一種靜態(tài)路網(wǎng)中求解最短路最有效的方法。公式表示為：f(n)=g(n)+h(n),其中f(n)是節(jié)點(diǎn)n從初始點(diǎn)到目標(biāo)點(diǎn)的估價函數(shù)，g(n)是在狀態(tài)空間中從初始節(jié)點(diǎn)到n節(jié)點(diǎn)的實際代價，h(n)是從n到目標(biāo)節(jié)點(diǎn)最佳路徑的估計代價。保證找到最短路徑(最優(yōu)解的)條件，關(guān)鍵在于估價函數(shù)h(n)的選?。汗纼r值h(n)＜=n到目標(biāo)節(jié)點(diǎn)的距離實際值，這種情況下，搜索的點(diǎn)數(shù)多，搜索范圍大，效率低。但能得到最優(yōu)解。如果估價值＞實際值，搜索的點(diǎn)數(shù)少，搜索范圍小，效率高，但不能保證得到最優(yōu)解。估價值與實際值越接近，估價函數(shù)取得就越好。例如對于幾何路網(wǎng)來說，可以取兩節(jié)點(diǎn)間歐幾理德距離(直線距離)做為估價值，即f=g(n)+sqrt((dx-nx)*(dx-nx)+(dy-ny)*(dy-ny))；這樣估價函數(shù)f在g值一定的情況下，會或多或少的受估價值h的制約，節(jié)點(diǎn)距目標(biāo)點(diǎn)近，h值小，f值相對就小，能保證最短路的搜索向終點(diǎn)的方向進(jìn)行。明顯優(yōu)于Dijstra算法的毫無無方向的向四周搜索。conditionsofheuristicOptimistic(mustbelessthanorequaltotherealcost)Asclosetotherealcostaspossible詳細(xì)內(nèi)容初始A*算法主要搜索過程：創(chuàng)建兩個表，OPEN表保存所有已生成而未考察的節(jié)點(diǎn)，CLOSED表中記錄已訪問過的節(jié)點(diǎn)。遍歷當(dāng)前節(jié)點(diǎn)的各個節(jié)點(diǎn)，將n節(jié)點(diǎn)放入CLOSE中，取n節(jié)點(diǎn)的子節(jié)點(diǎn)X,-＞算X的估價值->While(OPEN!=NULL){從OPEN表中取估價值f最小的節(jié)點(diǎn)n;if(n節(jié)點(diǎn)==目標(biāo)節(jié)點(diǎn))break;else{if(XinOPEN)比較兩個X的估價值f//注意是同一個節(jié)點(diǎn)的兩個不同路徑的估價值if(X的估價值小于OPEN表的估價值)更新OPEN表中的估價值;〃取最小路徑的估價值if(XinCLOSE)比較兩個X的估價值//注意是同一個節(jié)點(diǎn)的兩個不同路徑的估價值if(X的估價值小于CLOSE表的估價值)更新CLOSE表中的估價值；把X節(jié)點(diǎn)放入OPEN//取最小路徑的估價值if(Xnotinboth)求X的估價值；并將X插入OPEN表中;〃還沒有排序}將n節(jié)點(diǎn)插入CLOSE表中；按照估價值將OPEN表中的節(jié)點(diǎn)排序；〃實際上是比較OPEN表內(nèi)節(jié)點(diǎn)f的大小，從最小路徑的節(jié)點(diǎn)向下進(jìn)行。啟發(fā)式搜索其實有很多的算法，比如：局部擇優(yōu)搜索法、最好優(yōu)先搜索法等等。當(dāng)然A*也是。這些算法都使用了啟發(fā)函數(shù)，但在具體的選取最佳搜索節(jié)點(diǎn)時的策略不同。象局部擇優(yōu)搜索法，就是在搜索的過程中選取“最佳節(jié)點(diǎn)”后舍棄其他的兄弟節(jié)點(diǎn)，父親節(jié)點(diǎn)，而一直得搜索下去。這種搜索的結(jié)果很明顯，由于舍棄了其他的節(jié)點(diǎn)，可能也把最好的節(jié)點(diǎn)都舍棄了，因為求解的最佳節(jié)點(diǎn)只是在該階段的最佳并不一定是全局的最佳。最好優(yōu)先就聰明多了，他在搜索時，便沒有舍棄節(jié)點(diǎn)(除非該節(jié)點(diǎn)是死節(jié)點(diǎn))，在每一步的估價中都把當(dāng)前的節(jié)點(diǎn)和以前的節(jié)點(diǎn)的估價值比較得到一個“最佳的節(jié)點(diǎn)”。這樣可以有效的防止“最佳節(jié)點(diǎn)”的丟失。那么A*算法又是一種什么樣的算法呢？其實A*算法也是一種最好優(yōu)先的算法。只不過要加上一些約束條件罷了。由于在一些問題求解時，我們希望能夠求解出狀態(tài)空間搜索的最短路徑，也就是用最快的方法求解問題，A*就是干這種事情的！我們先下個定義，如果一個估價函數(shù)可以找出最短的路徑，我們稱之為可采納性。A*算法是一個可采納的最好優(yōu)先算法。A*算法的估價函數(shù)可表示為：f(n)=g'(n)+h'(n)這里，f(n)是估價函數(shù)，g'(n)是起點(diǎn)到終點(diǎn)的最短路徑值，h'(n)是n到目標(biāo)的最斷路經(jīng)的啟發(fā)值。由于這個f(n)其實是無法預(yù)先知道的，所以我們用前面的估價函數(shù)f(n)做近似。g(n)代替g'(n)，但g(n)>=g'(n)才可(大多數(shù)情況下都是滿足的，可以不用考慮)，h(n)代替h'(n)，但h(n)<=h'(n)才可(這一點(diǎn)特別的重要)?？梢宰C明應(yīng)用這樣的估價函數(shù)是可以找到最短路徑的，也就是可采納的。我們說應(yīng)用這種估價函數(shù)的最好優(yōu)先算法就是A*算法。舉一個例子，其實廣度優(yōu)先算法就是A*算法的特例。其中g(shù)(n)是節(jié)點(diǎn)所在的層數(shù)，h(n)=0，這種h(n)肯定小于h'(n)，所以由前述可知廣度優(yōu)先算法是一種可采納的。當(dāng)然它是一種最臭的A*算法。再說一個問題，就是有關(guān)h(n)啟發(fā)函數(shù)的信息性。h(n)的信息性通俗點(diǎn)說其實就是在估計一個節(jié)點(diǎn)的值時的約束條件，如果信息越多或約束條件越多則排除的節(jié)點(diǎn)就越多，估價函數(shù)越好或說這個算法越好。這就是為什么廣度優(yōu)先算法的那么臭的原因了，誰叫它的h(n)=0，一點(diǎn)啟發(fā)信息都沒有。但在游戲開發(fā)中由于實時性的問題，h(n)的信息越多，它的計算量就越大，耗費(fèi)的時間就越多。就應(yīng)該適當(dāng)?shù)臏p小h(n)的信息，即減小約束條件。但算法的準(zhǔn)確性就差了，這里就有一個平衡的問題。概述雖然掌握了A*算法的人認(rèn)為它容易，但是對于初學(xué)者來說，A*算法還是很復(fù)雜的。搜索區(qū)域(TheSearchArea)我們假設(shè)某人要從A點(diǎn)移動到B點(diǎn)，但是這兩點(diǎn)之間被一堵墻隔開。如圖1，綠色是A，紅色是B，中間藍(lán)色是墻。圖1你應(yīng)該注意到了，我們把要搜尋的區(qū)域劃分成了正方形的格子。這是尋路的第一步，簡化搜索區(qū)域，就像我們這里做的一樣。這個特殊的方法把我們的搜索區(qū)域簡化為了2維數(shù)組。數(shù)組的每一項代表一個格子，它的狀態(tài)就是可走(walkalbe)和不可走(unwalkable)。通過計算出從A到B需要走過哪些方格，就找到了路徑。一旦路徑找到了，人物便從一個方格的中心移動到另一個方格的中心，直至到達(dá)目的地。方格的中心點(diǎn)我們成為“節(jié)點(diǎn)(nodes)”。如果你讀過其他關(guān)于A*尋路算法的文章，你會發(fā)現(xiàn)人們常常都在討論節(jié)點(diǎn)。為什么不直接描述為方格呢？因為我們有可能把搜索區(qū)域劃為為其他多變形而不是正方形，例如可以是六邊形，矩形，甚至可以是任意多變形。而節(jié)點(diǎn)可以放在任意多邊形里面，可以放在多變形的中心，也可以放在多邊形的邊上。我們使用這個系統(tǒng)，因為它最簡單。開始搜索(StartingtheSearch)一旦我們把搜尋區(qū)域簡化為一組可以量化的節(jié)點(diǎn)后，就像上面做的一樣，我們下一步要做的便是查找最短路徑。在A*中，我們從起點(diǎn)開始，檢查其相鄰的方格，然后向四周擴(kuò)展，直至找到目標(biāo)。我們這樣開始我們的尋路旅途：從起點(diǎn)A開始，并把它就加入到一個由方格組成的openlist(開放列表)中。這個openlist有點(diǎn)像是一個購物單。當(dāng)然現(xiàn)在openlist里只有一項，它就是起點(diǎn)A，后面會慢慢加入更多的項。Openlist里的格子是路徑可能會是沿途經(jīng)過的，也有可能不經(jīng)過?；旧蟧penlist是一個待檢查的方格列表。查看與起點(diǎn)A相鄰的方格(忽略其中墻壁所占領(lǐng)的方格，河流所占領(lǐng)的方格及其他

非法地形占領(lǐng)的方格)，把其中可走的(walkable)或可到達(dá)的(reachable)方格也加入到openlist中。把起點(diǎn)A設(shè)置為這些方格的父親(parentnode或parentsquare)。當(dāng)我們在追蹤路徑時，這些父節(jié)點(diǎn)的內(nèi)容是很重要的。稍后解釋。3.把A從openlist中移除，加入到closelist(封閉列表)中，closelist中的每個方格都是現(xiàn)在不需要再關(guān)注的。如下圖所示，深綠色的方格為起點(diǎn)，它的外框是亮藍(lán)色，表示該方格被加入到了closelist。與它相鄰的黑色方格是需要被檢查的，他們的外框是亮要從§1計算出組成路徑的方格的關(guān)鍵是下面這個等式:綠色。每個黑方格都有一個灰色的指針指向他們的父節(jié)點(diǎn)，這里是起點(diǎn)A。要從§1計算出組成路徑的方格的關(guān)鍵是下面這個等式::點(diǎn)A相鄰的方格，按下面描述的一樣或各好呢？具有最小F值的那個。F=G+H這里，G=從起點(diǎn)A移動到指定方格的移動代價，沿著到達(dá)該方格而生成的路徑。H=從指定的方格移動到終點(diǎn)B的估算成本。這個通常被稱為試探法，有點(diǎn)讓人混淆。為什么這么叫呢，因為這是個猜測。直到我們找到了路徑我們才會知道真正的距離，因為途中有各種各樣的東西(比如墻壁，水等)。我們的路徑是這么產(chǎn)生的：反復(fù)遍歷openlist，選擇F值最小的方格。這個過程稍后詳細(xì)描述。我們還是先看看怎么去計算上面的等式。如上所述，G是從起點(diǎn)A移動到指定方格的移動代價。在本例中，橫向和縱向的移動代價為10，對角線的移動代價為14。之所以使用這些數(shù)據(jù)，是因為實際的對角移動距離是2的平方根，或者是近似的1.414倍的橫向或縱向移動代價。使是有10和14就是為了簡單起見。比例是對的，我們避免了開放和小數(shù)的計算。這并不是我們沒有這個能力或是不喜歡數(shù)學(xué)。使用這些數(shù)字也可以使計算機(jī)更快。稍后你便會發(fā)現(xiàn)，如果不使用這些技巧，尋路算法將很慢。既然我們是沿著到達(dá)指定方格的路徑來計算G值，那么計算出該方格的G值的方法就是找出其父親的G值，然后按父親是直線方向還是斜線方向加上10或14。隨著我們離開起點(diǎn)而得到更多的方格，這個方法會變得更加明朗。有很多方法可以估算H值。這里我們使用Manhattan方法，計算從當(dāng)前方格橫向或縱向移動到達(dá)目標(biāo)所經(jīng)過的方格數(shù)，忽略對角移動，然后把總數(shù)乘以 10。之所以叫做Manhattan方法，是因為這很像統(tǒng)計從一個地點(diǎn)到另一個地點(diǎn)所穿過的街區(qū)數(shù)，而你不能斜向穿過街區(qū)。重要的是，計算H是，要忽略路徑中的障礙物。這是對剩余距離的估算值，而不是實際值，因此才稱為試探法。把G和H相加便得到F。我們第一步的結(jié)果如下圖所示。每個方格都標(biāo)上了F，G，H的值，就像起點(diǎn)右邊的方格那樣，左上角是F，左下角是G，右下角是H。

因為水平方向方格的G值都是10，對角線的方格G值都是14。H值通過估算起點(diǎn)于終點(diǎn)（紅色方格）的Manhattan距離得到，僅作橫向和縱向移動，并且忽略沿途的墻壁。使用這種方式，起點(diǎn)右邊的方格到終點(diǎn)有3個方格的距離，因此H=30。這個方格上方的方格到終點(diǎn)有4個方格的距離（注意只計算橫向和縱向距離），因此H=40。對于其他的方格，可以用同樣的方法知道H值是如何得來的。每個方格的F值，再說一次，直接把G值和H值相加就可以了。繼續(xù)搜索（ContinuingtheSearch）為了繼續(xù)搜索，我們從openlist中選擇F值最小的（方格）節(jié)點(diǎn)，然后對所選擇的方格作如下操作：把它從openlist里取出，放到closelist中。檢查所有與它相鄰的方格，忽略其中在closelist中或是不可走（unwalkable）的方格（比如墻，水，或是其他非法地形），如果方格不在openlsit中，則把它們加入到openlist中。把我們選定的方格設(shè)置為這些新加入的方格的父親。,起點(diǎn)被放入如果某個相鄰的方格已經(jīng)在openlist中，則檢查這條路徑是否更優(yōu)，也就是說經(jīng)由當(dāng)前方格（我們選中的方格）到達(dá)那個方格是否具有更小的G值。如果沒有，不做任何操作。相反，如果G值更小，則把那個方格的父親設(shè)為當(dāng)前方格（我們選中的方格），然后重新計算那個方格的F值和G值。如果你還是很混淆，請參考下圖。

,起點(diǎn)被放入了closelist中。在這些方格中，起點(diǎn)右邊的格子的F值40最小，因此我們選擇這個方格作為下一個要處理的方格。它的外框用藍(lán)線打亮。首先，我們把它從openlist移到closelist中（這就是為什么用藍(lán)線打亮的原因了）。然后我們檢查與它相鄰的方格。它右邊的方格是墻壁，我們忽略。它左邊的方格是起點(diǎn)，在closelist中，我們也忽略。其他4個相鄰的方格均在openlist中，我們需要檢查經(jīng)由這個方格到達(dá)那里的路徑是否更好，使用G值來判定。讓我們看看上面的方格。它現(xiàn)在的G值為14。如果我們經(jīng)由當(dāng)前方格到達(dá)那里，G值將會為20（其中10為到達(dá)當(dāng)前方格的G值，此外還要加上從當(dāng)前方格縱向移動到上面方格的G值10）。顯然20比14大，因此這不是最優(yōu)的路徑。如果你看圖你就會明白。直接從起點(diǎn)沿對角線移動到那個方格比先橫向移動再縱向移動要好。當(dāng)把4個已經(jīng)在openlist中的相鄰方格都檢查后，沒有發(fā)現(xiàn)經(jīng)由當(dāng)前方格的更好路徑，因此我們不做任何改變?，F(xiàn)在我們已經(jīng)檢查了當(dāng)前方格的所有相鄰的方格，并也對他們作了處理，是時候選擇下一個待處理的方格了。因此再次遍歷我們的openlist，現(xiàn)在它只有7個方格了，我們需要選擇F值最小的那個。有趣的是，這次有兩個方格的F值都54，選哪個呢？沒什么關(guān)系。從速度上考慮，選擇最后加入openlist的方格更快。這導(dǎo)致了在尋路過程中，當(dāng)靠近目標(biāo)時，優(yōu)先使用新找到的方格的偏好。但是這并不重要。（對相同數(shù)據(jù)的不同對待，導(dǎo)致兩中版本的A*找到等長的不同路徑）。我們選擇起點(diǎn)右下方的方格，如下圖所示。們把

動到I,隼。我方格移意：穿越墻角的規(guī)則是可選的，依賴于你的節(jié)點(diǎn)是怎么放置的）這樣還剩下5們把

動到I,前方格下面的2個方格還沒有加入openlist，所以把它們加入，同時把當(dāng)前方格設(shè)為他們的父親。在剩下的3個方格中，有2個已經(jīng)在closelist中（一個是起點(diǎn)，一個是當(dāng)前方格上面的方格，外框被加亮的），我們忽略它們。最后一個方格，也就是當(dāng)前方格左邊的方格，我們檢查經(jīng)由當(dāng)前方格到達(dá)那里是否具有更小的G值。沒有。因此我們準(zhǔn)備從openlist中選擇下一個待處理的方格。不斷重復(fù)這個過程，直到把終點(diǎn)也加入到了openlist中，此時如下圖所示。

它右上方的方格?，F(xiàn)在它的G值為20，并且指向它正上方的方格。這在尋路過程中的某處發(fā)生，使用新路徑時G值經(jīng)過檢查并且變得更低，因此父節(jié)點(diǎn)被重新設(shè)置，G和F值被重新計算。盡管這一變化在本例中并不重要，但是在很多場合中，這種變化會導(dǎo)致尋路結(jié)果的巨大變化。那么我們怎么樣去確定實際路徑呢？很簡單，從終點(diǎn)開始，按著箭頭向父節(jié)點(diǎn)移動，這樣你就被帶回到了起點(diǎn)，這就是你的路徑。如下圖所示。從起點(diǎn)A移動到終點(diǎn)B就是簡單從路徑上的一個方格的中心移動到另一個方格的中心，直至目標(biāo)圖7。就是這么簡單圖7圖7代碼如下：namespaceAStar{classPoint

{publicPoint(){}publicPoint(intx,inty){this.x=x;this.y=y;}privateintx;publicintX{get{returnx;}set{x=value;}}privateinty;publicintY{get{returny;}set{y=value;}} }classPath{privateinth;publicintH{get{returnh;}set{h=value;} }privateintf;publicintF{get{returnf;}set{f=value;}}privateintg;publicintG{get{returng;}set{g=value;}}privatePointstartPoint;publicPointStartPoint{get{returnstartPoint;}set{startPoint=value;}}privatePointendPoint;publicPointEndPoint{get{returnendPoint;}set{endPoint=value;}} } }namespaceAStar{classProgram{privatestaticArrayListcloselist=newArrayList();privatestaticArrayListopenlist=newArrayList();privateprivatestaticPointp_start=newPoint(0,0);privateprivatestaticPointp_end=newPoint(9,9);privatestaticintgw=10,privatestaticintgw=10,gwh=14;///gh=10,privatestaticintw=10,h=10;//privatestaticstringn_path=privatestaticprivatestaticintw=10,h=10;//privatestaticstringn_path=privatestaticPaths_path=newPath();privatestaticintnum;staticvoidMain(string[]args){inth=(Math.Abs(p_end.X-p_start.Y)+Math.Abs(p_end.Y-p_start.Y))*gw;s_path.F=h;s_path.G=0;s_path.H=h;s_path.StartPoint=p_start;s_path.EndPoint=p_start;do{GetF(setDirection(s_path.StartPoint));Sort(openlist);s_path=(Path)openlist[openlist.Count-1];closelist.Add(s_path);openlist.RemoveAt(openlist.Count-1);if(openlist.Count==0){Console.WriteLine("找不到路徑");return;}if((s_path.StartPoint.X==p_end.X)&&(s_path.StartPoint.Y==p_end.Y)){getPath();break;}}while(true);}staticArrayListsetDirection(PointstartPoint){ArrayListdirection=newArrayList();PointnorthEast=newPoint();northEast.X=startPoint.X+1;northEast.Y=startPoint.Y-1;direction.Add(northEast);//東北Pointeast=newPoint();east.X=startPoint.X+1;east.Y=startPoint.Y;direction.Add(east);//東PointsouthEast=newPoint();southEast.X=startPoint.X+1;southEast.Y=startPoint.Y+1;direction.Add(southEast);//東南Pointsouth=newPoint();south.X=startPoint.X;south.Y=startPoint.Y+1;direction.Add(south);//南PointsouthWest=newPoint();southWest.X=startPoint.X-1;southWest.Y=startPoint.Y+1;direction.Add(southWest);//西南Pointwest=newPoint();west.X=startPoint.X-1;west.Y=startPoint.Y;direction.Add(west);//西PointnorthWast=newPoint();northWast.X=startPoint.X-1;northWast.Y=startPoint.Y-1;direction.Add(northWast);//西北Pointnorth=newPoint();north.X=startPoint.X;north.Y=startPoint.Y-1;direction.Add(north);//西北returndirection;}staticvoidGetF(ArrayListarr){int[]t=newint[2];intG,H,F;for(inti=0;i<arr.Count;i++){t[0]=((Point)arr[i]).X;t[1]=((Point)arr[i]).Y;if(IsOutScreen((Point)arr[i])||IsPass((Point)arr[i])||IsClose((Point)arr[i])||IsStart((Point)arr[i])||!IsInTurn((Point)arr[i]))continue;if((t[0]-s_path.StartPoint.X)*(t[1]-s_path.StartPoint.Y)!=0)G=s_path.G+gwh;elseG=s_path.G+gw;if(InOpen((Point)arr[i])){if(G<((Path)openlist[num]).G){((Path)openlist[num]).F=(G+((Path)openlist[num]).H);((Path)openlist[num]).G=G;((Path)openlist[num]).EndPoint=s_path.StartPoint;}else{G=((Path)openlist[num]).G;} }else{H=(Math.Abs(p_end.X-t[0])+Math.Abs(p_end.Y-t[1]))*gw;F=G+H;Pathp=newPath();p.F=F;p.G=G;p.H=H;p.StartPoint=(Point)arr[i];p.EndPoint=s_path.StartPoint;openlist.Add(p);}} }staticboolIsStart(Pointarr){if(arr.X==p_start.X&&arr.Y==p_start.Y)returntrue;returnfalse;}staticboolIsInTurn(Pointarr){if(arr.X>p_start.X){if(arr.Y>p_start.Y)if(IsPass(newPoint(arr.X-1,arr.Y))||IsPass(newPoint(arr.X,arr.Y-1)))returnfalse;}elseif(arr.Y<p_start.Y){if(IsPass(newPoint(arr.X-1,arr.Y))||IsPass(newPoint(arr.X,arr.Y+1)))returnfalse;} }elseif(arr.X<p_start.X){if(arr.Y>p_start.Y){if(IsPass(newPoint(arr.X+1,arr.Y))||IsPass(newPoint(arr.X,arr.Y-1)))returnfalse;}elseif(arr.Y<p_start.Y){if(IsPass(newPoint(arr.X+1,arr.Y))||IsPass(newPoint(arr.X,arr.Y+1)))returnfalse;} }returntrue;}staticboolIsOutScreen(Pointarr){if(arr.X<0||arr.Y<0||arr.X>(w-1)||arr.Y>(h-1))returntrue;returnfalse;}staticboolInOpen(Pointarr){boolresult=false;for(inti=0;i<openlist.Count;i++){if(arr.X==((Path)openlist[i]).StartPoint.X&&arr.Y==((Path)openlist[i]).StartPoint.Y){result=true;num=i;break;}}returnresult;}staticboolIsClose(Pointarr){boolresult=false;for(inti=0;i<closelist.Count;i++){if((arr.X==((Path)closelist[i]).StartPoint.X)&&(arr.Y==((Path)closelist[i]).StartPoint.Y)){result=true;break;}}returnresult;}staticboolIsPass(Pointpos){if(Map[pos.X,pos.Y]>1)returntrue;returnfalse;}staticvoidSort(ArrayListarr){Pathtemp;for(inti=0;i<arr.Count;i++){if(arr.Count==1)break;if(((Path)arr[i]).F<=((Path)arr[i+1]).F){temp=(Path)arr[i];arr[i]=arr[i+1];arr[i+1]=temp;}if((i+1)==(arr.Count-1))break;}}staticvoidgetPath(){stringstr="”;Pointt=((Path)closelist[closelist.Count-1]).EndPoint;while(true){str+="("+t.X+","+t.Y+")”;for(inti=0;i<closelist.Count;i++){if(((Path)closelist[i]).StartPoint.X==t.X&&((Path)closelist[i]).StartPoint.Y==t.Y)t=((Path)closelist[i]).EndPoint;}if(t.X==p_start.X&&t.Y==p_start.Y)break;}Console.WriteLine(str);}staticint[,]Map={TOC\o"1-5"\h\z{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },{ 1, 1, 1, 1, 1, 2, 1, 1, 1, 1 },{ 1, 1, 1, 1, 2, 3, 2, 1, 1, 1 },{ 1, 1, 1, 2, 3, 4, 3, 2, 1, 1 },{ 1, 1, 2, 3, 4, 5, 4, 3, 2, 1 },{ 1, 1, 1, 2, 3, 4, 3, 2, 1, 1 },{ 1, 1, 1, 1, 2, 3, 2, 1, 1, 1 },{ 1, 1, 1, 1, 1, 2, 1, 1, 1, 1 },{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }深入A*算法如圖有如下的狀態(tài)空間：（起始位置是人，目標(biāo)位置是P,字母后的數(shù)字表示節(jié)點(diǎn)的估價值）搜索過程中設(shè)置兩個表：Open和closed。open表保存了所有已生成而未考察的節(jié)點(diǎn)，CLOSED表中記錄已訪問過的節(jié)點(diǎn)。算法中有一步是根據(jù)估價函數(shù)重排OPEN表。這樣循環(huán)中的每一步只考慮OPEN表中狀態(tài)最好的節(jié)點(diǎn)。具體搜索過程如下：1） 初始狀態(tài)：OPEN=[A5]；CLOSED=[]；2） 估算A5，取得搜有子節(jié)點(diǎn)，并放入OPEN表中；OPEN=[B4，C4，D6]；CLOSED=[A5]3） 估算B4，取得搜有子節(jié)點(diǎn)，并放入OPEN表中；OPEN=[C4,E5，F(xiàn)5，D6]；CLOSED=[B4，A5]4） 估算C4；取得搜有子節(jié)點(diǎn)，并放入OPEN表中；OPEN=[H3,G4,E5,F5,D6]；CLOSED=[C4,B4,A5]估算H3,取得搜有子節(jié)點(diǎn)，并放入OPEN表中；OPEN=[O2,P3,G4,E5,F5,D6]；CLOSED=[H3,C4,B4,A5]估算O2，取得搜有子節(jié)點(diǎn)，并放入OPEN表中；OPEN=[P3，G4,E5,F5,D6]；CLOSED=[O2,H3,C4,B4,A5]估算P3，已得到解；看了具體的過程，再看看偽程序吧。算法的偽程序如下：Best_First_Search(){Open=[起始節(jié)點(diǎn)];Closed=[];while(Open表非空){從Open中取得一個節(jié)點(diǎn)X，并從OPEN表中刪除。if(X是目標(biāo)節(jié)點(diǎn)){求得路徑PATH返回路徑PATH}for(每一個X的子節(jié)點(diǎn)Y){if(Y不在OPEN表和CLOSE表中){求Y的估價值；并將Y插入OPEN表中；}elseif(Y在OPEN表中){if(Y的估價值小于OPEN表的估價值)更新OPEN表中的估價值；}else{if(Y的估價值小于CLOSE表的估價值){更新CLOSE表中的估價值；從CLOSE表中移出節(jié)點(diǎn)，并放入OPEN表中；} }將X節(jié)點(diǎn)插入CLOSE表中；按照估價值將OPEN表中的節(jié)點(diǎn)排序；} } }偽程序出來了，寫一個源程序應(yīng)該不是問題了，依葫蘆畫瓢就可以。A*算法的程序與此是一樣的，只要注意估價函數(shù)中的g(n)的h(n)約束條件就可以了。不清楚的可以看看《初識A*算法》。我們可以進(jìn)入另一個重要的話題，用A*算法實現(xiàn)最短路徑的搜索。用A*算法實現(xiàn)最短路徑的搜索A*算法的核心是估價函數(shù)f(n)，它包括g(n)和h(n)兩部分。g(n)是已經(jīng)走過的代價，h(n)是n到目標(biāo)的估計代價。在這個例子中g(shù)(n)表示在狀態(tài)空間從起始節(jié)點(diǎn)到n節(jié)點(diǎn)的深度，h(n)表示n節(jié)點(diǎn)所在地圖的位置到目標(biāo)位置的直線距離。?。∫粋€是狀態(tài)空間，一個是實際的地圖，不要搞錯了。再詳細(xì)點(diǎn)說，有一個物體A，在地圖上的坐標(biāo)是(xa,ya)，A所要到達(dá)的目標(biāo)b的坐標(biāo)是(xb,yb)。則開始搜索時，設(shè)置一個起始節(jié)點(diǎn)1，生成八個子節(jié)點(diǎn)2-9因為有八個方向。如圖：仔細(xì)看看節(jié)點(diǎn)1、9、17的g(n)和h(n)是怎么計算。就知道下面程序中的f(n)是如何計算。其實這個程序是一個很典型程序，上面的偽程序，這個程序是十分容易理解的。不過他和上面的偽程序有一些的不同，我在后面會提出來。搜索主函數(shù)：voidAstarPathfinder::FindPath(intsx,intsy,intdx,intdy)(NODE*Node,*BestNode;intTileNumDest;TileNumDest=TileNum(sx,sy);OPEN=(NODE*)calloc(1,sizeof(NODE));CLOSED=(NODE*)calloc(1,sizeof(NODE));Node=(NODE*)calloc(1,sizeof(NODE));Node->g=0;Node->h=(dx-sx)*(dx-sx)+(dy-sy)*(dy-sy);Node->f=Node->g+Node->h;Node->NodeNum=TileNum(dx,dy);Node->x=dx;Node->y=dy;OPEN->NextNode=Node;for(;;)(BestNode=ReturnBestNode();if(BestNode->NodeNum==TileNumDest)GenerateSuccessors(BestNode,sx,sy);}PATH=BestNode;}生成子節(jié)點(diǎn)函數(shù)：voidAstarPathfinder::GenerateSuccessors(NODE*BestNode,intdx,intdy)(intx,y;if(FreeTile(x=BestNode->x-TILESIZE,y=BestNode->y-TILESIZE))GenerateSucc(BestNode,x,y,dx,dy);if(FreeTile(x=BestNode->x,y=BestNode->y-TILESIZE))GenerateSucc(BestNode,x,y,dx,dy);if(FreeTile(x=BestNode->x+TILESIZE,y=BestNode->y-TILESIZE))GenerateSucc(BestNode,x,y,dx,dy);if(FreeTile(x=BestNode->x+TILESIZE,y=BestNode->y))GenerateSucc(BestNode,x,y,dx,dy);if(FreeTile(x=BestNode->x+TILESIZE,y=BestNode->y+TILESIZE))GenerateSucc(BestNode,x,y,dx,dy);if(FreeTile(x=BestNode->x,y=BestNode->y+TILESIZE))GenerateSucc(BestNode,x,y,dx,dy);if(FreeTile(x=BestNode->x-TILESIZE,y=BestNode->y+TILESIZE))GenerateSucc(BestNode,x,y,dx,dy);if(FreeTile(x=BestNode->x-TILESIZE,y=BestNode->y))GenerateSucc(BestNode,x,y,dx,dy);}最重要的函數(shù)：voidAstarPathfinder::GenerateSucc(NODE*BestNode,intx,inty,intdx,intdy){intg,TileNumS,c=0;NODE*Old,^Successor;g=BestNode->g+1;TileNumS=TileNum(x,y);if((Old=CheckOPEN(TileNumS))!=NULL){for(c=0;c<8;c++)if(BestNode->Child[c]==NULL)break;BestNode->Child[c]=Old;if(g<Old->g){Old->Parent=BestNode;Old->g=g;Old->f=g+Old->h;}}elseif((Old=CheckCLOSED(TileNumS))!=NULL){for(c=0;c<8;c++)if(BestNode->Child[c]==NULL)break;BestNode->Child[c]=Old;if(g<Old->g){Old->Parent=BestNode;Old->g=g;Old->f=g+Old->h;PropagateDown(Old);}}Else{Successor=(NODE*)calloc(1,sizeof(NODE));Successor->Parent=BestNode;Successor->g=g;Successor->h=(x-dx)*(x-dx)+(y-dy)*(y-dy);Successor->f=g+Successor->h;Successor->x=x;Successor->y=y;Successor->NodeNum=TileNumS;Insert(Successor);for(c=0;c<8;c++)if(BestNode->Child[c]==NULL)break;BestNode->Child[c]=Successor;}}A*算法誤區(qū)A*是一個啟發(fā)式搜索算法。就是說在一個可以被窮舉的有限解空間集中，用比較有效的方法(主要是利用估價函數(shù))求出最優(yōu)解的算法°A*跟尋路算法沒有太多關(guān)系，我們只是借助了這個方法來解決尋路這個問題，正如四則運(yùn)算對于數(shù)學(xué)題一樣，它只是一個基本工具。尋路算法本身有很多種，我們找到算法后，借助A*這個工具實現(xiàn)這個算法而已。A*算法理論上可以得到最優(yōu)解，不過我們可以通過選擇一個更好的估價函數(shù)，或是減少解空間來提高性能。A*是傳統(tǒng)意義上的地圖尋路，其實依據(jù)的是這樣一種算法：把地圖分成若干個格子，反復(fù)迭代下去把地圖分格子，給格子間的路徑一個權(quán)值(前面的例子中，格子間的距離都是相等的，我們也可以根據(jù)地形劃分成不等的距離，即權(quán)值，或者定義單向道路，這都是可以的)，這是解決尋路問題的關(guān)鍵，但都不是A*算法的范疇。這種一步步嘗試的過程，就是一種搜索過程。如果加上啟發(fā)函數(shù)，不讓它盲目的尋找，就衍生出很多啟發(fā)式搜索算法。A*是其中的一種。之所以加一個*號，是因為它的啟發(fā)式函數(shù)是有限制的，這個限制確保它能找到絕對最優(yōu)解，去掉這個限制，就是A算法了。如果你想出某種算法，比如把地圖劃分成不規(guī)則的區(qū)域，或者把地圖矢量化。依然可以再此基礎(chǔ)上用A*算法這個工具來從中求到最優(yōu)解。如果想別的方法來尋路，比如擬人的判斷，預(yù)設(shè)路點(diǎn)等等，甚至按走迷宮的方法一樣，分叉右轉(zhuǎn)，碰壁回頭，那些可以算是對分格尋路方法的一些改進(jìn)，卻都不關(guān)A*什么事情。A*算法總結(jié)(SummaryoftheA*Method)把起點(diǎn)加入openlist。重復(fù)如下過程：遍歷openlist，查找F值最小的節(jié)點(diǎn)，把它作為當(dāng)前要處理的節(jié)點(diǎn)。把這個節(jié)點(diǎn)移到closelist。對當(dāng)前方格的8個相鄰方格的每一個方格？?如果它是不可抵達(dá)的或者它在closelist中，忽略它。否則，做如下操作。?如果它不在openlist中，把它加入openlist，并且把當(dāng)前方格設(shè)置為它的父親，記錄該方格的F，G和H值。?如果它已經(jīng)在openlist中，檢查這條路徑(即經(jīng)由當(dāng)前方格到達(dá)它那里)是否更好，用G值作參考。更小的G值表示這是更好的路徑。如果是這樣，把它的父親設(shè)置為當(dāng)前方格，并重新計算它的G和F值。如果你的openlist是按F值排序的話，改變后你可能需要重新排序。停止，當(dāng)你?把終點(diǎn)加入到了openlist中，此時路徑已經(jīng)找到了，或者?查找終點(diǎn)失敗，并且openlist是空的，此時沒有路徑。保存路徑。從終點(diǎn)開始，每個方格沿著父節(jié)點(diǎn)移荻直至起點(diǎn)，這就是你的路徑。Floyd算法定義Floyd算法又稱為弗洛伊德算法，插點(diǎn)法，是一種用于尋找給定的加權(quán)圖中頂點(diǎn)間最短路徑的算法。核心思路通過一個圖的權(quán)值矩陣求出它的每兩點(diǎn)間的最短路徑矩陣。從圖的帶權(quán)鄰接矩陣A=[a(i,j)]nxn開始，遞歸地進(jìn)行n次更新，即由矩陣D(0)=A，按一個公式，構(gòu)造出矩陣D(1)；又用同樣地公式由D(1)構(gòu)造出D(2)；……；最后又用同樣的公式由D(n-1)構(gòu)造出矩陣D(n)。矩陣D(n)的i行j列元素便是i號頂點(diǎn)到j(luò)號頂點(diǎn)的最短路徑長度，稱D(n)為圖的距離矩陣，同時還可引入一個后繼節(jié)點(diǎn)矩陣path來記錄兩點(diǎn)間的最短路徑。采用的是松弛技術(shù)，對在i和j之間的所有其他點(diǎn)進(jìn)行一次松弛。所以時間復(fù)雜度為0*3);其狀態(tài)轉(zhuǎn)移方程如下： map[i,j]:=min{map[i,k]+map[k,j],map[i,j]}map[i,j]表示i到j(luò)的最短距離K是窮舉i,的斷點(diǎn)map[n,n]初值應(yīng)該為0，或者按照題目意思來做。當(dāng)然，如果這條路沒有通的話，還必須特殊處理 ，比如沒有map[i,k]這條路算法過程把圖用鄰接矩陣G表示出來，如果從Vi到Vj有路可達(dá)，則G[i,j]=d，d表示該路的長度；否則G[i,j]=空值。定義一個矩陣D用來記錄所插入點(diǎn)的信息，D[i,j]表示從Vi到Vj需要經(jīng)過的點(diǎn)，初始化D[i,j]=j。把各個頂點(diǎn)插入圖中，比較插點(diǎn)后的距離與原來的距離， G[i,j]=min(G[i,j],G[i,k]+G[k,j])，如果G[i,j]的值變小，貝0D[i,j]=k。在G中包含有兩點(diǎn)之間最短道路的信息， 而在D中則包含了最短通路徑的信息。比如，要尋找從V5到V1的路徑。根據(jù)D，假如D(5,1)=3則說明從V5到V1經(jīng)過V3，路徑為{V5,V3,V1}，如果D(5,3)=3，說明V5與V3直接相連，如果D(3,1)=1，說明V3與V1直接相連。優(yōu)缺點(diǎn)分析Floyd算法適用于APSP(AllPairsShortestPaths)，是一種動態(tài)規(guī)劃算法，稠密圖效果最佳，邊權(quán)可正可負(fù)。此算法簡單有效，由于三重循環(huán)結(jié)構(gòu)緊湊，對于稠密圖，效率要高于執(zhí)行|V|次Dijkstra算法。優(yōu)點(diǎn)：容易理解，可以算出任意兩個節(jié)點(diǎn)之間的最短距離，代碼編寫簡單；缺點(diǎn)：時間復(fù)雜度比較高，不適合計算大量數(shù)據(jù)。如何用floyd算法求出最短路徑一：flody是如何實現(xiàn)搜索最短路徑的：

Floyd又稱插點(diǎn)法，它的基本過程如下：首先用圖鄰接矩陣G表示出來，如果從Vi到Vj有路可達(dá)。則G(I,j)=d,d表示該路長度，否則G(I,j)=inf,最后圖可以用如下圖表示：G=02hfhfi)104[nf4Inf1]0Inf10In：10rr.r90InfInf7Inf210041S4Inf0為了搜索出最短路徑我們還需要一個矩陣用來記錄所插入點(diǎn)的信息，這個矩陣的D，D(i,j)表示從V(i)到V(j)需要經(jīng)過的點(diǎn)，初始化D(I,j)=jD=然后把各個頂點(diǎn)插入圖中，比較插點(diǎn)后的距離與原來的距離，G(I,j)=min(G(I,j)+G(I,k)+G(k,j)),如果G(I,j)的值變小，則G(I,j)=k,如在上個圖中把Vi的值插入后所得結(jié)果為G=(J23Inf[if9I0?1]nf011)110]nfl(i101090Int07E2to0414Inf0D=

124612345：■123451134511□345f]111456這樣我們把各個值都加入后得到G為G=02.1It)2fiI02X04110g1?10】0勺0101433280413■1430D=1262512：&512362IJ43536h111426二：如何搜索出最短路徑：在G中包含有最短道路的消息，而在D中則包含有最短通路徑的信息，如果我從V5到V1的路徑則根據(jù)D,D(5,1)=3則說名點(diǎn)經(jīng)過V3，道路為(V5,V3,V1),D(5,3)=3,說明V5與V3直接連接，D(3,1)=1，說明V3與V1直接相連，具體算法是建立一個表，Vi為頭，以Vj為尾，如果D(i.j)習(xí)則完結(jié)，否則Vh=Vi,Vk0=Vj轉(zhuǎn)(2)如果k(m)=D(h,k(m)),裝(4)，否則轉(zhuǎn)(3)k(m+1)=D(h,k(m))把Vk(m+1)插在Vh,Vk(m)之間，返(2)如果k(m)=j,則完結(jié)，否則Vh=Vk(m),Vk(m)=Vk(m-1);

如上圖經(jīng)過圖中搜索可得到一條較長的道路是從V8如上圖經(jīng)過圖中搜索可得到一條較長的道路是從V8到V200,依次經(jīng)過的頂點(diǎn)為182{8,21,22,27,28,29,51,62,83,90,100,110，126,136,151，150,164，177,178，179,180,181，185，195,197,200}182弗洛伊德Floyd算法思想：遞推地產(chǎn)生一個矩陣序列dist(0)dist⑴...dist(n)其中dist(0)=costcost為鄰接矩陣元素dist(0)[i,j]表示從頂點(diǎn)Vi到頂點(diǎn)Vj，中間經(jīng)過的頂點(diǎn)序號M0(即不經(jīng)任何其他頂點(diǎn))的最短路徑長度。最后dist(n)[i,j]表示從vi到vj中間經(jīng)過的頂點(diǎn)序號不大于n的最短路徑長度。即為所求。dist(k)[i,j]是從vi到vj的中間經(jīng)過頂點(diǎn)序號Mk的最短路——k型最短路。VIV2V3V4VI-oV215p6偵?yoooo4V4CC：'8 2001010615820dist(0)(i,j)=cost(i,j)dist(k)(i,j)=min{dist(k-l)(i,j),dist(k-l)(i,k)+dist(k-1)(k,j)}voidFloyd(GraphG,cost,path){for(i=1;i<=n;i++)//dist,path初始化for(j=1;j<=n;j++){dist[i][j]=cost[i][j];if(dist[i][j]<32767)path[i][j]={Vi}+{Vj};}for(k=1;k<=n;k++)〃遞推產(chǎn)生dist序列for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(dist[i][k]+dist[k][j]{dist[i][j]=dist[i][k]+dist[k][j];path[i][j]=path[i][k]+path[k][j];}}注意：Floyd算法中一種標(biāo)準(zhǔn)錯誤寫法：請注意floyed算法的本質(zhì)是動態(tài)規(guī)劃！定義f(i,j,k)表示只用第0?i個點(diǎn)從j走到k所用的最短路程。f(i,j,k)=min(f(i-1,j,k),f(i-1,j,i)+f(i-1,i,k))所以應(yīng)該是for(inti=0;i<sz;i++)for(intj=0;j<sz;j++)for(intk=0;k<sz;k++){intt_dis=distances[j][i]+distances[i][k];if(distances[j][k]>t_dis)distances[j][k]=t_dis;}很多人沒有弄懂floyed的本質(zhì)就開始背“三個for”的代碼，所以會出現(xiàn)這種標(biāo)準(zhǔn)錯誤答案。Johnson算法Johnson算法要求Johnson算法本身需要調(diào)用BELLMAN_FORD算法和SUKSTRA算法，所以需要另外實現(xiàn)這兩個算法。Johnson算法結(jié)構(gòu)要求不要全部放在一個函數(shù)中，分別為每個算法寫個函數(shù)，然后通過函數(shù)調(diào)用實現(xiàn)，可以用類實現(xiàn)，把圖的信息作為類的成員變量，每個函數(shù)作為類的成員函數(shù)；也可以不用類，就單獨(dú)寫幾個函數(shù)，然后通過main函數(shù)直接調(diào)用。Johnson算法數(shù)據(jù)結(jié)構(gòu)下面給的測試數(shù)據(jù)是用鄰接矩陣存儲的，大家實現(xiàn)算法的時候用什么方式存儲都可以，如果用鄰接表，把自己的數(shù)據(jù)轉(zhuǎn)換成你需要的格式。但是輸出的時候必須按照下面的要求，這樣檢查程序的時候也比較方便。Johnson算法的內(nèi)容Johnson算法適用于求AllPairsShortestPath.Johnson算法應(yīng)用了重標(biāo)號技術(shù)，先進(jìn)行一次Bellman-Ford算法，然后對原圖進(jìn)行重標(biāo)號，w'(i,j)=h[i]-h[j]+w(i,j)。然后對每個點(diǎn)進(jìn)行一次Dijkstra，每次Dijkstra的復(fù)雜度為O(nlogn+m)，于是算法復(fù)雜度為O(nA2logn+m)oJohnson算法源程序II、#include#include#definelensizeof(structnode)typedefstructnode(floatbound;intstaus[50];structnode*next;}node;intitem[50],wl,n,state[50];floatvalue[50],weight[50],max_value,ratio[50];voiddele(node*father,node*current){if(current->next==NULL){father->next=NULL;return;}father->next=current->next;}voidinit(node*father,node*son){inti;father->next=son;for(i=0;ison->staus[i]=0;son->next=NULL;}voidbranch(){inti,t,j;floatdiff,sum=0,sum_value=0;node*head,*sonbrother,*father,*son,*prenode,*p,*q;head=prenode=(node*)malloc(len);father=(node*)malloc(len);init(prenode,father);father->bound=32768;while(head->next!=NULL){son=(node*)malloc(len);init(father,son);for(i=0;istaus[i]!=0;i++)son->staus[i]=father->staus[i];t=i;son->staus[t]=-(t+1);sum=0;sum_value=0;for(j=0;jstaus[j]!=0;j++)if(son->staus[j]>0){sum=sum+weight[item[j]];sum_value=sum_value+value[item[j]];}while(sum!=wl&&son->staus[n-1]==0){diff=wl-(sum+weight[item[j]]);if(diff>=0)(sum=sum+weight[item[j]];sum_value=sum_value+value[item[j]];}else{sum=wl;sum_value=sum_value+(1+diff/weight[item[j]])*value[item[j]];}j++;}son->bound=sum_value;sonbrother=(node*)malloc(len);init(son,sonbrother);for(i=0;isonbrother->staus[i]=father->staus[i];sonbrother->staus[t]=t+1;sum=0;sum_value=0;for(j=0;jstaus[j]!=0;j++)if(sonbrother->staus[j]>0){sum=sum+weight[item[j]];sum_value=sum_value+value[item[j]];}if(sum>wl){sonbrother->bound=-32768;dele(son,sonbrother);}else{while(sum!=wl&&sonbrother->staus[n-1]==0){diff=wl-(sum+weight[item[j]]);if(diff>=0){sum=sum+weight[item[j]];sum_value=sum_value+value[item[j]];}else{sum=wl;sum_value=sum_value+(1+diff/weight[item[j]])*value[item[j]];}j++;}sonbrother->bound=sum_value;}dele(prenode,father);father=prenode->next;if(son->staus[n-1]!=0){if(son->next!=NULL){max_value=sonbrother->bound;for(i=0;istate[i]=sonbrother->staus[i];dele(son,sonbrother);dele(prenode,father);father=prenode->next;}else{max_value=son->bound;for(i=0;istate[i]=son->staus[i];dele(prenode,father);}q=head;p=head->next;while((p!=NULL)&&(p->bound<=max_value)){dele(q,p);p=q->next;}if(p!=NULL){prenode=q;father=p;}elsereturn;}elseif(father->next!=NULL){prenode=prenode->next;father=father->next;} }return;}intgetmin(){inti;floatamin=weight[0];for(i=1;iif(amin>weight[i])amin=weight[i];returnamin;}voidsort(){inti,j,exchange=1;floattemp1,temp2;for(i=0;iratio[i]=value[i]/weight[i];for(j=n-1;j>=0&&exchange==1;j--){exchange=0;for(i=0;iif(ratio[i+1]>ratio[i]){exchange=1;temp1=ratio[i+1];ratio[i+1]=ratio[i];ratio[i]=temp1;temp2=item[i+1];item[i+1]=item[i];item[i]=temp2;}}voidmain(){inti,j;floatsum=0;clrscr();printf("\tWelcometotheBRANCH_BOUNDsystem!\n"););printf("numberofthematerials^?);scanf("%d”,&n);");printf("maximunweighoftheproblem=?");scanf("%d”,&wl);for(i=0;i{item[i]=i;printf("\n*******************\n");printf("inputitem%ddata!\n",i+1);printf("*******************\n");

”,i+1)；”,i+1)；scanf("%f”,&weight[i]);printf("value%d=?scanf("%f”,&value[i]);if((getmin())>wl)(printf("\nThereisnosolutionoftheproblem!");exit(0);}for(i=0;isum=sum+weight[i];if(sum<=wl)(printf("\nAllthematerialscanbeloaded!");exit(0);}sort();branch();printf("\n\n\nThemaximumvalueofthematerialsis%f",max_value);printf("\nincludingthefollowingmaterials\n");sum=0;for(i=0;iif(state[i]>0){sum=sum+weight[item[i]];printf("%d\n",item[i]+1);}printf("\nTheweightofthematerialsis%f",sum);Dijkstra算法Dijkstra算法算法簡介Dijkstra(迪杰斯特拉)算法是典型的單源最短路徑算法，用于計算一個節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展， 直到擴(kuò)展到終點(diǎn)為止。Dijkstra算法是很有代表性的最短路徑算法，在很多專業(yè)課程中都作為基本內(nèi)容有詳細(xì)的介紹，如數(shù)據(jù)結(jié)構(gòu)，圖論，運(yùn)籌學(xué)等等。 Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標(biāo)號方式，一種是用OPEN,CLOSE表的方式，這里均采用永久和臨時標(biāo)號的方式。注意該算法要求圖中不存在負(fù)權(quán)回路。算法描述(這里描述的是從節(jié)點(diǎn)1開始到各點(diǎn)的dijkstra算法，其中Wa->b表示a->b的邊的權(quán)值，d(i)即為最短路徑值)置集合S={2,3,...n},數(shù)組d(1)=0,d(i)=W1->i(1,i之間存在邊)or+無窮大(1.i之間不存在邊)在S中，令d(j)=min{d(i),i屬于S}，令S=S-{j}，若S為空集則算法結(jié)束，否則轉(zhuǎn)3對全部i屬于S,如果存在邊j->i，那么置d(i)=min{d(i),d(j)+Wj->i}，轉(zhuǎn)2復(fù)雜度分析Dijkstra算法的時間復(fù)雜度為O(V2)空間復(fù)雜度取決于存儲方式，鄰接矩陣為算法實現(xiàn)岸」O(nA2)輸入輸出格式輸入格式：第1行:一個數(shù)n，代表有n個節(jié)點(diǎn)第2-n+1行:每行n個數(shù)，代表圖的鄰接矩陣，沒有邊相連為-1輸出格式：第1行:n-1個數(shù)，分別是1號節(jié)點(diǎn)到2-n號節(jié)點(diǎn)的最短路徑C++#include<fstream>#include<cstring>usingnamespacestd;constintMaxNum=1000000;//邊權(quán)最大值intn;intdist[501];boolstate[501];intdata[501][501];intfindmin(){intminnode=0,min=MaxNum;for(inti=1;i<=n;i++)if((dist[i]<min)&&(!state[i])){min=dist[i];minnode=i;}returnminnode;}intmain(){ifstreamin("dijkstra.in");ofstreamout("dijkstra.out");memset(state,0,sizeof(state));in>>n;for(intp=1;p<=n;p++)for(intq=1;q<=n;q++){in>>data[p][q];if(data[p][q]==0)data[p][q]=MaxNum;}for(inti=1;i<=n;i++)dist[i]=data[1][i];state[1]=true;intdone=1;while(done<n){intnode=findmin();if(node!=0){done++;state[node]=true;for(inti=1;i<=n;i++)if((dist[i]>dist[node]+data[node][i])&&(!state[i]))dist[i]=dist[node]+data[node][i];}elsebreak;}for(intp=1;p<=n;p++){if(dist[p]==MaxNum)out<<-1;elseout<<dist[p];if(p==n)out<<endl;elseout<<"";}in.close();out.close();return0;}Pascalprogramdijkstra;varstate:array[1..100]ofboolean;data:array[1..100,1..100]oflongint;n,i,j,k,min,node:longint;beginassign(input,'dijkstra.in');assign(output,'dijkstra.out');reset(input);rewrite(output);fillchar(data,sizeof(data),0);fillchar(state,sizeof(state),0);readln(n);fori:=1tondoforj:=1tondobeginread(data[i,j]);ifdata[i,j]=0thendata[i,j]:=maxint;end;state[1]:=true;fork:=2tondobeginmin:=maxint;｛查找權(quán)值最小的點(diǎn)為node｝node:=1;fori:=2tondoif(data[1,i]<min)and(state[i]=false)thenbeginmin:=data[1,i];node:=i;end;｛更新其他各點(diǎn)的權(quán)值｝state[node]:=true;forj:=1tondoif(data[1,node]+data[node,j]<data[1,j])and(state[j]=false)thendata[1,j]:=data[1,node]+data[node,j];end;fori:=1ton-1doifdata[1,i]<>maxintthenwrite(data[1,i],'')elsewrite(-1,'');writeln(data[1,n]);close(input);close(output);end.測試樣例

dijkstra算法原理詳解如下圖，設(shè)A為源點(diǎn)，求A到其他各頂點(diǎn)（B、C、D、E