[算法]馬踏棋盤貪婪算法實現

馬踏棋盤問題:
   將中國象棋的馬放入8x8的棋盤中, 如何不重入的跳遍棋盤的每一格.

分析:
俗話說, 馬踩八方. 馬在每一點最多有8中走法.
下一步將跳到哪一點可用一個數組來表示 pos[8], 數據定義如下.
struct horse_way
{
  struct {
    int  x;
    int  y;
  } pos[8] ;
  int size ;      /*共有多少中走法*/
  int idx ;      /*目前選擇 , 如果死路, idx++,選另一條路*/
};

一共有64個格子,那就需要定義長度為64的struct horse_way數組.
  struct horse_way   way[64]
way[0] 存放第一步,
way[n]存放第[n]步


一步一步探測, 遇到死路(無路可跳), idx++,選下一條,   idx == size時, 退回上一步 .
回溯法的解法是這樣.
利用計算機的強大計算能力,  可走出一條正確的路.


馬可跳入的點有多個時,如何選擇算法更優?
有一中方法是選擇下一步出口最少的點. 即孫子最少的點.
具體做法是將可跳入點存入數組, 分別計算每一點下一步可入格點數 (child_cnt)
按child_cnt由小到到大排序.

網上一查,這就是所謂的貪婪法
我的理解是: 貪婪法  =   回溯法 +  路徑選擇算法.

在這個程序中, 用貪婪法計算, 大部分都不需要回溯.
從[0,0]  到[7,7] 計算出64個點的解法一共不超過1秒.

直接用回溯法某些點須幾秒,某些點要幾個小時.

附上所有的測試代碼 . 歡迎大家指正

文件:	chess.tar.gz
大小:	2KB
下载:	下载

 209 chess.c
 111 chess.h
 320 total

也可以这样理解:
如果将8x8的棋盘按1-64编上号, 可以将棋盘看做一个有64个点的无向图,
马的走法是每个点的边.
要求无重复遍历图.

阿飛
2007/12/18