回溯法求哈密爾頓回路2014211053譚富林一. 實驗目的和算法分析試驗目的：通過回溯的方法找出圖的一般哈密頓爾回路，并且能夠輸出結果。算法分析：回溯法是一個既帶有系統性又帶有跳躍性的的搜索算法。它在包含問題的所有解的解空間樹中，按照深度優先的策略，從根結點出發搜索解空間樹。算法搜索至解空間樹的任一結點時，總是先判斷該結點是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結點為根的子樹的系統搜索，逐層向其祖先結點回溯。否則，進入該子樹，繼續按深度優先的策略進行搜索?；厮莘ㄔ谟脕砬髥栴}的所有解時，要回溯到根，且根結點的所有子樹都已被搜索遍才結束。而回溯法在用來求問題的任一解時，只要搜索到問題的一個解就可以結束。這種以深度優先的方式系統地搜索問題的解的算法稱為回溯法，它適用于解一些組合數較大的問題。哈密頓回路是從某頂點開始，經過圖全部頂點一次回到起點的回路。二.實驗內容1.編寫實現算法：給定n點，m條變，找出所有哈密爾頓回路。2.將輸出數據顯示在控制臺窗體中。3.對實驗結果進行分析。三.實驗開發工具操作系統：windows8開發工具:Microsoft visual studio 2010開發語言:C+四.實驗操作程序的思路：創建一個N節點的連通圖輸入頂點N的值輸入連通圖的邊數創建每一條邊，構成完整連通圖求出哈密爾頓回路的所有解程序的實現：#include#include#include/全局變量聲明int m=1; /用于標志哈密爾頓回路的總個數int n; /int x128;int graph128128;void nextvalue(int k)int j;while(1)xk=(xk+1)%(n+1);if(xk=0) return;if(graphxk-1xk)for(j=1;j=k-1;j+)if(xj=xk) break;if(j=k)if(kn|(k=n&graphxn1)return;void print(int x,int n)int i=1;printf(回路%d:,m);for(;i=n;i+)printf(%d ,xi);printf(n);m+;void hamiltonian(int k)while(1)nextvalue(k);if(xk=0) return;if(k=n)print(x,n);elsehamiltonian(k+1);void main()int i,j,e,a,b;printf(*哈密頓回路遞歸回溯算法*n);printf(*n);printf(請先創建一個n結點的連通圖graphnnn);printf(請輸入頂點n的值:);scanf_s(%d,&n);printf(圖中一共有幾條邊？請輸入以便我們創建圖:);scanf_s(%d,&e);for(i=1;i=n;i+)for(j=1;j=n;j+)graphij=0;for(i=1;i=e;i+)printf(n創建第%d條邊:n,i);printf(構成此邊的一個頂點號(1%d):,n);scanf_s(%d,&a);printf(另一個頂點號(1%d):,n);scanf_s(%d,&b);graphab=graphba=1;x1=1;for(i=2;i=n;i+)xi=0;printf(n以下為所求hamiltonian回路的所有解n);hamiltonian(2);五實驗結果以及分析有哈密爾頓回路連通圖： 運行結果：無哈密爾頓回路連通圖：六.總結通過本次課程設計，本人對算法設計與分析基礎有了更深的認識，基本掌握了回溯法求解一般哈密爾頓回路的算法思路以及編程原理，提高了程序開發