而更好的做法是运用“贪心策略”。
[贪心算法]
贪心算法（也叫贪婪算法）不是某种特定的算法，而是一类抽象的算法，或者说只是一种思想，它的具体表现在，对解空间进行搜索时，不是机械地搜索，而是对局部进行择优选取，贪心算法的目的不是为了找到全部解，也当然找不出最优解，而只是找出一种可行解，这样就会得到惊人的高效性。因此，贪心算法也叫启发式搜索，这种启发就是所谓的“贪心策略”。
以马踏棋盘问题为例，问题描述：在国际象棋的棋盘上指定一个初始马位置，一匹马从这个位置出发，经过不重复的走动，直到踏遍整个棋盘，输出一种可行路径。
对8×8的棋盘来说，马踏棋盘的解是一个天文数字，相当之多，而采用蛮干算法，求一个解的时候会非常吃力，因此采用贪心算法。这里选取的贪心策略是，在某个马位置顶点的后继顶点（子结点）中，择优选取那些出口更小的顶点进行搜索，出口的意思就是这个点能跳到的可行位置的路径数，这样的贪心策略是容易被人接受的，一开始往出口少的点跳，则往后出口多的点就多，能跳通的可能性就大，而事实也证明了，如果采用这样的策略在求一个解时几乎不需要回溯，对于更大的棋盘也如此。
#include "stdio.h"class horse{public: horse(int,int); ~horse(); void solve(int,int);protected: void dfs(int,int,int); int **data; int *head; int width; int height; int size; int count;};struct hnode{ int x; int y; int weight;};horse::horse(int n,int m){ width=n; height=m; size=n*m; head=new int[size]; data=new int*[m]; for(int i=0;i m;++i) { data[i]=head+i*n; for(int j=0;j n;++j) data[i][j]=0; }}horse::~horse(){ delete[] data; delete[] head;}void horse::solve(int x,int y){ try { count=0; dfs(x,y,1); printf("无解!\n回溯%d次\n",count); } catch(int) { for(int i=0;i height;++i) { printf("\n"); for(int j=0;j width;++j) printf(" %02d",data[i][j]); } printf("\n回溯%d次\n",count); }}void horse::dfs(int x,int y,int c){ static int dx[8]={-1,-1,1,1,-2,-2,2,2}; static int dy[8]={-2,2,-2,2,-1,1,-1,1}; hnode hn[8]; data[y][x]=c; if(c==size)throw(1); for(int i=0;i 8;++i) { int tx,ty; hn[i].x=tx=x+dx[i]; hn[i].y=ty=y+dy[i]; if(tx 0
tx =width
ty =height
data[ty][tx] 0) { hn[i].weight=-1;continue; } hn[i].weight=0; for(int j=0;j 8;++j) { int mx,my; mx=tx+dx[j]; my=ty+dy[j]; if(mx =0&&mx width&&my =0&&my height&&data[my][mx]==0) hn[i].weight++; } if(hn[i].weight==0) hn[i].weight=9; } for(i=0;i 7;++i) for(int j=i+1;j 8;++j) if(hn[i].weight hn[j].weight) { hnode temp=hn[i]; hn[i]=hn[j]; hn[j]=temp; } for(i=0;i 8;++i) if(hn[i].weight 0) dfs(hn[i].x,hn[i].y,c+1); data[y][x]=0; ++count;//回溯次数}void main(){ horse a(8,9);//width=8 * height=9的盘棋 a.solve(0,0);//初始棋子位置}
