蛮干算法的成功完全是借助于计算机运算的快速,如果问题的解比较少的时候使用起来是比较容易的。但当问题的解比较多,则不宜使用,常用的做法是剪枝,剪枝是一种形象的描述,因为按深搜的算法,图可以描述为与之对应的树或森林,而剪枝的意思就是去掉某些子树,为什么要去掉,这里要用到一个剪枝判断,判断的方法是具体问题具体分析,但是有一点是要考虑到的,剪枝的高效性是建立在判断的额外开销上的,如果这里的开销大,则剪枝只会宣告失败。
而更好的做法是运用“贪心策略”。
【贪心算法】
贪心算法(也叫贪婪算法)不是某种特定的算法,而是一类抽象的算法,或者说只是一种思想,它的具体表现在,对解空间进行搜索时,不是机械地搜索,而是对局部进行择优选取,贪心算法的目的不是为了找到全部解,也当然找不出最优解,而只是找出一种可行解,这样就会得到惊人的高效性。因此,贪心算法也叫启发式搜索,这种启发就是所谓的“贪心策略”。
以马踏棋盘问题为例,问题描述:在国际象棋的棋盘上指定一个初始马位置,一匹马从这个位置出发,经过不重复的走动,直到踏遍整个棋盘,输出一种可行路径。
对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<0||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);//初始棋子位置 }