飛天

马踏棋盘问题

回朔法
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int nx[8]={-1,-1,1,1,-2,-2,2,2};
int ny[8]={-2,2,-2,2,-1,1,-1,1};

class Horse
{
     public:
         Horse(int m,int n);
         void start(int m,int n);
         void output();
         bool dfs(int m,int n,int step);
     private:
         int width,height,size;
         int **borad;
         int *data ;
         int step;
};
Horse::Horse(int m,int n):width(m),height(n),size(m*n),step(1)
{
     data=new int[size];
     borad=new int*[n];
     for(int i=0;i<height;i++)
     {
        borad[i]=data+i*n;
     }
     memset(data,0,size);
}
void Horse::output()
{
        for(int i=0;i<height;++i)
        {
                for(int j=0;j<width;++j)
                   printf("%2d ",borad[i][j]);
                cout<<endl;
        }
}

bool Horse::dfs(int m,int n,int step)
{
      if(borad[m][n]!=0) return false;
      borad[m][n]=step;
      if(step==size)//如果得到一个解,就推出.
         throw 1;
      int newx,newy;
      Node node[8];
      int len=0;
      for(int i=0;i<8;++i)
      {
          newx=m+nx[i];
          newy=n+ny[i];
          if(newx<0||newy<0||newx>=width||newy>=height)
             continue;
          dfs(newx,newy,step+1);
      }

      borad[m][n]=0;
      backcount++;
      return false;

}
//开始
void Horse::start(int m,int n)
{
     try
     {
     dfs(m,n,1);
     cout<<"no solve"<<endl;
     }
     catch(int)
     {
     cout<<"back:"<<backcount<<endl;
     output();
     }
}

int main(int argc, char* argv[])
{
        int m,n;
        cin>>m>>n;
        Horse horse(m,n);
        horse.start(0,0);
        system("pause");
        return 0;
}

      2.优化之后的算法:
      在每个结点对其子结点进行选取时，优先选择‘出口’最小的进行搜索，‘出口’的意思是在这些子结点中它们的可行子结点的个数，也就是‘孙子’结点越少的越优先跳，为什么要这样选取，这是一种局部调整最优的做法，如果优先选择出口多的子结点，那出口少的子结点就会越来越多，很可能出现‘死’结点（顾名思义就是没有出口又没有跳过的结点），这样对下面的搜索纯粹是徒劳，这样会浪费很多无用的时间，反过来如果每次都优先选择出口少的结点跳，那出口少的结点就会越来越少，这样跳成功的机会就更大一些。这种算法称为为贪心算法，也叫贪婪算法或启发示算法，它对整个求解过程的局部做最优调整，它只适用于求较优解或者部分解，而不能求最优解。这样的调整方法叫贪心策略，至于什么问题需要什么样的贪心策略是不确定的，具体问题具体分析。实验可以证明马遍历问题在运用到了上面的贪心策略之后求解速率有非常明显的提高，如果只要求出一个解甚至不用回溯就可以完成，因为在这个算法提出的时候世界上还没有计算机，这种方法完全可以用手工求出解来，其效率可想而知。

//简单排序
void Horse::sort(Node * node,int len)
{
        for(int i=0;i<len-1;i++)
          for(int j=i+1;j<len;j++)
          {
                if(node[i].value>node[j].value)
                {
                        Node temp=node[i];
                        node[i]=node[j];
                        node[j]=temp;
                }
          }
}
//计算节点的出口数(估值)
void Horse::ways_out(Node & node)
{
      int m,n;

      for(int i=0;i<8;++i)
      {
          m=node.x+nx[i];
          n=node.y+ny[i];
          if(m<0||n<0||m>=width||n>=height)
             continue;
          if(borad[m][n]==0)
                node.value++;
      }
}

bool Horse::dfs(int m,int n,int step)
{
      if(borad[m][n]!=0) return false;
      borad[m][n]=step;
      if(step==size)         
         throw 1;
      int newx,newy;
      Node node[8];
      int len=0;
      for(int i=0;i<8;++i)
      {
          newx=m+nx[i];
          newy=n+ny[i];
          if(newx<0||newy<0||newx>=width||newy>=height)
             continue;

          node[len].x=newx;
          node[len].y=newy;
          node[len].value=0;
          ways_out(node[len]);
          len++;
          //dfs(newx,newy,step+1);
      }

      sort(node,len);
      for(int i=0;i<len;++i)
          dfs(node[i].x,node[i].y,step+1);

      borad[m][n]=0;
      backcount++;//回塑次数 
      return false;

}

posted on 2008-01-19 13:12 飛天 阅读(3777) 评论(2)  编辑 收藏 引用 所属分类: 算法描述