無(wú)向圖最短路徑

-.z.一、問(wèn)題重述最強(qiáng)大腦中的收官蜂巢迷宮變態(tài)級(jí)挑戰(zhàn)，相信大家都嘆為觀(guān)止！最強(qiáng)大腦收官戰(zhàn)打響后，收視率節(jié)節(jié)攀升，就連蟻后也不時(shí)出題難為一下她的子民們。在動(dòng)物世界中，稱(chēng)得上活地圖的，除了蜜蜂，螞蟻當(dāng)仁不讓。在復(fù)雜多變的蟻巢中，螞蟻總是能以最快、最高效的方式游歷在各個(gè)儲(chǔ)藏間〔存儲(chǔ)食物〕。今天，她看完最新一期節(jié)目，又發(fā)布了一項(xiàng)新任務(wù)：小蟻同學(xué)，我需要玉米庫(kù)的玉米，再要配點(diǎn)水果，去幫我找來(lái)吧。小蟻正準(zhǔn)備出發(fā)，蟻后又說(shuō)：哎呀，回來(lái)，我還沒(méi)說(shuō)完呢，還有假設(shè)干要求如下：1.小蟻同學(xué)，你需要盡可能以最少的花費(fèi)拿到食物〔附件圖中路線(xiàn)上的數(shù)值表示每?jī)蓚€(gè)儲(chǔ)物間的花費(fèi)〕；2.小蟻同學(xué)，你最多只能經(jīng)過(guò)9個(gè)儲(chǔ)藏間拿到食物〔包含起止兩個(gè)節(jié)點(diǎn)，屢次通過(guò)同一節(jié)點(diǎn)按重復(fù)次數(shù)計(jì)算〕；3.小蟻同學(xué)，你必須經(jīng)過(guò)玉米間，水果間〔附件圖中標(biāo)綠色節(jié)點(diǎn)〕；4.別忘了，食蟻獸也在路上活動(dòng)呢，一旦與食蟻獸相遇，性命危矣！不過(guò)小蟻微信群公告已經(jīng)公布了敵人信息〔附件圖中標(biāo)紅色路段〕；5.最后，千萬(wàn)別忘了，還有兩段路是必須經(jīng)過(guò)的，那里有我準(zhǔn)備的神秘禮物等著你呢(附件圖中標(biāo)綠色路段)。這下小蟻犯難了，這和它們平時(shí)找食物的集體活動(dòng)規(guī)則不一樣嘛,看來(lái)這次需要單獨(dú)行動(dòng)了。要怎么選路呢？小蟻經(jīng)過(guò)一番苦思冥想，稿紙堆了一摞，啊，終于找到了！親愛(ài)的同學(xué)們，你們能否也設(shè)計(jì)一種通用的路徑搜索算法，來(lái)應(yīng)對(duì)各種搜索限制條件，找到一條最優(yōu)路徑，順利完成蟻后布置的任務(wù)呢？注：1、蟻巢，有假設(shè)干個(gè)儲(chǔ)藏間〔附件圖中圓圈表示〕，儲(chǔ)藏間之間有諸多路可以到達(dá)(各儲(chǔ)藏間拓?fù)鋱D見(jiàn)附件);2、節(jié)點(diǎn)本身通行無(wú)花費(fèi)；3、該圖為無(wú)向圖，可以正反兩方向通行，兩方向都會(huì)計(jì)費(fèi)，并且花費(fèi)一樣；4、起止節(jié)點(diǎn)分別為附件圖中S點(diǎn)和E點(diǎn)。5、最優(yōu)路徑：即滿(mǎn)足限制條件的路徑。圖1二、模型假設(shè)與符號(hào)說(shuō)明2.1模型假設(shè)1.因?yàn)轭}目中并未明確給出是否是從起始點(diǎn)開(kāi)場(chǎng)到達(dá)終止點(diǎn)，即從s到e，為防止歧義、方便計(jì)算，假設(shè)每條路徑都是從起點(diǎn)到終點(diǎn)；2.下文中說(shuō)到的點(diǎn)或點(diǎn)數(shù)均代表存儲(chǔ)室或存儲(chǔ)室數(shù)量；3.通過(guò)圖1各路段關(guān)系，可以假設(shè)，為得到最優(yōu)路徑，不會(huì)再?gòu)腘1、N2、N3走回起點(diǎn)。2.2符號(hào)說(shuō)明符號(hào)含義N最多經(jīng)過(guò)的點(diǎn)的個(gè)數(shù)x經(jīng)過(guò)的第n個(gè)點(diǎn)P第j個(gè)集合Pj個(gè)點(diǎn)中的第i的數(shù)值，即將要走向的下一個(gè)點(diǎn)P第j個(gè)點(diǎn)所有與其相鄰的點(diǎn)的集合APC和第k個(gè)點(diǎn)相鄰的點(diǎn)的總數(shù)i走過(guò)的第k個(gè)點(diǎn)集合元素的下標(biāo)，從0到APCi-F走第k條路所需要的總費(fèi)用f從編號(hào)為i的點(diǎn)到編號(hào)為j的點(diǎn)的費(fèi)用，即表3i行j列對(duì)應(yīng)的值表1三、問(wèn)題分析3.1整體分析題目的總體思路是在各種約束條件下求出一條從起點(diǎn)到終點(diǎn)的最優(yōu)路徑，最優(yōu)可以說(shuō)是有兩個(gè)方面：第一是經(jīng)過(guò)的儲(chǔ)藏室即經(jīng)過(guò)的點(diǎn)最好，題目中給定為9個(gè)，第二是在途中花費(fèi)的費(fèi)用最少。基于以上分析，我們決定建立無(wú)向圖最優(yōu)路徑模型，從通過(guò)的點(diǎn)數(shù)和費(fèi)用進(jìn)展優(yōu)化。3.2約束條件分析〔1〕題目中并未明確給出是從起始點(diǎn)到達(dá)終點(diǎn)〔即圖中給出的s和e〕，為了不產(chǎn)生歧義，以及方便計(jì)算，我們?cè)诩僭O(shè)中規(guī)定該路線(xiàn)是從起始點(diǎn)到達(dá)終點(diǎn)〔即圖1中給出的s和e〕?！?〕最多只能經(jīng)過(guò)9個(gè)儲(chǔ)藏室〔即9個(gè)點(diǎn)〕〔3〕必須經(jīng)過(guò)兩條綠色的路線(xiàn)，即必須經(jīng)過(guò)N2、N4、N13、N14，并且N2和N3相鄰，N13和N14相鄰。〔4〕必須經(jīng)過(guò)水果間和玉米間，即必須經(jīng)過(guò)N7和N12?！?〕不能經(jīng)過(guò)有食蟻獸的紅色路段，可以有兩種解決方法，第一：即N11和N12不能相鄰出現(xiàn)，第二：N11和N12之間沒(méi)有連線(xiàn)，沒(méi)有通路?！?〕所有的路都是可以雙向通行的。3.3可行性分析經(jīng)過(guò)約束條件的分析，我們發(fā)現(xiàn)，有八個(gè)特殊點(diǎn)〔N2、N4、N7、N12、N13、N14、〕必須經(jīng)過(guò)，則按照題目要求，只能再選擇一個(gè)非特殊點(diǎn)通過(guò)以完成該路徑，通過(guò)圖1分析，這顯然是無(wú)法完成的，經(jīng)過(guò)進(jìn)一步的分析與計(jì)算，我們發(fā)現(xiàn)在滿(mǎn)足以上約束條件的情況下，最少需要通過(guò)11個(gè)點(diǎn)才能完成任務(wù)〔相關(guān)計(jì)算與證明在4.3.1中給出〕。四、模型建立與求解4.1模型準(zhǔn)備影響實(shí)際問(wèn)題的因素很多，要解決實(shí)際問(wèn)題就要建立適當(dāng)?shù)哪Ｐ停纫阉媚Ｐ偷拇我蛩睾雎?，否則所得模型會(huì)因?yàn)闃?gòu)造復(fù)雜而失去可解性同時(shí)又不能把與實(shí)質(zhì)相關(guān)的因素忽略掉，而造成所得模型不能夠正確反映實(shí)際情況而失去可靠性。但假設(shè)是無(wú)法取得實(shí)際問(wèn)題的最優(yōu)解，只能在犧牲次要因素的條件下獲得最優(yōu)近似解。因此要對(duì)實(shí)際問(wèn)題進(jìn)展簡(jiǎn)化、確定變量和參數(shù)，并用*些"規(guī)律〞建起變量與參數(shù)間的數(shù)學(xué)模型。影響路線(xiàn)選擇因素很多：經(jīng)過(guò)儲(chǔ)藏間數(shù)量限制、必經(jīng)節(jié)點(diǎn)與路徑、危險(xiǎn)路徑阻礙、費(fèi)用最少。對(duì)于問(wèn)題中兩種不同決策變量最少節(jié)點(diǎn)與最少花費(fèi)建立兩種模型分別求出在側(cè)重點(diǎn)不同情況下的最優(yōu)解。經(jīng)過(guò)以上的問(wèn)題分析，針對(duì)此問(wèn)題應(yīng)該建立一個(gè)無(wú)線(xiàn)圖最優(yōu)路徑模型。4.2模型的建立與求解此模型是要找出從起始點(diǎn)到終點(diǎn)滿(mǎn)足約束條件，并且使得經(jīng)過(guò)的點(diǎn)最少、費(fèi)用最少，因此其核心表達(dá)式是一個(gè)由一個(gè)點(diǎn)指向另一個(gè)點(diǎn)的路線(xiàn)。4.2.1確定所有路線(xiàn)表達(dá)式x式〔1〕0式〔2〕i∈公式說(shuō)明：式〔1〕表示從x0到xN-1的所有點(diǎn)，用有向箭頭連起來(lái)，表示一條經(jīng)過(guò)了N的點(diǎn)的路徑，起始點(diǎn)顯而易見(jiàn)為x 式〔2〕與式〔1〕對(duì)應(yīng)，Pj[i]對(duì)應(yīng)xn，Pj[i]為xn確實(shí)定方法。比方此時(shí)走到x2點(diǎn)，則下一個(gè)點(diǎn)確實(shí)定必然與x2有關(guān)，具體由P2集合中的第i〔i從0到APC2-1公式意義： 從x0開(kāi)場(chǎng)，遍歷與它相鄰的所有點(diǎn)，并且每個(gè)點(diǎn)都嘗試走，走到下一個(gè)點(diǎn)，同樣遍歷與其相鄰的所有點(diǎn)，重復(fù)上述步驟，直到走到第N個(gè)點(diǎn)〔即編號(hào)為N-1的點(diǎn)〕，便不再繼續(xù)走，或者沒(méi)有走到第N個(gè)點(diǎn)，而是已經(jīng)走到了終點(diǎn)即e，也不再繼續(xù)走。這樣可以找到所有走過(guò)點(diǎn)數(shù)為N或者能到達(dá)終點(diǎn)的路徑點(diǎn)編號(hào)對(duì)應(yīng)符號(hào)與其相鄰點(diǎn)的總數(shù)列舉相鄰的點(diǎn)01234560P31231P32492P413453P425674P412595P72346910126P735781213147P33688P46714159P5145101110P459111211P39101612P55610131613P66121415161714P468131515P4813141716P41112131717P00表2各節(jié)點(diǎn)信息表4.2.2對(duì)路徑的篩選〔添加程序〕〔1〕限制經(jīng)過(guò)的最多點(diǎn)數(shù)為了保證程序能夠正常、快速地運(yùn)行，在第一步尋找路徑中其實(shí)已經(jīng)限制了最多經(jīng)過(guò)的點(diǎn)數(shù)，走到第N個(gè)點(diǎn)〔即編號(hào)為N-1的點(diǎn)〕，便不再繼續(xù)走，或者沒(méi)有走到第N個(gè)點(diǎn)，而是已經(jīng)走到了終點(diǎn)即e，也不再繼續(xù)走，這樣已經(jīng)保證了每條路走過(guò)的點(diǎn)數(shù)都限制在N個(gè)以?xún)?nèi)?！?〕經(jīng)過(guò)N7和N12 每條路走完之后，遍歷一下所有的點(diǎn)，看看其中是否有7和12這兩個(gè)值，沒(méi)有的話(huà)此路不滿(mǎn)足約束條件，否則繼續(xù)檢驗(yàn)其他條件。〔3〕經(jīng)過(guò)兩條綠的路線(xiàn) 首先可以確定2、4、13、14必須通過(guò)，就是必須有這兩個(gè)數(shù)值，其次，2和4,13和14還必須相鄰出現(xiàn)，才能說(shuō)明通過(guò)綠的路段?！?〕不經(jīng)過(guò)紅的的路線(xiàn)，兩種解決方案 第一：直接切斷N11和N12間的路線(xiàn)，在表2中編號(hào)為11的節(jié)點(diǎn)中不添加12這個(gè)相鄰節(jié)點(diǎn)，在編號(hào)為12的節(jié)點(diǎn)中不添加11這個(gè)相鄰節(jié)點(diǎn)，這樣所得到的路線(xiàn)絕對(duì)不會(huì)經(jīng)過(guò)紅色路段。第二：每條路走完之后，遍歷一下所有的點(diǎn)，尋找N12與N13是否相鄰出現(xiàn)過(guò)，假設(shè)出現(xiàn)過(guò)，這說(shuō)明經(jīng)過(guò)了紅色路段，否則，未經(jīng)過(guò)，符合約束條件，繼續(xù)檢驗(yàn)其他條件。 注：本算法用第一種解決方案實(shí)現(xiàn)！費(fèi)用分析經(jīng)過(guò)上述分析與計(jì)算，已經(jīng)求得了滿(mǎn)足所有約束條件并且經(jīng)過(guò)的點(diǎn)盡量少的路徑，接下來(lái)還需要考慮每條路徑的費(fèi)用?！?〕費(fèi)用計(jì)算設(shè)有一條符合條件的路徑如下x式〔3〕其費(fèi)用F式〔4〕〔2〕費(fèi)用排序?qū)⑺玫降穆窂桨凑沼?jì)算的費(fèi)用升序排序，每條路的費(fèi)用將會(huì)一目了然，結(jié)合通過(guò)的點(diǎn)數(shù)、費(fèi)用選取最優(yōu)路徑。點(diǎn)編號(hào)0123456789101112131415161700311000001000000001301010000000000000211012100000000000031010022100000000004012101000100000000500120010031030000060002010120002430007000100101000000000800000021000000130090400130000110000001000000100010120000011000000000110100010120000032000210200101300000040000020122114000000301000010100150000000030000210041600000000000111200117000000000000010410表3費(fèi)用表算法設(shè)計(jì) 核心代碼如下：voidfindMoreShortPath(intinde*,int*pointCount){inti; //將第一個(gè)點(diǎn)編號(hào)寫(xiě)入路徑信息實(shí)例 *(allPath[pathNum].pathPoint+(*pointCount)-1)=inde*; //如果已經(jīng)到最后一個(gè)點(diǎn)或者走過(guò)的點(diǎn)數(shù)超過(guò)POINT_COUNT_MA*，對(duì)此路徑進(jìn)展處理 if(*pointCount>=POINT_COUNT_MA*||inde*==END_INDE*) { //如果此時(shí)最后一個(gè)點(diǎn)的編號(hào)為最后一個(gè)點(diǎn)的，則繼續(xù)對(duì)此路徑進(jìn)展處理 if(inde*==END_INDE*) //判斷此路徑是否滿(mǎn)足約束條件，是則繼續(xù) if(checkPointOfPath()) { //給pathNum先加一，以防止覆蓋上一條符合條件的路徑pathNum++; //因?yàn)椴粫?huì)再?gòu)念^開(kāi)場(chǎng)遍歷，下一條路的前半局部與上一條路是一樣的 //因此將上一條路徑的信息賦給下一條路徑，分叉之后的路徑會(huì)在上邊被修改 for(i=0;i<POINT_COUNT_MA*;i++) *(allPath[pathNum].pathPoint+i)=*(allPath[pathNum-1].pathPoint+i); } }else //如果不滿(mǎn)足以上條件，繼續(xù)向前走 for(i=0;i<point[inde*].adjoinPointCount;i++) { //走過(guò)的點(diǎn)數(shù)加1 *pointCount=*pointCount+1; //繼續(xù)找findMoreShortPath(*(point[inde*].adjoinPoint+i),pointCount); //找完一次，走過(guò)的總點(diǎn)數(shù)減1 *pointCount=*pointCount-1; }}模型求解使用C語(yǔ)言編寫(xiě)程序求解，設(shè)計(jì)無(wú)向圖最短路徑算法，其核心是通過(guò)遞歸的思想求解。注：程序運(yùn)行結(jié)果詳見(jiàn)4.3對(duì)模型的檢驗(yàn)！ 1.經(jīng)過(guò)點(diǎn)數(shù)最少的路徑有兩條，費(fèi)用分別為14和16，路徑如下：s->2->4->5->12->6->7->8->14->13->e式〔5〕s->2->4->5->12->6->7->6->14->13->e式〔6〕2、費(fèi)用最少的路徑有兩條，第一條經(jīng)過(guò)12個(gè)點(diǎn)，第二條經(jīng)過(guò)13個(gè)點(diǎn)，費(fèi)用都為13，路徑如下：s->2->4->5->6->7->8->14->13->12->16->e式〔7〕s->2->5->4->2->3->7->8->14->13->12->16->e式〔8〕4.3對(duì)模型的檢驗(yàn)1.將N置為9或10時(shí)，程序運(yùn)行結(jié)果如下：圖3當(dāng)設(shè)置N為9或10時(shí)均未找到符合條件的路徑，說(shuō)明經(jīng)過(guò)最少點(diǎn)數(shù)為9或10時(shí)均無(wú)法完成此任務(wù)，而設(shè)置為11及以更多時(shí)，會(huì)找到符合條件的路徑。這些檢驗(yàn)結(jié)果驗(yàn)證了3.3可行性分析的正確性，按照原題約束條件，此題無(wú)解。2.將N置為11時(shí)，程序運(yùn)行結(jié)果如下：圖4 所以得出節(jié)點(diǎn)最少的路徑有兩條，費(fèi)用分別為14和16：分別是s->2->4->5->12->6->7->8->14->13->e式〔9〕s->2->4->5->12->6->7->6->14->13->e式〔10〕3.將N置為12時(shí)，程序運(yùn)行結(jié)果如下：圖5 共找到73條符合條件的路徑，其中經(jīng)過(guò)11個(gè)點(diǎn)的路徑已被標(biāo)出，費(fèi)用最少的情況為經(jīng)過(guò)12個(gè)點(diǎn)，費(fèi)用為13，可行路徑有一條，為：s->2->4->5->6->7->8->14->13->12->16->e式〔11〕4.將N置為13時(shí)，程序運(yùn)行結(jié)果如下：圖6共找到1018條符合條件的路徑，從結(jié)果可以看到，也能找到一條費(fèi)用最少的路徑，為13，路徑如下：s->2->5->4->2->3->7->8->14->13->12->16->e式〔12〕4.將N置為14時(shí)，程序運(yùn)行結(jié)果如下：圖7 由此運(yùn)行結(jié)果分析可知，經(jīng)過(guò)14個(gè)點(diǎn)以及14個(gè)點(diǎn)以上，不會(huì)再有費(fèi)用最少的路徑。五、模型評(píng)價(jià)5.1模型優(yōu)缺點(diǎn)5.1.1〔1〕算法中使用遞歸進(jìn)展路徑的檢索，這樣可以大大地提高代碼的運(yùn)行速度，即使數(shù)據(jù)比擬龐大，也能很快求解；〔2〕此模型看似是針對(duì)無(wú)向圖求解最優(yōu)路徑的模型，實(shí)際上針對(duì)有向圖同樣適用，并且計(jì)算起來(lái)更加快速，如何推廣位有向圖最優(yōu)路徑的模型在5.2模型改良中講到；〔3〕對(duì)此網(wǎng)絡(luò)的規(guī)模增大縮小都是適用的，只需要對(duì)矩陣進(jìn)展擴(kuò)大，填入新增加的數(shù)據(jù)，修改少量參數(shù)；〔4〕能夠列出除最優(yōu)路徑之外的其他很多路徑，這為尋找其他適宜的路徑提供了方便。5.1.2〔1〕暫時(shí)所有的數(shù)據(jù)都是直接從源代碼中陸入進(jìn)去的，這就需要使用此模型的人非常熟悉這個(gè)模型才能保證修改后的矩陣和常量不出問(wèn)題；〔2〕算法中，對(duì)約束條件進(jìn)過(guò)兩條綠線(xiàn)的判斷比擬繁瑣，修改時(shí)容易出錯(cuò)；〔3〕模型中參加的影響因比素較少，在投放到實(shí)際問(wèn)題中可能會(huì)出比擬大的偏差。5.2模型改良此模型此次計(jì)算是針對(duì)題目中的無(wú)向圖來(lái)設(shè)計(jì)與填充數(shù)據(jù)的，但是只要稍加改動(dòng)，便可以成為幾個(gè)無(wú)向圖最優(yōu)路徑算法。以此題目為例，假設(shè)只能從N2走到N4，則要修改的只有兩個(gè)地方，而且是點(diǎn)的信息矩陣，將N4相鄰點(diǎn)的個(gè)數(shù)減1，相鄰點(diǎn)中將2除去，這樣便實(shí)現(xiàn)的從N2到N4的單方向，其他節(jié)點(diǎn)也是一樣。完成了對(duì)無(wú)向圖的模型。參考文獻(xiàn)[1]姜啟源.數(shù)學(xué)模型.高等教育.2021.[2]ThmoasH.CormenCharlesE.LeisersonRonaldL.RivestCliffordStein著，殷建平，*云，王剛，*曉光，蘇朋，鄒恒明，王宏志譯.算法導(dǎo)論.機(jī)械工業(yè)，2021.01.附錄：源代碼如下：#include<stdio.h>//最大允許通過(guò)的點(diǎn)數(shù)#definePOINT_COUNT_MA* 14//最后一個(gè)點(diǎn)的下標(biāo)#defineEND_INDE* 17#defineBooleanint#defineTRUE 1#defineFALSE 0//節(jié)點(diǎn)構(gòu)造體，包含相鄰點(diǎn)的個(gè)數(shù)adjoinPointCount，以及對(duì)應(yīng)的各個(gè)相鄰點(diǎn)adjoinPointtypedefstructPOINT{intadjoinPointCount;intadjoinPoint[20];}POINT;//路徑構(gòu)造體，pathPoint用來(lái)保存符合條件的路徑，以及費(fèi)用allFaretypedefstructPATH{intpathPoint[POINT_COUNT_MA*];intallFare;}PATH;//在遍歷路徑時(shí)，符合條件的路徑編號(hào)intpathNum=0;//保存所有的符合條件的路徑信息PATHallPath[1000000];//點(diǎn)信息矩陣POINTconstpoint[18]={/*0*/ {3,1,2,3},/*1*/ {3,2,4,9},/*2*/ {4,1,3,4,5},/*3*/ {4,2,5,6,7},/*4*/ {4,1,2,5,9},/*5*/ {7,2,3,4,6,9,10,12},/*6*/ {7,3,5,7,8,12,13,14},/*7*/ {3,3,6,8},/*8*/ {4,6,7,14,15},/*9*/ {5,1,4,5,10,11},/*10*/ {4,5,9,11,12},/*11*/ {3,9,10,16},/*12*/ {5,5,6,10,13,16},/*13*/ {6,6,12,14,15,16,END_INDE*},/*14*/ {4,6,8,13,15},/*15*/ {4,8,13,14,END_INDE*},/*16*/ {4,11,12,13,END_INDE*},/*17*/ {0,0}};//費(fèi)用矩陣intconstpathFare[18][18]={/* 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17*//*0*/ {0, 3, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},/*1*/ {3, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},/*2*/ {1, 1, 0, 1, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},/*3*/ {1, 0, 1, 0, 0, 2, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},/*4*/ {0, 1, 2, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},/*5*/ {0, 0, 1, 2, 0, 0, 1, 0, 0, 3, 1, 0, 3, 0, 0, 0, 0, 0},/*6*/ {0, 0, 0, 2, 0, 1, 0, 1, 2, 0, 0, 0, 2, 4, 3, 0, 0, 0},/*7*/ {0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0},/*8*/ {0, 0, 0, 0, 0, 0, 2, 1, 0, 0, 0, 0, 0, 0, 1, 3, 0, 0},/*9*/ {0, 4, 0, 0, 1, 3, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0},/*10*/ {0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 2, 0, 0, 0, 0, 0},/*11*/ {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0},/*12*/ {0, 0, 0, 0, 0, 3, 2, 0, 0, 0, 2, 0, 0, 2, 0, 0, 1, 0},/*13*/ {0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 2, 0, 1, 2, 2, 1},/*14*/ {0, 0, 0, 0, 0, 0, 3, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0},/*15*/ {0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 2, 1, 0, 0, 4},/*16*/ {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 0, 0, 0, 1},/*17*/ {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 4, 1, 0},};//查找符合條件的路徑voidfindMoreShortPath(intinde*,int*pointCount);//檢查路徑是否符合條件BooleancheckPointOfPath(void);//計(jì)算費(fèi)用voidcaculateFare(void);//通過(guò)費(fèi)用排序voidsortPathByFare(void);//顯示路徑信息voidshowPath(void);voidshowPath(void){inti,j; if(pathNum!=0) for(i=0;i<pathNum;i++) { for(j=0;j<POINT_COUNT_MA*;j++) if(j==0)printf("第%4d條路線(xiàn)：%2d",i+1,*(allPath[i].pathPoint+j)); elseprintf("->%2d",*(allPath[i].pathPoint+j));printf("總費(fèi)用為：%d\n",allPath[i].allFare); } elseprintf("未找到符合的路徑！\n");}voidsortPathByFare(void){inti,j; PATHtemp; for(i=0;i<pathNum;i++) { for(j=i;j<pathNum;j++) { if(allPath[i].allFare>allPath[j].allFare) { temp=allPath[i];allPath[i]=allPath[j];allPath[j]=temp; } } }}voidcaculateFare(void){inti,j; for(i=0;i<pathNum;i++) { for(j=0;j<POINT_COUNT_MA*-1;j++) { //假設(shè)碰到兩個(gè)值相等的點(diǎn)，說(shuō)明已經(jīng)到終點(diǎn)，不再累加費(fèi)用 if(*(allPath[i].pathPoint+j)!=*(allPath[i].pathPoint+j+1))allPath[i].allFare+=pathFare[*(allPath[i].pathPoint+j)][*(allPath[i].pathPoint+j+1)]; } }}BooleancheckPointOfPath(void){inttemp; Booleancontain24=FALSE,contain7=FALSE,contain12=FALSE,contain1314=FALSE; for(temp=0;temp<POINT_COUNT_MA*;temp++) { //判斷是否經(jīng)過(guò)7和12 switch(*(allPath[pathNum].pathPoint+temp)) { case7:contain7=TRUE; break; case12:contain12=TRUE; break; } //判斷是否經(jīng)過(guò)兩條綠線(xiàn) if((*(allPath[pathNum].pathPoint+temp)==2) &&(*(allPath[pathNum].pathPoint+temp+1)==4)) contain24=TRUE; if((*(allPath[pathNum].pathPoint+temp)==4) &&(*(allPath[pathNum].pathPoint+temp+1)==2)) contain24=TRUE; if((*(allPath[pathNum].pathPoint+temp)==13) &&(*(allPath[pathNum].pathPoint+temp+1)==14)) contain1314=TRUE; if((*(allPath[pathNum].pathPoint+