回溯法求哈密爾頓回路試驗報告.doc

回溯法求哈密爾頓回路2014211053譚富林一. 實驗?zāi)康暮退惴ǚ治鲈囼災(zāi)康模和ㄟ^回溯的方法找出圖的一般哈密頓爾回路，并且能夠輸出結(jié)果。算法分析：回溯法是一個既帶有系統(tǒng)性又帶有跳躍性的的搜索算法。它在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結(jié)點出發(fā)搜索解空間樹。算法搜索至解空間樹的任一結(jié)點時，總是先判斷該結(jié)點是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結(jié)點為根的子樹的系統(tǒng)搜索，逐層向其祖先結(jié)點回溯。否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索?；厮莘ㄔ谟脕砬髥栴}的所有解時，要回溯到根，且根結(jié)點的所有子樹都已被搜索遍才結(jié)束。而回溯法在用來求問題的任一解時，只要搜索到問題的一個解就可以結(jié)束。這種以深度優(yōu)先的方式系統(tǒng)地搜索問題的解的算法稱為回溯法，它適用于解一些組合數(shù)較大的問題。哈密頓回路是從某頂點開始，經(jīng)過圖全部頂點一次回到起點的回路。二.實驗內(nèi)容1.編寫實現(xiàn)算法：給定n點，m條變，找出所有哈密爾頓回路。2.將輸出數(shù)據(jù)顯示在控制臺窗體中。3.對實驗結(jié)果進(jìn)行分析。三.實驗開發(fā)工具操作系統(tǒng)：windows8開發(fā)工具:Microsoft visual studio 2010開發(fā)語言:C+四.實驗操作程序的思路：創(chuàng)建一個N節(jié)點的連通圖輸入頂點N的值輸入連通圖的邊數(shù)創(chuàng)建每一條邊，構(gòu)成完整連通圖求出哈密爾頓回路的所有解程序的實現(xiàn)：#include#include#include/全局變量聲明int m=1; /用于標(biāo)志哈密爾頓回路的總個數(shù)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(請先創(chuàng)建一個n結(jié)點的連通圖graphnnn);printf(請輸入頂點n的值:);scanf_s(%d,&n);printf(圖中一共有幾條邊？請輸入以便我們創(chuàng)建圖:);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創(chuàng)建第%d條邊:n,i);printf(構(gòu)成此邊的一個頂點號(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);五實驗結(jié)果以及分析有哈密爾頓回路連通圖： 運行結(jié)果：無哈密爾頓回路連通圖：六.總結(jié)通過本次課程設(shè)計，本人對算法設(shè)計與分析基礎(chǔ)有了更深的認(rèn)識，基本掌握了回溯法求解一般哈密爾頓回路的算法思路以及編程原理，提高了程序開發(fā)