初探搜索算法

09.11.10 Programming >> a star , BFS , DFS , greed , search

(注:这是一篇学习笔记,其实是写的第2遍.昨晚3点多快要收尾时,电脑啪的一声关机了.当我想起用的编辑器是gedit时,一口鲜血很华丽地喷在屏幕上.只怪我手欠没用vim..因为得重新写一遍,所以很多地方简化了很多.你完全可以挑着想看的看,没有什么影响.)

宽度优先搜索

宽搜与深搜一道,是最简便的图搜索算法之一.这一算法也是其他很多重要的搜索算法的原型.诸如带贪婪的搜索,双向搜索,A*搜索等,其实都可以认为是基于宽度优先搜索的.之所以称之为宽度优先,是因为算法每次扩展的节点都是当前节点的直接后继,也就是说,算法首先搜索和s距离为k的所有节点,然后才搜索和s距离为k+1的所有节点.因此,宽搜找到的必定是最短路径.下面是宽度优先搜索的伪代码:

声明两个空的链表: Open 和 Closed.

将起始节点压入Open 表中.

While Open表非空:

移出Open表首元素X.

If X为目标节点:

跳出While循环,将X压入Closed表中,返回成功信息.

Else 继续.

For X的所有直接后继节点Y.

将Y压入Open表尾.

将X压入Closed表中.

End While

对于宽搜,我们并不关心其复杂度,因为宽搜实际上使用得并不多.当然,如果你有兴趣的话,可以参考<Artificial Intelligence : A Modern Approach>这本书.我们更多的是关心宽搜能解决些什么问题.用宽搜解决迷宫问题是数据结构课上的内容,下面的问题你可以思考下如何解决:

[题目]魔板(via: sicily 1150)由8个大小相同方块组成，分别用涂上不同颜色，用1到8的数字表示。

其初始状态是

1 2 3 4

8 7 6 5

对魔板可进行三种基本操作：

A操作（上下行互换）：

8 7 6 5

1 2 3 4

B操作（每次以行循环右移一个）：

4 1 2 3

5 8 7 6

C操作（中间四小块顺时针转一格）：

1 7 2 4

8 6 3 5

用上述三种基本操作，可将任一种状态装换成另一种状态。

编写一程序,对于给定的目标态,输入到达的最短路径上的所有基本操作序列.不能到达输出-1.

深度优先搜索

和宽度优先搜索不一样的是,深度优先搜索的搜索策略是尽可能深地搜索图.换句话说,深搜其实就是在搜索树的每一层始终先扩展一个子节点,不断地递归该过程,直到不能再牵及,然后才从当前节点返回到上一级节点,沿另一方向继续搜索.需要注意的是,深搜的搜索策略是不完备的,而且,深搜得到的解并不一定就是最优解.下面是深度优先搜索的伪代码(注意它与宽搜的异同):

声明两个空的链表: Open 和 Closed.

将起始节点压入Open 表中.

While Open表非空:

移出Open表首元素X.

If X为目标节点:

跳出While循环,将X压入Closed表中,返回成功信息.

Else 继续.

For X的所有直接后继节点Y.

将Y压入Open表首.

将X压入Closed表中.

End While

我们可以看到,深搜和宽搜的代码基本上是一样的,也许实现上,对于数据结构的选择可以会有略微不同.因为深搜得到的结果可能是局部最优的,因此除非深搜的完备性很清楚,一般用宽搜而不是深搜.

[题目]下面是一个来自<the art of java>的题目,你可以试着使用深搜解决它:

航班问题:一位顾客要预定一张从New York到Los Angeles的航班机票，下面是航班线路，请你为顾客找一种购票方案。

航班                                          距离
New York到Chicago           900英里
Chicago到Denver                1000英里
New York到Toronto           500英里
New York到Denver             1800英里
Toronto到Calgary               1700英里
Toronto到Los Angeles      2500英里
Toronto到Chicago              500英里
Denver到Urbana                1000英里
Denver到Houston              1000英里
Houston到Los Angeles    1500英里
Denver到Los Angeles       1000英里

带贪心的搜索

带贪心的搜索其实是指在搜索时,算法根据某信息进行贪心搜索.如dijkstra算法.它与A*算法类似,但是却没有使用启发函数.贪心算法和动态规划一样,更多的是一种思想,如何使用则需灵活选择.比如,在马周游问题中,可以每次选择8连节点(马最多可以跳往8个方向)中入度最小的那个节点进行扩展.这里,节点Y的入度指能跳到它的节点X的个数,已跳过的X不算.找出贪心策略需要有比较清晰的理解,最好的办法就是多做些题.

[题目] 马周游问题 (via: sicily 1152)

在一个5 * 6的棋盘中的某个位置有一只马,如果它走29步正好经过除起点外的其他位置各一次,这样一种走法则称马的周游路线,试设计一个算法,从给定的起点出发,找出它的一条周游路线.

为了便于表示一个棋盘,我们按照从上到下,从左到右对棋盘的方格编号,如下所示：

对输入的每一个起点,求一条周游线路.对应地输出一行,有30个整数,从起点开始按顺序给出马每次经过的棋盘方格的编号.

双向搜索

双向搜索是指搜索同时在正反两个方向进行,正反向定义为:

正向搜索:从起始节点向目标节点搜索
反向搜索:从目标节点向起始节点搜索

注意,双向搜索中,正反两个方向是交替进行的,当两个方向上搜索到同一子节点时,程序结束.该子节点我们一般称为"相交点",可以证明,如果存在从起始节点到目标节点的最优路径,那么双向搜索的两个方向必定相交,从起始节点到相交点再到目标节点的路径即是最优路径.双向搜索的伪代码如下:

创建Open队列和Closed队列

将起始节点压入Open队列,将目标节点压入Closed队列

While

移出Open队列首元素X

For X的所有直接后继节点Y

If Y是否已经搜索过

跳出While循环,输出成功信息

Else 将Y压入Open队列中

End For

移出Closed队列首元素X'

For X'的所有直接后继节点Y'

If Y'是否已经搜索过

跳出While循环,输出成功信息

Else 将Y'压入Closed队列中

End For

End While

使用双向搜索可以让程序更快,比如下面的八数码问题,如果双向搜索函数写的好的话,它甚至于比下文要介绍的A*算法还快,在sicily上提交,0.01秒过了,暴爽.

/* source code of submission 273100, Zhongshan University Online Judge System */
#include <stdlib.h>
#include <map>
#include <iostream>
#include <deque>
using namespace std;
 
deque<int> Dsrc,Ddes;
map<int,int> Msrc,Mdes;
 
int cur[9],nxt[9],zero,state,nxt_sta,floor,dir[4]={-1,1,-3,3};
 
void num2array(int s,int n[],int len)
{
     for(int i=len-1;i>=0;i--)
     {
       n[i]=s%10;
       s/=10;
     }
}
 
 
 
void array2num(int &s,int n[],int len)
{
    int res=0;
    for(int i=0;i<len;i++)
    {
        res=n[i]+res*10;
    }
    s=res;
}
 
void swap(int &x,int &y)
{
    int tmp=x;
    x=y;
    y=tmp;
}
 
bool isreachable(int sta[],int len)
{
    int res=0;
    for(int i=0;i<len;i++)
    {
        if(sta[i]==0)
            continue;
        for(int j=i+1;j<len;j++)
        {
            if(sta[j]==0)
                continue;
            if(sta[j]<sta[i])
                res++;
        }
    }
    return (res%2==0);
 
}
 
bool check(int pos,int i)
{
    switch (i)
    {
        case 1:
            if(pos!=0&&pos!=3&&pos!=6)
                return true;
            return false;
        case 2:
            if(pos!=2&&pos!=5&&pos!=8)
                return true;
            return false;
        case 3:
            if(pos!=0&&pos!=1&&pos!=2)
                return true;
            return false;
        case 4:
            if(pos!=6&&pos!=7&&pos!=8)
                return true;
            return false;
    }
}
 
void initial()
{
    Dsrc.clear();
    Ddes.clear();
    Msrc.clear();
    Mdes.clear();
    state=123456780;
    num2array(state,cur,9);
    Dsrc.push_back(state);
    floor=0;
    Msrc[state]=floor;
    for(int i=0;i<=8;i++)
        cin>>cur[i];
    for(int i=0;i<=8;i++)
        nxt[i]=0;
    array2num(state,cur,9);
    Ddes.push_back(state);
    floor=0;
    Mdes[state]=floor;
    nxt_sta=0;
    zero=0;
 
}
 
int find0(int sta[],int len)
{
    for(int i=0;i<len;i++)
        if(sta[i]==0)
            return i;
}
 
int solve()
{
    if(state==123456780)
        return 0;
    if(!isreachable(cur,9))
        return -1;
    int tmp;
    while(1)
    {
        while(Msrc[Dsrc.front()]==floor)
        {
            tmp=Dsrc.front();
            Dsrc.pop_front();
            num2array(tmp,cur,9);
            zero=find0(cur,9);
            for(int i=1;i<=4;i++)
            {
                for(int j=0;j<=8;j++)
                    nxt[j]=cur[j];
                if(check(zero,i))
                {
                    swap(nxt[zero],nxt[zero+dir[i-1]]);
                    array2num(nxt_sta,nxt,9);
                    if(Msrc.find(nxt_sta)!=Msrc.end())
                        continue;
                    if(Mdes.find(nxt_sta)!=Mdes.end())
                        return floor+Mdes[nxt_sta]+1;
                    Dsrc.push_back(nxt_sta);
                    Msrc[nxt_sta]=floor+1;
                }
            }
        }
        while(Mdes[Ddes.front()]==floor)
        {
            tmp=Ddes.front();
            Ddes.pop_front();
            num2array(tmp,cur,9);
            zero=find0(cur,9);
            for(int i=1;i<=4;i++)
            {
                for(int j=0;j<=8;j++)
                    nxt[j]=cur[j];
                if(check(zero,i))
                {
                    swap(nxt[zero],nxt[zero+dir[i-1]]);
                    array2num(nxt_sta,nxt,9);
                    if(Mdes.find(nxt_sta)!=Mdes.end())
                        continue;
                    if(Msrc.find(nxt_sta)!=Msrc.end())
                        return floor+Msrc[nxt_sta]+1;
                    Ddes.push_back(nxt_sta);
                    Mdes[nxt_sta]=floor+1;
                }
            }
        }
        floor++;
    }
 
}
 
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        initial();
        cout<<solve()<<endl;
    }
}

[题目]八数码问题(via: sicily 1378)求从初始状态，如下：

1 2 3

4 5 6

7 8 0

到某一目标状态所需的最少步数，每次可将0与某一相邻位置(上、下、左、右)的数字互换。

A*搜索

你可以参考这篇A*搜索相对完整的介绍: 对于A*算法的一些疑问,还有这篇,A*算法中启发函数的使用.

A*算法适用性很强,但要注意的是,相同的问题可以找出不同的启发函数,使用不同的启发函数的A*算法效率差别是很大的,更多的时候,我们必须在这些启发函数中找到较好的那一个,并且保证它是相容(consistent)的.A*算法的伪代码请参考上面的两个链接,下面直接给出一道例题.

[题目] Rush Hour (via: rush hour 本地下载)

 
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <map>
using namespace std;
 
#define max 6+1 // for every map[][]
#define num 8+1 // num of cars
#define impossible 99999
 
int car[num]; // = 1 or 2,   1:left/right, 2:up/down
int map_tmp[max][max]; 
int map_nxt[max][max]; //temp for next map
int map_src[max][max]; // source of the map, only written once
int id;//id++ hash
double factor=1;
// store every car's position; pos_x[2] : start pos, pos_y[2] : end pos
struct Car_Pos
{
    int pos_x[2],pos_y[2];
}car_pos[num];
 
struct info
{
    int id;
    int father;
    int map[max][max];
    int route[2];// which car(route[0]) goes which dir(route[1]) comes to this map, 1:left 3:right 2:up 4:down
    double g,h,f;//f=g+h, and h is always fo car1
} info_tmp,info_src,info_nxt; // info_tmp is the father pf info_nxt
 
map<int,info> Mtable;
 
deque<struct info> Dopen,Dclosed;
 
int hash_id(int m[max][max]);
 
void initial()
{
    Dopen.clear();
    Dclosed.clear();
    Mtable.clear();
    for(int i=1;i<=max-1;i++) // from 1 to 100
    {
        for(int j=1;j<=max-1;j++) // from 1 to 100
        {
            cin>>map_src[i][j];
            info_src.map[i][j]=map_src[i][j];
        }
    }
 
	id=hash_id(map_src);	
    info_src.id=id; 
	info_src.father=-1; 
	info_src.g=0; // info_src.h=0; info_src.f=0;
	info_src.h=impossible;
	info_src.f=factor*info_src.h+info_src.g;
	if(Mtable.find(id)==Mtable.end())
	{
		Dopen.push_back(info_src);
		Mtable[id]=info_src;
	}
}
 
//whether the car in position (pos_x,pos_y) can expand to direction (dir) or not, true for yes, vice verse
bool check_dir(int pos_x,int pos_y,int dir,int m[max][max],int t) // dir:1/3/2/4, 1:left 3:right 2:up 4:down
{
    switch(dir)
    {
        case 1: // go left
			{
				if(pos_y>1)
				{
					if(m[pos_x][pos_y-1]==t)
						return true;
					else return false;
				}
				return false;
			}
        case 3: // go right				
			{           
				if(pos_y<max-1)
				{
					if(m[pos_x][pos_y+1]==t)
						return true;
					else return false;
				}
				return false;
			}
        case 2: // go up
			{
				if(pos_x>1)
				{
					if(m[pos_x-1][pos_y]==t)
						return true;
					else return false;
				}
				return false;
			}
        case 4: // go down				
			{
				if(pos_x<max-1)
				{
					if(m[pos_x+1][pos_y]==t)
						return true;
					else return false;
				}
				return false;
			}
    }        
}
 
void get_cars_info()
{    
    for(int i=1;i<=max-1;i++) // from 1 to 100
    {
        for(int j=1;j<=max-1;j++)// from 1 to 100
        {
            if(map_src[i][j]!=0)
            {
                int temp=map_src[i][j];
                for(int k=1;k<=4;k++)
                {
                    if(check_dir(i,j,k,map_src,temp))
                    {
						if(k%2==1)
							car[temp]=1;
						else 
							car[temp]=2;                      
						break;                        
                    }
                }                
            }            
        }
    }
 
}
 
// to calculate hash for every map,making sure no two maps shares same hash,and one map goes with one hash,actually it is more like a mess
int hash_id(int m[max][max])
{
	int id=0;
    for(int j=1;j<=max-1;j++)
    {
        for(int k=1;k<=max-1;k++)
        {
			int temp=j*max+k;   // no meaning,just a fun
			temp*=temp;         
			temp+=3;             
            id=id+m[j][k]*temp;
        }
    }
	return id;
}
 
void find_car1(int m[max][max],int &pos_x,int &pos_y) // car1 can only goes left or right, up or down is impossible
{
    for(int i=max-1;i>=0;i--) // from 100 to 1, to find car1 quicker using the hint before
    {
        for(int j=max-1;j>=0;j--) // from 100 to 1
        {
            if(m[i][j]==1) // car1 found
            {
                pos_x=i;
                pos_y=j;
                return;
            }
        }
    }    
}
 
int calc_h(struct info t) // calc h for t using its map infomation
{
    int pos_x,pos_y;
    find_car1(t.map,pos_x,pos_y); // the pos of car1
    int temp1=0,temp2=max-1-pos_y;
    for(int i=pos_y+1;i<=max-1;i++) // from pos_y+1 to 100
    {
        if(t.map[pos_x][i]!=0)
            temp1++;
    }
    return temp1+temp2;                
}
 
int cmp(const struct info &t1,const struct info &t2)
{
	if(t1.f!=t2.f)
	   return t1.f<t2.f;
	else
		return t1.h<t2.h;
}
 
void get_every_car_pos(int m[max][max])
{	
    for(int i=1;i<=max-1;i++) // get the left/right cars info
    {
        int j=1;
        while(j<=max-1)
        {
			// while(j<=max-1&& m[i][j]==0 )
            while(j<=max-1&& (m[i][j]==0 || car[m[i][j]]!=1))
            {
                j++;
            }
            if(j>max-1)
                break;
            int no_of_car=m[i][j];
            car_pos[no_of_car].pos_x[0]=i;
            car_pos[no_of_car].pos_x[1]=j;
            while(j<=max-1&&m[i][j]==no_of_car)
            {
                j++;
            }
            car_pos[no_of_car].pos_y[0]=i;
            car_pos[no_of_car].pos_y[1]=j-1;
		}
	}
 
    for(int i=1;i<=max-1;i++) // get the up/down cars info
    {
        int j=1;
        while(j<=max-1)
        {
			//while(j<=max-1&& m[j][i]==0 )
            while(j<=max-1&& (m[j][i]==0 || car[m[j][i]]!=2))
            {
                j++;
            }
            if(j>max-1)
                break;
            int no_of_car=m[j][i];
            car_pos[no_of_car].pos_x[0]=j;
            car_pos[no_of_car].pos_x[1]=i;
            while(j<=max-1&&m[j][i]==no_of_car)
            {
                j++;
            }
            car_pos[no_of_car].pos_y[0]=j-1;
            car_pos[no_of_car].pos_y[1]=i;
        }
    }        
}
 
void a_star()
{   
    while(1)
    {
		if(Dopen.size()==0){
			cout<<endl;
			cout<<"Sorry,Dead lock!"<<endl;
			return ;
		}
        //info_tmp=Dopen.front();
		deque<info>::iterator ptr;
		ptr=min_element(Dopen.begin(),Dopen.end(),cmp);
		info_tmp=(*ptr);
        Dclosed.push_back(info_tmp);
		//Dopen.pop_front();
		Dopen.erase(ptr);
 
        //if(the_end(info_tmp.map)==true)
		if(info_tmp.h==0)
        {
			cout<<endl;
            cout<<"The min moves will be : "<<info_tmp.g<<endl;
 
			vector<int>Vcar;
			vector<int>Vdir;
 
			while(info_tmp.father!=-1)
			{
				Vcar.push_back(info_tmp.route[0]);
				Vdir.push_back(info_tmp.route[1]);
				info_tmp=Mtable[info_tmp.father];
			}
 
			for(int i=Vcar.size()-1;i>=0;i--)
			{
 
				cout<<"Car"<<Vcar[i]<<" moves ";
 
				switch(Vdir[i])
				{
					case 2:
						cout<<"up"<<endl;
						break;
					case 4:
						cout<<"down"<<endl;
						break;					
					case 1:
						cout<<"left"<<endl;
						break;
					case 3:
						cout<<"right"<<endl;
						break;
				}
			}
 
 
            return ;
        }
 
        get_every_car_pos(info_tmp.map);
 
        for(int i=1;i<=num-1;i++)//	for every car
        {
            int pos_x[2]={car_pos[i].pos_x[0],car_pos[i].pos_x[1]};
            int pos_y[2]={car_pos[i].pos_y[0],car_pos[i].pos_y[1]};
 
            if(car[i]==1) // cari goes left/right
            {
                if(pos_x[1]>1&&info_tmp.map[pos_x[0]][pos_x[1]-1]==0) // cari goes left
                {
                    for(int j=1;j<=max-1;j++)
                    {
                        for(int k=1;k<=max-1;k++)
                        {
                            info_nxt.map[j][k]=info_tmp.map[j][k];
                        }
                    }
                    info_nxt.map[pos_x[0]][pos_x[1]-1]=i;
                    info_nxt.map[pos_y[0]][pos_y[1]]=0;
                    info_nxt.g=info_tmp.g+1;
                    info_nxt.h=calc_h(info_nxt);
                    info_nxt.f=info_nxt.g+factor*info_nxt.h;
                    info_nxt.father=info_tmp.id;
					id=hash_id(info_nxt.map);
                    info_nxt.id=id;
                    info_nxt.route[1]=1; // 1:left 3:right 2:up 4:down
					info_nxt.route[0]=i;
					if(Mtable.find(id)==Mtable.end())
					{
						Mtable[id]=info_nxt;
						Dopen.push_back(info_nxt);
					}
				}
 
                if(pos_y[1]<max-1&&info_tmp.map[pos_y[0]][pos_y[1]+1]==0) // cari goes right
                {
                    for(int j=1;j<=max-1;j++)
                    {
                        for(int k=1;k<=max-1;k++)
                        {
                            info_nxt.map[j][k]=info_tmp.map[j][k];
                        }
                    }
                    info_nxt.map[pos_y[0]][pos_y[1]+1]=i;
                    info_nxt.map[pos_x[0]][pos_x[1]]=0;
                    info_nxt.g=info_tmp.g+1;
                    info_nxt.h=calc_h(info_nxt);
                    info_nxt.f=info_nxt.g+factor*info_nxt.h;
                    info_nxt.father=info_tmp.id;
					id=hash_id(info_nxt.map);
                    info_nxt.id=id;
                    info_nxt.route[1]=3;// 1:left 3:right 2:up 4:down
					info_nxt.route[0]=i;
					if(Mtable.find(id)==Mtable.end())
					{
					    Mtable[id]=info_nxt;
						Dopen.push_back(info_nxt);
					}
                }
            }
            if(car[i]==2) // cari goes up/down
            {
                if(pos_x[0]>1&&info_tmp.map[pos_x[0]-1][pos_x[1]]==0) // cari goes up
                {
                    for(int j=1;j<=max-1;j++)
                    {
                        for(int k=1;k<=max-1;k++)
                        {
                            info_nxt.map[j][k]=info_tmp.map[j][k];
                        }
                    }
                    info_nxt.map[pos_x[0]-1][pos_x[1]]=i;
                    info_nxt.map[pos_y[0]][pos_y[1]]=0;                    
                    info_nxt.g=info_tmp.g+1;
                    info_nxt.h=calc_h(info_nxt);
                    info_nxt.f=info_nxt.g+factor*info_nxt.h;
                    info_nxt.father=info_tmp.id;
					id=hash_id(info_nxt.map);
                    info_nxt.id=id;
                    info_nxt.route[1]=2;// 1:left 3:right 2:up 4:down
					info_nxt.route[0]=i;
					if(Mtable.find(id)==Mtable.end())
					{
					    Mtable[id]=info_nxt;
						Dopen.push_back(info_nxt);
					}             
				}
 
                if( pos_y[0]<max-1 && info_tmp.map[pos_y[0]+1][pos_y[1]]==0) // cari goes down
                {
                    for(int j=1;j<=max-1;j++)
                    {
                        for(int k=1;k<=max-1;k++)
                        {
                            info_nxt.map[j][k]=info_tmp.map[j][k];
                        }
                    }
                    info_nxt.map[pos_y[0]+1][pos_y[1]]=i;
                    info_nxt.map[pos_x[0]][pos_x[1]]=0;
                    info_nxt.g=info_tmp.g+1;
                    info_nxt.h=calc_h(info_nxt);
                    info_nxt.f=info_nxt.g+factor*info_nxt.h;
                    info_nxt.father=info_tmp.id;
					id=hash_id(info_nxt.map);
                    info_nxt.id=id;
                    info_nxt.route[1]=4;// 1:left 3:right 2:up 4:down
					info_nxt.route[0]=i;
					if(Mtable.find(id)==Mtable.end())
					{
						Mtable[id]=info_nxt;
						Dopen.push_back(info_nxt);
					}
                }
            }
        }       
 
       // sort(Dopen.begin(),Dopen.end(),cmp);
		//push_heap(Dopen.begin(),Dopen.end(),cmp);
 
	}
}
 
int main()
{ 
	cout<<"Please input the map of "<<max-1<<"*"<<max-1<<": "<<endl;
    initial();
    get_cars_info();
    a_star();
    cout<<endl;
}

宽度优先搜索

深度优先搜索

带贪心的搜索

双向搜索

A*搜索

发表留言点击这里，取消回复

Hello

Search

Archives