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