哈密頓回路課程實驗報告

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

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