蛮干算法的成功完全是借助于计算机运算的快速，如果问题的解比较少的时候使用起来是比较容易的。但当问题的解比较多，则不宜使用，常用的做法是剪枝，剪枝是一种形象的描述，因为按深搜的算法，图可以描述为与之对应的树或森林，而剪枝的意思就是去掉某些子树，为什么要去掉，这里要用到一个剪枝判断，判断的方法是具体问题具体分析，但是有一点是要考虑到的，剪枝的高效性是建立在判断的额外开销上的，如果这里的开销大，则剪枝只会宣告失败。

而更好的做法是运用“贪心策略”。

【贪心算法】
贪心算法（也叫贪婪算法）不是某种特定的算法，而是一类抽象的算法，或者说只是一种思想，它的具体表现在，对解空间进行搜索时，不是机械地搜索，而是对局部进行择优选取，贪心算法的目的不是为了找到全部解，也当然找不出最优解，而只是找出一种可行解，这样就会得到惊人的高效性。因此，贪心算法也叫启发式搜索，这种启发就是所谓的“贪心策略”。

以马踏棋盘问题为例，问题描述：在国际象棋的棋盘上指定一个初始马位置，一匹马从这个位置出发，经过不重复的走动，直到踏遍整个棋盘，输出一种可行路径。

对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);//初始棋子位置
}

评论