飛天

馬踏棋盤問題

回朔法
#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 飛天 閱讀(3787) 評論(2)  編輯 收藏 引用 所屬分類: 算法描述