馬踏演算法

⑴ 求數據結構課程設計 馬踏棋盤 C語言

沒看見你說的是非遞歸的。

其實我也不懂，碰巧知道答案，在51CTO上下的。 不能插圖。
9.3 馬踏棋盤（1）
【題目要求】
國際象棋的棋盤為8*8的方格棋盤。現將"馬"放在任意指定的方格中，按照"馬"走棋的規則將"馬"進行移動。要求每個方格只能進入一次，最終使得"馬"走遍棋盤的64個方格。編寫一個C程序，實現馬踏棋盤操作，要求用1～64這64個數字標注馬移動的路徑，也就是按照求出的行走路線，將數字1，2，……64依次填入棋盤的方格中，並輸出。
國際象棋中，"馬"的移動規則如圖9-4所示。

圖9-4 "馬"的移動規則
如圖9-4所示，圖中實心的圓圈代表"馬"的位置，它下一步可移動到圖中空心圓圈標注的8個位置上，該規則叫做"馬走日"。但是如果"馬"位於棋盤的邊界附近，它下一步可移動到的位置就不一定有8個了，因為要保證"馬"每一步都走在棋盤中。
【題目分析】
馬踏棋盤的問題其實就是要將1，2，…，64填入到一個8*8的矩陣中，要求相鄰的兩個數按照"馬"的移動規則放置在矩陣中。例如數字a放置在矩陣的(i,j)位置上，數字a+1隻能放置在矩陣的(i-2,j+1)，(i-1,j+2)，(i+1,j+2)，(i+2,j+1)，(i+2,j-1)，(i+1,j-2)，(i-1,j-2)，(i-2,j-1)之中的一個位置上。將矩陣填滿並輸出。這樣在矩陣中從1，2…遍歷到64，就得到了馬踏棋盤的行走路線。因此本題的最終目的是輸出一個8*8的矩陣，在該矩陣中填有1，2…64這64個數字，相鄰數字之間遵照"馬走日"的規則。
解決馬踏棋盤問題的一種比較容易理解的方法是應用遞歸的深度優先搜索的思想。因為"馬"每走一步都是盲目的，它並不能判斷當前的走步一定正確，而只能保證當前這步是可走的。"馬"走的每一步棋都是從它當前位置出發，向下一步的8個位置中的1個行走（在它下一步有8個位置可走的情況下）。因此"馬"當前所走的路徑並不一定正確，因為它可能還有剩下的可選路徑沒有嘗試，如圖9-5所示。

圖9-5 "馬"的可選路徑
如圖9-5所示，假設最開始"馬"位於棋盤的(0,0)的位置，接下來"馬"有兩處位置可走，即(1,2)和(2,1)。這時"馬"是無法確定走2的位置最終是正確的，還是走3的位置最終是正確的。因此"馬"只能任意先從一個路徑走下去（例如從2的位置）。如果這條路是正確的，那當然是幸運的，如果不正確，則"馬"要退回到第一步，繼續從3的位置走下去。以後"馬"走的每一步行走都遵循這個規則。這個過程就是一種深度搜索的過程，同時也是一種具有重復性操作的遞歸過程。可以用一棵"探索樹"來描述該深度優先搜索過程，如圖9-6所示。

圖9-6 深度優先搜索過程
"馬"的行走過程實際上就是一個深度探索的過程。如圖9-6所示，"探索樹"的根結點為"馬"在棋盤中的初始位置（這里用4*4的棋盤示意）。接下來"馬"有兩種行走方式，於是根結點派生出兩個分支。而再往下一步行走，根結點的兩個孩子又能夠分別派生出其他不同的"行走路線"分支，如此派生下去，就得到了"馬"的所有可能的走步狀態。可以想見，該探索樹的葉子結點只可能有兩種狀態：一是該結點不能再派生出其他的"走步"分支了，也就是"馬"走不通了；二是棋盤中的每個方格都被走到，即"馬"踏遍棋盤。於是從該探索樹的根結點到第二種情況的葉結點構成的路徑就是馬踏棋盤的行走過程。
如何才能通過搜索這棵探索樹找到這條馬踏棋盤的行走路徑呢？可以採用深度優先搜索的方法以先序的方式訪問樹中的各個結點，直到訪問到葉結點。如果葉結點是第二種情況的葉結點，則搜索過程可以結束，因為找到了馬踏棋盤的行走路徑；如果葉結點為第一種情況的葉結點，即走不通了，則需要返回到上一層的結點，順著該結點的下一條分支繼續進行深度優先搜索下去。
因此在設計"馬踏棋盤"的演算法時可以借鑒前面講過的圖的深度優先遍歷演算法和二叉樹的先序遍歷演算法。但是在這里並不需要真正地構建這樣一棵探索樹，我們只需要借用探索樹的思想。在實際的操作過程中，所謂的探索樹實際就是深度優先搜索的探索路徑，每個結點實際就是當前的棋盤狀態，而所謂的葉結點要麼就是在當前棋盤狀態下，"馬"無法再進行下一步行走；要麼就是馬踏棋盤成功。該演算法描述可如下：
int TravelChess Board (int x,int y,int tag)
{
chess[x][y] = tag;
if(tag == 64) { return 1;}
找到"馬"的下一個行走坐標（x1,y1），如果找到返回flag=1,否則返回flag=0；
while(flag ){
if(TravelChessBoard (x1,y1,tag+1))return 1; /*遞歸調用TravelChess ， 從x1,y1向下搜索；如果從 x1,y1往下馬踏棋盤成功，返回1*/
else
繼續找到"馬"的下一個行走坐標（x1,y1），如果找到返回flag=1,否則返回flag=0；
}
if(flag == 0)
chess[x][y] = 0;
return 0;
}
9.3 馬踏棋盤（2）
http://book.51cto.com 2010-03-17 08:57 楊峰 清華大學出版社 我要評論(0)
摘要：《妙趣橫生的演算法（C語言實現）》第9章綜合題，，本章將列舉一些經典的綜合題編程實例。這些題目生動有趣，同時具有一定的難度，因此作者盡量做到講解深入淺出，把問題講透徹，講清楚。同時希望讀者能從中得到啟發，啟迪思維，提高自身的編程水平。本節為大家介紹馬踏棋盤。
標簽：妙趣橫生 C語言實現 妙趣橫生的演算法（C語言實現）

Oracle幫您准確洞察各個物流環節
9.3 馬踏棋盤（2）
該演算法中通過函數TravelChess()遞歸地搜索"馬"的每一種走法。其中參數x，y指定 "馬" 當前走到棋盤中的位置，tag是標記變數，每走一個棋盤方格，tag自動增1，它標識著馬踏棋盤的行走路線。
演算法首先將當前"馬"處在棋盤中的位置上添加標記tag，然後判斷tag是否等於64，如果等於64，說明這是馬踏棋盤的最後一步，因此搜索成功，程序應當結束，返回1。否則，找到"馬"下一步可以走到的位置(x1,y1)，如果找到這個位置坐標，flag置1，否則flag置0。
下面在flag為1的條件下（即找到x1,y1），遞歸地調用函數TravelChess()。也就是從x1,y1指定的棋盤中的位置繼續向下深度搜索。如果從x1,y1向下搜索成功，即程序一直執行下去，直到tag等於64返回1，那就說明"馬"已經踏遍棋盤（馬踏棋盤的過程是：先走到棋盤的(x,y）位置，再從(x1,y1)向下深度搜索，走遍全棋盤），於是搜索結束，返回1；否則繼續找到"馬"的下一個可以行走的坐標(x1,y1)，如果找到這個位置坐標，flag置1，並從(x1,y1)向下重復上述的遞歸搜索，否則flag置0，本次遞歸結束。
如果找遍當前位置(x,y)的下一個坐標(x1,y1)（一般情況是8種），但是從(x1,y1)向下繼續深度優先搜索都不能成功地"馬踏棋盤"（此時flag等於0），則表明當前所處的狀態並不處於馬踏棋盤的"行走路徑"上，也就是說"馬"本不應該走到(x,y)的位置上，因此將chess[x][y]置0，表明棋盤中該位置未被走過（擦掉足跡），同時返回0，程序退到上一層的探索狀態。
這里應當知道，所謂當前位置(x,y)的下一個坐標(x1,y1)是指"馬"下一步可以走到的地方，用坐標(x1,y1)返回。在探索樹中它處在(x,y)所在的結點的子結點中，如圖9-7所示。

圖9-7 (x,y)的下一個坐標(x1,y1)
當前位置(x,y)的下一個坐標(x1,y1)的可選個數由當前棋盤的局面決定。一般情況下是有8種可走的位置（如圖9-7所示），但是如果"馬"位於棋盤的邊緣（如圖9-7所示的探索樹的根結點）或者8個可選位置中有的已被"馬"前面的足跡所佔據，在這兩種情況下(x1,y1)的可選個數就不是8個了。
上述搜索演算法相當於先序遍歷探索樹，只不過它不一定是將探索樹完整地遍歷，而是當tag等於64時，也就是棋盤被全部"踏遍"時就停止繼續搜索了。
下面給出完整的程序清單供讀者參考。
程序清單9-3
/*--------------------------------- 9-3.c --------------------------*/
#include "stdio.h"
#define X 8
#define Y 8
int chess[X][Y];

int nextxy(int *x,int *y,int count) /*找到基於x、y位置的下一個可走的位置*/
{
switch(count)
{
case 0: if(*x+2<=X-1 && *y-1>=0 && chess[*x+2][*y-1]==0) {*x =*x+2;*y = *y-1;return 1; } break;
case 1: if(*x+2<=X-1 && *y+1<=Y-1 && chess[*x+2][*y+1]==0) {*x = *x+2; *y = *y+1 ;
return 1;}break;
case 2: if(*x+1<=X-1 && *y-2>=0 && chess[*x+1][*y-2]==0) {*x = *x+1; *y = *y-2; return 1;} break;
case 3: if(*x+1<=X-1 && *y+2<=Y-1 &&chess[*x+1][*y+2]==0) {*x = *x+1; *y = *y+2;
return 1;}break;
case 4: if(*x-2>=0 && *y-1>=0 && chess[*x-2][*y-1]==0) {*x = *x-2; *y = *y-1; return 1;} break;
case 5: if(*x-2>=0 && *y+1<=Y-1 && chess[*x-2][*y+1]==0){*x = *x-2; *y = *y+1; return 1;} break;
case 6:if(*x-1>=0 && *y-2>=0 && chess[*x-1][*y-2]==0) {*x = *x-1; *y = *y-2;return 1;}break;
case 7: if(*x-1>=0 && *y+2<=Y-1 && chess[*x-1][*y+2]==0) {*x = *x-1; *y = *y+2;
return 1;}break;
default: break ;
}
return 0;
}

int TravelChessBoard(int x,int y,int tag) /*深度優先搜索地"馬踏棋盤"*/
{
int xx1 = x, yy1 = y, flag = 0,a,b ,count = 0 ;
chess[x][y] = tag;
if(tag == X*Y) { return 1;}
flag = nextxy(&x1,&y1,count);
while(flag == 0 && count <7){
countcount = count + 1;
flag = nextxy(&x1,&y1,count);
}
while(flag ){
if(TravelChessBoard(x1,y1,tag+1))return 1;
xx1 = x;yy1 = y;
countcount = count +1;
flag = nextxy(&x1,&y1,count); /*尋找下一個(x,y)*/
while(flag == 0 && count <7){ /*循環地尋找下一個(x,y)*/
countcount = count + 1;
flag = nextxy(&x1,&y1,count);
}
}
if(flag == 0)
chess[x][y] = 0;
return 0;
}
main()
{
int i,j;
for(i=0;i<X;i++)
for(j=0;j<Y;j++)
chess[i][j] = 0;
if(TravelChessBoard(2,0,1)) {
for(i=0;i<X;i++) {
for(j=0;j<Y;j++)
printf("%d ",chess[i][j]);
printf("\n");
}
printf("The horse has travelled the chess borad\n");
}
else
printf("The horse cannot travel the chess board\n");
getche();
}
9.3 馬踏棋盤（3）
http://book.51cto.com 2010-03-17 08:57 楊峰 清華大學出版社 我要評論(0)
摘要：《妙趣橫生的演算法（C語言實現）》第9章綜合題，，本章將列舉一些經典的綜合題編程實例。這些題目生動有趣，同時具有一定的難度，因此作者盡量做到講解深入淺出，把問題講透徹，講清楚。同時希望讀者能從中得到啟發，啟迪思維，提高自身的編程水平。本節為大家介紹int nextxy(int *x,int *y,int count)。
標簽：妙趣橫生 C語言實現 妙趣橫生的演算法（C語言實現）

Oracle幫您准確洞察各個物流環節
9.3 馬踏棋盤（3）
【程序說明】
本程序中應用二維數組chess[8][8]作為8*8的棋盤，"馬"每走到棋盤的(i,j)處，就將當前的步數tag賦值給chess[i][j]。為了方便起見，將數組chess設置為外部變數。另外定義字元常量X，Y，它規定棋盤的大小。本程序清單中將X和Y都設置為8。
函數TravelChessBoard()是上述馬踏棋盤演算法的具體實現。本程序中初始的(x,y)位置為(2,0)，說明"馬"從chess[8][8]的chess[2][0]位置開始進行"馬踏棋盤"的。在函數TravelChessBoard()中要調用函數nextxy()。
int nextxy(int *x,int *y,int count)
函數nextxy()包含3個參數：x和y為傳遞下來的"馬"當前踏到棋盤上的位置，它是指針變數。變數count的作用是標記調用nextxy()過程的次數，根據count值的不同，返回基於(x,y)的下一個不同的坐標，以此來避免返回同一個坐標，真正實現尋找"針對當前位置(x,y)的下一個位置"的目的。函數nextxy()的作用是找到"馬"當前的位置(x,y)的下一個可以行走的位置，並通過指針修改x、y的內容，將下一個位置坐標用變數x、y返回。
"尋找(x,y)的下一個位置坐標"的操作通過代碼：
xx1 = x; yy1 = y; /*將坐標(x1,y1)初始化為當前訪問的坐標 (x,y)，因為(x,y)不能被改動*/
flag = nextxy(&x1,&y1,count); /*尋找(x,y)下一個位置坐標(x1,y1)*/
while(flag == 0 && count <7){ /*循環地尋找(x,y)的下一個坐標*/
countcount = count + 1;
flag = nextxy(&x1,&y1,count);
}
實現。程序最開始將(x1,y1)初始化為當前坐標(x,y)，因為"馬"的當前位置坐標(x,y)不能被輕易改動。然後將&x1、&y1作為函數nextxy的參數傳遞，並通過參數&x1和&y1返回當前坐標(x,y)的第count個下一個坐標(x1,y1)。只有當flag為1時，才表明找到了下一個坐標，於是循環可以停止。但是如果count的值超過了7，則說明無法找到(x,y)的下一個坐標，也就說明棋走不通了。所謂當前位置(x,y)的"下一個位置"，如圖9-8所示。

（點擊查看大圖）圖9-8 (x,y)的"下一個位置"示意
圖中實心的圓圈的坐標為(x,y)，它周圍的8個空心的圓圈1～8，為當前坐標(x,y)的可選的"下一個"坐標(x1,y1)。每次調用nextxy()都可能得到這8個坐標其中的一個，當參數count為i時，返回圓圈i所處的坐標。這樣就保證了不返回同一個坐標。
如果像本程序這樣將字元常量X和Y都設置為8，那麼程序就執行8*8的馬踏棋盤。但是這樣一來會非常費時，實踐證明應用本程序運算出8*8的馬踏棋盤的結果要花幾分鍾的時間。因此讀者在調試程序時可以通過設置X和Y的值減小棋盤的規格，從而更快地得到結果。
本程序的運行結果如圖9-9所示。

（點擊查看大圖）圖9-9 程序9-3的運行結果

⑵ 貪婪啟發式和貪婪演算法的區別是什麼

馬踏棋盤的問題很早就有人提出，且早在1823年，J.C.Warnsdorff就提出了一個有名的演算法。在每個結點對其子結點進行選取時，優先選擇『出口』最小的進行搜索，『出口』的意思是在這些子結點中它們的可行子結點的個數，也就是『孫子』結點越少的越優先跳，為什麼要這樣選取，這是一種局部調整最優的做法，如果優先選擇出口多的子結點，那出口少的子結點就會越來越多，很可能出現『死』結點（顧名思義就是沒有出口又沒有跳過的結點），這樣對下面的搜索純粹是徒勞，這樣會浪費很多無用的時間，反過來如果每次都優先選擇出口少的結點跳，那出口少的結點就會越來越少，這樣跳成功的機會就更大一些。這種演算法稱為為貪心演算法，也叫貪婪演算法或啟發式演算法，它對整個求解過程的局部做最優調整，它只適用於求較優解或者部分解，而不能求最優解。這樣的調整方法叫貪心策略，至於什麼問題需要什麼樣的貪心策略是不確定的，具體問題具體分析。實驗可以證明馬遍歷問題在運用到了上面的貪心策略之後求解速率有非常明顯的提高，如果只要求出一個解甚至不用回溯就可以完成，因為在這個演算法提出的時候世界上還沒有計算機，這種方法完全可以用手工求出解來，其效率可想而知。
貪心演算法當然也有正確的時候。求最小生成樹的Prim演算法和Kruskal演算法都是漂亮的貪心演算法。
貪心法的應用演算法有Dijkstra的單源最短路徑和Chvatal的貪心集合覆蓋啟發式
所以需要說明的是，貪心演算法可以與隨機化演算法一起使用，具體的例子就不再多舉了。其實很多的智能演算法（也叫啟發式演算法），本質上就是貪心演算法和隨機化演算法結合——這樣的演算法結果雖然也是局部最優解，但是比單純的貪心演算法更靠近了最優解。例如遺傳演算法，模擬退火演算法。

⑶ 馬踏棋盤程序解釋

實現馬走完8×8棋盤的路線；
分步解析：
（1）
step[9][3]={{0,0,0},{1,1,2},{2,1,-2},{3,-1,2},{4,-1,-2},
{5,2,1},{6,2,-1},{7,-2,1},{8,-2,-1}};設定馬可走的八個方向，第二維第一個是序號（沒什麼用），後兩個分別得X坐標，Y坐標增量；
（2）
for(i=1;i<=8;i++)
for(j=1;j<=8;j++)
for(k=1;k<=8;k++)
{
x=i;y=j;
x=x+step[k][1];
y=y+step[k][2];
if(x>=1&&x<=8&&y>=1&&y<=8)
a[i][j]++ ; /* initilize array */
}
初始化整個棋盤，a[i][j]表示馬在（i，j）上可走的方向個數；例如a[1][1]=2,說明馬如果在(1,1)只能走（2，3）和（3，2）；這步為後面做鋪墊；
（3）
for(z=1;z<=64;z++)
//標記棋盤的64個可達點，起點為1號，終點為64號，object[m][n]=z；

a[m][n]=0;//每走過一個點，就置該點為0，表示不能再走，（if(a[x][y]!=0) ）；
能走的話（a[i][j])!=0)就選一個小於min的點if(a[x][y]<min) 作為下一步棋； 之所以要選一個a[i][j]最小的點牽扯到一些演算法，只有這樣才能保證走遍所有點並且不重復。
最後列印，不用說了吧。
大概我想說的就這些。