馬步遍歷問題與騎士巡游問題的回溯算法_第1頁
馬步遍歷問題與騎士巡游問題的回溯算法_第2頁
馬步遍歷問題與騎士巡游問題的回溯算法_第3頁
全文預(yù)覽已結(jié)束

下載本文檔

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領(lǐng)

文檔簡介

1、馬步遍歷問題與騎士巡游問題的回溯算法【摘要】馬步遍歷問題與騎士巡游（knights tour）問題是指在有8 8方格的國際象棋棋盤上進行奇異的騎士“L型”（L-shaped）移動的問題。而騎士巡游問題實際是帶有約束條件的馬步遍歷問題，因此在用程序求解的時候可以一并求解。本文給出求解這一問題的回溯算法之C+語言程序。論文關(guān)鍵詞：騎士巡游,回溯算法,C+語言一般地說，我們用如下方法表示一個解：即把數(shù)字0，1，63放入棋盤中的方格來表示到達這些方格的順序。解決騎士巡游問題更具創(chuàng)意的方法之一是由J. C. Warnsdorff在1823年提出的。其規(guī)則是：騎士總是移向具有最少出口且沒有到達過的方格之一

2、。由于騎士巡游問題實際是帶有約束條件的馬步遍歷問題，因此在用程序求解的時候可以一起求解。程序算法依然是回溯法，和皇后問題有相似之處。馬步遍歷和騎士巡游問題的復(fù)雜度較高，求出一個解相對容易，但要求出所有的解是要花一定時間的。一、回溯算法的實現(xiàn)1為解決這個問題，我們把棋盤的橫坐標定為i，縱坐標定為j。i和j的取值范圍是從到SIZE。當某個騎士占了位置(i，j)時，其在這個位置上可以向8個方向以“L型”移動，它們分別是：方向1：i+2，j+1；方向2：i+1，j+2；方向3：i-1，j+2；方向4：i-2，j+1；方向5：i-2，j-1；方向6：i-1，j-2；方向7：i+1，j+2；方向8：i+2，j-1。2棋盤以二維數(shù)組表示，其下標最大值8，將騎士的每一步按1，2，3 64填入數(shù)組相應(yīng)單元。其過程如下：for(int i=0;i8;i+)for(int j=0;j8;j+)trajKTij=0;作者簡介 王力強（1965- ），江蘇省常州市武進區(qū)人，陜西省城市經(jīng)濟學(xué)校財務(wù)科長，工程師。for(int e=0; e=curPointSub; e+)trajKTmoveTraje.Location.x_posmoveTraje.Location.y_pos

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論