問題描述:
馬的遍歷問題。在８×８方格的棋盤上，從任意指定方格出發(fā)，為馬尋找一條走遍棋盤每一格并且只經(jīng)過一次的一條路徑。
分析:
1.可以根據(jù)深度優(yōu)先搜索求解.
回朔法
#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.優(yōu)化之后的算法:
在每個結(jié)點對其子結(jié)點進(jìn)行選取時，優(yōu)先選擇‘出口’最小的進(jìn)行搜索，‘出口’的意思是在這些子結(jié)點中它們的可行子結(jié)點的個數(shù)，也就是‘孫子’結(jié)點越少的越優(yōu)先跳，為什么要這樣選取，這是一種局部調(diào)整最優(yōu)的做法，如果優(yōu)先選擇出口多的子結(jié)點，那出口少的子結(jié)點就會越來越多，很可能出現(xiàn)‘死’結(jié)點（顧名思義就是沒有出口又沒有跳過的結(jié)點），這樣對下面的搜索純粹是徒勞，這樣會浪費很多無用的時間，反過來如果每次都優(yōu)先選擇出口少的結(jié)點跳，那出口少的結(jié)點就會越來越少，這樣跳成功的機(jī)會就更大一些。這種算法稱為為貪心算法，也叫貪婪算法或啟發(fā)示算法，它對整個求解過程的局部做最優(yōu)調(diào)整，它只適用于求較優(yōu)解或者部分解，而不能求最優(yōu)解。這樣的調(diào)整方法叫貪心策略，至于什么問題需要什么樣的貪心策略是不確定的，具體問題具體分析。實驗可以證明馬遍歷問題在運用到了上面的貪心策略之后求解速率有非常明顯的提高，如果只要求出一個解甚至不用回溯就可以完成，因為在這個算法提出的時候世界上還沒有計算機(jī)，這種方法完全可以用手工求出解來，其效率可想而知。
//簡單排序
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;
}
}
}
//計算節(jié)點的出口數(shù)(估值)
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++;//回塑次數(shù)
return false;
}
下載 參考文章:
http://www.programfan.com/blog/article.asp?id=4148