哈密頓回路課程實驗報告

實用文檔《算法分析與設(shè)計》課程設(shè)計報告題目：哈密頓回路專業(yè)：計算機(jī)科學(xué)與技術(shù)班級：14計算機(jī)科學(xué)與技術(shù)二班姓名：陳凌志洪文豪楊旭指導(dǎo)教師：湛維明2016年5月22日河北金融學(xué)院課程設(shè)計報告目錄一、問題描述 3二、問題分析與解題思路 31．確定解題方法 32．用回溯法分析和解哈密頓回路問題 33.由以上解題思路作出基本思路圖： 4三、由基本思路圖編寫算法并實現(xiàn)可視化 51、源代碼 52、算法實現(xiàn)圖 7四、關(guān)于本次算法實驗的總結(jié) 8一、問題描述哈密頓圖是一個無向圖，由天文學(xué)家哈密頓提出，由指定的起點前往指定的終點，途中經(jīng)過的所有其他節(jié)點且只經(jīng)過一次。從一張普通圖中的任意一點出發(fā)，路途中經(jīng)過圖中每一個結(jié)點當(dāng)且僅當(dāng)一次的回路，稱為為哈密頓回路。要求：隨機(jī)生成無向圖，且圖中部分頂點間無通路。設(shè)計算法找到一條哈密頓回路。如果實現(xiàn)可視化展示給予大幅度額外加分。要滿足兩個條件：封閉的環(huán)，是一個連通圖，且圖中任意兩點可達(dá)。二、問題分析與解題思路1．確定解題方法由于哈密頓回路問題是一個完全NP問題，沒有多項式可解，所以我們用最簡單的回溯法找出哈密頓回路，并且能夠?qū)崿F(xiàn)可視化輸出?；厮莘ǖ幕舅悸罚夯厮莘ㄊ怯邢到y(tǒng)性和跳躍性的搜算算法。它在包含的問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結(jié)點出發(fā)搜索解空間樹。算法搜算至解空間樹的任一結(jié)點時，總是先判斷該結(jié)點是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結(jié)點為根的子樹的系統(tǒng)搜索，逐層向其祖先結(jié)點回溯。否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索?；厮莘ㄔ谟脕砬髥栴}的所有解時，要回溯到根，且根結(jié)點的所有子樹都已被搜索遍才結(jié)束。而回溯法在用來求問題的任一解時，只要搜索到問題的一個解就可以結(jié)束。這種算法比較適合哈密頓回路問題。

2．用回溯法分析和解哈密頓回路問題在求解哈密頓問題時，題目要求是求出一種可行的路徑，所以這個問題的解可能是由很多很多步驟構(gòu)成的，每一步可能還有不同的決策方向。是一個完全NP問題，沒有固定明確的數(shù)學(xué)解析方法。所以我們要用搜素的方法，從某一個初始狀態(tài)下出發(fā)，不斷的向下一個狀態(tài)搜索，以達(dá)到想要達(dá)到的最終目的，來得到我們想要的解。在搜索的過程中，由于這個圖本身的特點，會有走到某一個狀態(tài)就走不下去的時候，這個時候，我們就必須往回走，即回到上一步，再嘗試別的可能性，別的方向或路徑。這樣不斷的向前走，回溯，再向前，再回溯……直到最終得到解，或者由于原問題無解而一路回溯到出發(fā)點。在回溯法的搜索中要注意的是，我們并不需要嘗試搜索問題解空間里的所有可能方向和路徑，而是以深度優(yōu)先搜素的方式，沿著一條路徑盡可能的向前探索。哈密頓回路問題的解空間是一顆最大度為n的樹（n為原圖中的頂點數(shù)）。且該樹中只有第一個結(jié)點度為n，其余的結(jié)點都為n-1（因為它不必與自身相連）。在回溯法編寫代碼解決哈密頓問題的時候，我們需要判斷路能不能走，有沒有走過和有沒有這條路，所以我們用到字典。由于路在生成的時候沒有的路我們根本沒有生成，所以我們考慮頂點有沒有走過，將已經(jīng)走過的頂點寫進(jìn)字典，再搜素的時候如果遇到字典里面的頂點，說明已經(jīng)走過，此路不可行。初始化點和路3.由以上解題思路作出基本思路圖：初始化點和路判斷是否走判斷是否走完所有頂點否路徑變紅路徑變紅是判斷最后一個點到第一個點是否為通路判斷最后一個點到第一個點是否為通路輸出圖像輸出圖像走另一個點走另一個點否判斷下一個點是否走過判斷下一個點是否走過返回上一個點否返回上一個點繼續(xù)往前走是繼續(xù)往前走三、由基本思路圖編寫算法并實現(xiàn)可視化1、源代碼#-*-coding:utf8-*-importnetworkxasnximportmatplotlib.pyplotaspltimportrandom首先確定頂點的數(shù)量，路程長度初始化（用來記錄是否走完了所有點），記錄有幾條通路，點的標(biāo)簽（給各個頂點一個編號便于使用）和點的判斷條件（用0表示沒有走過。1表示已經(jīng)走過）等基本條件。n=6#en=0#路程長度count1=0#記錄有幾條通路dot=[aforainrange(1,n+1)]#點的標(biāo)簽dotJudgement=[1forainrange(1,n+1)]#點的判斷條件隨機(jī)按照50%的概率生成頂點間的路。edge=[]#邊f(xié)orxinrange(1,n+1):foryinrange(x,n+1):if(random.randint(1,10)<=5)&(x!=y):#按照50%的概率構(gòu)建路edge.append((x,y))count1+=1根據(jù)先前的問題分析描述生成字典。（為了更清楚的可視化，我們用紅色標(biāo)記出回路。）judgement=[1forzinrange(1,count1+1)]#判斷這條路是否走過colours=["b"forcinrange(1,count1+1)]#邊的顏色A={key:valforval,keyinzip(judgement,edge)}#把邊和判斷條件（是否走過）合成一個字典B={key:valforval,keyinzip(dotJudgement,dot)}#把點和判斷條件（是否走過）合成一個字典C={key:valforval,keyinzip(colours,edge)}#把邊和對應(yīng)顏色合成一個字典準(zhǔn)備工作寫完。核心算法如下：defHamilton(dot1,len1):a=dot1#記錄點if(len1==n-1):#如果路程走到盡頭if((1,dot1)inA.keys()):#判斷這個點到起點有沒有通路if(A[(1,dot1)]==1):#判斷這條路有沒有走過C[(1,dot1)]="r"#有則把路改為紅色returnTrueelse:returnFalseforcountinrange(2,n+1):if((dot1,count)inA):#判斷字典中是否有這個鍵if(B[count]==1):#如果這條路沒走過，且點沒走過B[count]=0#標(biāo)記點走過len1+=1#路程加一C[(dot1,count)]="r"#把路變?yōu)榧t色if(Hamilton(count,len1)):#遞歸，找到后直接returnreturnTruelen1-=1#沒找到則退回去B[count]=1#退回C[(dot1,count)]="b"#顏色改為藍(lán)色dot1=a#點也退回if((count,dot1)inA):#判斷字典中是否有這個鍵，字典生成的時候是小數(shù)在前，所以多一個if判斷，才能遍歷所有路徑if((B[count]==1)):#如果這條路沒走過，且點沒走過B[count]=0#標(biāo)記點走過len1+=1#路程加一C[(count,dot1)]="r"#把路變?yōu)榧t色#dot1=count#換點if(Hamilton(count,len1)):#遞歸，找到后直接returnreturnTruelen1-=1#沒找到則退回去B[count]=1#退回C[(count,dot1)]="b"#顏色改為藍(lán)色dot1=a#點也退回returnFalse完成可視化：defshow():G=nx.Graph()G.add_edges_from(edges)pos=nx.circular_layout(G)nx.draw_networkx_nodes(G,pos,node_size=200)nx.draw_networkx_edges(G,pos,edge_color=colour,width=3)plt.show()if(Hamilton(1,len)):edges=[eforeinC.keys()]colour=[]foryinedge:if(C[y]=="r"):colour.append("r")if(C[y]=="b"):colour.append("b")show()else:print("沒有哈密頓回路")G=nx.Graph()G.add_edges_from(edge)pos=nx.circular_layout(G)nx.draw_networkx_nodes(G,pos,node_size=200)nx.draw_networkx_edges(G,pos,width=2)plt.show()最后的運行結(jié)果圖如下（我們自定義的六個頂點，并給出了像最后一張圖那樣沒有形成哈密頓回路的例子）2、算法實現(xiàn)圖四、關(guān)于本次算法實驗的總結(jié)回溯法，即在包含問題的所有解的解空間樹中，按照深度優(yōu)先搜索的策略，從根結(jié)點出發(fā)深度探索解空間樹。當(dāng)探索到某一結(jié)點時，要先判斷該結(jié)點是否包含問題的解，如果包含，就從該結(jié)點出發(fā)繼續(xù)探索下去，如果該結(jié)點不包含問題的解，則逐層向其祖先結(jié)點回溯。（其實回溯法就是對隱式圖的深度優(yōu)先搜索算法）。若用回溯法求問題的所有解時，要回溯到根，且根結(jié)點的所有可行的子樹都要已被搜索遍才結(jié)束的方法。回溯法的一般解題步驟：（1）針對所給問題，定義問題的解空間；（2）確定易于搜索的解空間結(jié)構(gòu)； （3）以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪