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

评论