密頓回路問題的回溯算法

1、 哈密頓回路問題： 解空間: A= (x1, x2, , xn)| x1=1, 2= xi=n, i= 2, , n其中，x1, x2, , xn表示G中的頂點(diǎn)序列。 解的約束條件：（設(shè)圖G用鄰接矩陣graph表示）(x1, x2, , xn)為哈密頓回路當(dāng)且僅當(dāng)graphxk-1, xk=1, k=2, 3, , n 且graphxn, x1=1且xixj (ij) 回溯算法：設(shè)置一個(gè)標(biāo)記數(shù)組tag1.n表示頂點(diǎn)是否在當(dāng)前生成的路徑上： tagi=1, 頂點(diǎn)i在當(dāng)前路徑上 tagi=0, 頂點(diǎn)i不在當(dāng)前路徑上注意：當(dāng)一個(gè)頂點(diǎn)退出當(dāng)前路徑時(shí)，該頂點(diǎn)的標(biāo)記應(yīng)復(fù)原為0。算法 HAMILTONIAN

2、輸入：正整數(shù)n和含n個(gè)頂點(diǎn)的連通圖G的鄰接矩陣graph。輸出：圖G的所有哈密頓回路, 若無哈密頓回路則輸出no solution。 x1=1 ; x2.n=0 /用x1.n表示搜索路徑, 從頂點(diǎn)1開始。tag1=1; for i=2 to n tagi=0/設(shè)頂點(diǎn)標(biāo)記初值。flag=hamilton( 2 )if not flag then output “no solution”/輸出無解 end HAMILTONIAN 過程 hamilton(k) /在已得到當(dāng)前路徑x1.k-1的情況下，求圖G的所有哈密 /頓回路并輸出，有解則返回true, 否則返回false。 t=false /用t

3、標(biāo)志是否有解。for i=2 to nxk=i /試將頂點(diǎn)i作為當(dāng)前路徑上的第k個(gè)頂點(diǎn)。 if route(k) then /當(dāng)前頂點(diǎn)可作為當(dāng)前路徑的下一頂點(diǎn)。 tagxk=1 /當(dāng)前頂點(diǎn)加入當(dāng)前路徑。if k=n then /找到一條哈密頓回路。 t=true；output x1.n /輸出當(dāng)前找到的哈密頓回路。else /x1.k是部分路徑。 t1= hamilton (k+1) /遞歸求后面所有的哈密頓回路 if t1 then t=true end iftagxk=0 /頂點(diǎn)xk退出當(dāng)前路徑。 end if end for return tend hamilton過程 route(k) /判斷當(dāng)前頂點(diǎn)xk是否可作為當(dāng)前路徑x1.k-1的下一頂點(diǎn), /是則返回true, 否則返回false。if (graphxk-1, xk=1)and (tagxk=0)and(kn or k=n and gra