蛮干算法的成功完全是借助于计算机运算的快速，如果问题的解比较少的时候使用起来是比较容易的。但当问题的解比较多，则不宜使用，常用的做法是剪枝，剪枝是一种形象的描述，因为按深搜的算法，图可以描述为与之对应的树或森林，而剪枝的意思就是去掉某些子树，为什么要去掉，这里要用到一个剪枝判断，判断的方法是具体问题具体分析，但是有一点是要考虑到的，剪枝的高效性是建立在判断的额外开销上的，如果这里的开销大，则剪枝只会宣告失败。 而更好的做法是运用“贪心策略”。 【贪心算法】 贪心算法（也叫贪婪算法）不是某种特定的算法，而是一类抽象的算法，或者说只是一种思想，它的具体表现在，对解空间进行搜索时，不是机械地搜索，而是对局部进行择优选取，贪心算法的目的不是为了找到全部解，也当然找不出最优解，而只是找出一种可行解，这样就会得到惊人的高效性。因此，贪心算法也叫启发式搜索，这种启发就是所谓的“贪心策略”。 以马踏棋盘问题为例，问题描述：在国际象棋的棋盘上指定一个初始马位置，一匹马从这个位置出发，经过不重复的走动，直到踏遍整个棋盘，输出一种可行路径。 对8×8的棋盘来说，马踏棋盘的解是一个天文数字，相当之多，而采用蛮干算法，求一个解的时候会非常吃力，因此采用贪心算法。这里选取的贪心策略是，在某个马位置顶点的后继顶点（子结点）中，择优选取那些出口更小的顶点进行搜索，出口的意思就是这个点能跳到的可行位置的路径数，这样的贪心策略是容易被人接受的，一开始往出口少的点跳，则往后出口多的点就多，能跳通的可能性就大，而事实也证明了，如果采用这样的策略在求一个解时几乎不需要回溯，对于更大的棋盘也如此。 C++代码：在（VC6上调试通过） #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);//初始棋子位置 }

评论