無向圖最短路徑

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