精华内容
下载资源
问答
  • 8数码问题

    万次阅读 2012-07-02 22:07:44
    8数码问题,即在一个3×3的矩阵中有8个数(1至8)和一个空格,从一个状态转换到另一个状态,每次只能移动与空格相邻的一个数字到空格当中 AOJ-417-8数码 http://icpc.ahu.edu.cn/OJ/Problem.aspx?id=417 这题是求...

    8数码问题,即在一个3×3的矩阵中有8个数(1至8)和一个空格,从一个状态转换到另一个状态,每次只能移动与空格相邻的一个数字到空格当中

    AOJ-417-8数码

    http://icpc.ahu.edu.cn/OJ/Problem.aspx?id=417

    这题是求转化的最少步数,可用BFS解决,共有9!=362880种情况,关键是如何标记已经访问过的状态,保证每次搜索得到的状态都是最小的步数,这里可将字符串转化成对应的整数来处理,可用康托展开来节省存储空间

    康托展开: X=an*(n-1)!+an-1*(n-2)!+...+ai*(i-1)!+...+a2*1!+a1*0! 
    ai为在当前未出现的数字中是排在第几个(0<=ai<i)
    例如3 5 7 4 1 2 9 6 8 展开为
    X=2*8!+3*7!+4*6!+2*5!+0*4!+0*3!+2*2!+0*1!+0*0!=98884

    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    char a[363000][9];  //共有9!=362880种情况,用char存储节省空间
    char goal[9];
    char visit[363000];
    int dis[363000];
    int dir[4][2]={{-1,0},{1,0},{0,1},{0,-1}};
    int c[9]={1,1,2,6,24,120,720,5040,40320};
    int find(char str[9]) //将字符串转换成一个整数
    {
         int i,j,k;
    	 int f[10];
    	 int sum=0;
    	 memset(f,0,sizeof(f));
    	 for(i=0;i<9;i++)
    	 {
    		 k=0;
    		 for(j=0;j<8;j++)
    		 if(j<str[i]&&!f[j])
    	     k++;
    		 f[str[i]]=1;
    		 sum+=k*c[8-i];
    	 }
    	 return sum;
    }
    int bfs()
    {
    	int i,j,t,flag;
    	int head,tail;
    	int x,y,z;
    	int nx,ny,nz;
    	memset(dis,0,sizeof(dis));  //到每种状态的做小步数
     	memset(visit,0,sizeof(visit)); //标记过的点不能重复走
        t=find(a[0]);
    	visit[t]=1;
    	head=0;
    	tail=1;
        while(head<tail)
    	{
    		flag=1;
    		for(i=0;i<9;i++)
    		if(a[head][i]!=goal[i])   //和目标状态相同即停止搜索
    		{
    			flag=0;
    			break;
    		}
    		if(flag)
    		return dis[head];
    		for(i=0;i<9;i++)  //找到0所在位置
    		if(a[head][i]==0)
    		{
    			x=i/3;
    			y=i%3;
    			z=i;
    			break;
    		}
            for(i=0;i<4;i++)
    		{
    			nx=x+dir[i][0];
    			ny=y+dir[i][1];
    			nz=nx*3+ny;
    			if(0<=nx&&nx<3&&0<=ny&&ny<3)
    			{
    				for(j=0;j<9;j++)
    				a[tail][j]=a[head][j];
    				a[tail][z]=a[head][nz];  //做一次移动,即非0元素和0交换
    				a[tail][nz]=0;
                    t=find(a[tail]);
    				if(!visit[t])
    				{
    					visit[t]=1;
    					dis[tail]=dis[head]+1;
    					tail++;
    				}
    			}
    		}
    		head++;
    	}
    	return -1;
    }
    int main()
    {
    	int i,ans;
    	for(i=0;i<9;i++)
    	scanf("%d",&a[0][i]);
    	for(i=0;i<9;i++)
    	scanf("%d",&goal[i]);
    	ans=bfs();
    	if(ans==-1)
    	printf("Impossible\n");
        else
        printf("%d\n",ans);
        return 0;
    }
    

    POJ-1077-Eight

    http://poj.org/problem?id=1077

    这题不需要求最小步数,要求移动的路劲,和上题差不多,用BFS,再记录一下路劲,最后反向输出即可

    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    char a[363000][9];  //共有9!=362880种情况,用char存储节省空间
    char goal[9];
    char visit[363000];
    int dis[363000];
    int step[363000];  //从上一步来的方向
    int pre[363000];  //从上一步来的状态
    int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};  
    char name[4]={'d','u','r','l'};
    int c[9]={1,1,2,6,24,120,720,5040,40320};
    void init()
    {
    	int i;
    	for(i=0;i<8;i++)
    	goal[i]=i+1;
    	goal[8]=0;
    }
    int find(char str[9]) //将字符串转换成一个整数
    {
         int i,j,k;
    	 int f[10];
    	 int sum=0;
    	 memset(f,0,sizeof(f));
    	 for(i=0;i<9;i++)
    	 {
    		 k=0;
    		 for(j=0;j<8;j++)
    		 if(j<str[i]&&!f[j])
    	     k++;
    		 f[str[i]]=1;
    		 sum+=k*c[8-i];
    	 }
    	 return sum;
    }
    int bfs()
    {
    	int i,j,t,flag;
    	int head,tail;
    	int p,q,temp;
    	int x,y,z;
    	int nx,ny,nz;
    	char sol[5000];
    	memset(dis,0,sizeof(dis));  //到每种状态的做小步数
     	memset(visit,0,sizeof(visit)); //标记过的点不能重复走
    	memset(step,0,sizeof(step));
        t=find(a[0]);
    	visit[t]=1;
    	step[0]=pre[0]=-1;
    	head=0;
    	tail=1;
        while(head<tail)
    	{
    		flag=1;
    		for(i=0;i<9;i++)
    		if(a[head][i]!=goal[i])   //和目标状态相同即停止搜索
    		{
    			flag=0;
    			break;
    		}
    		if(flag)   //打印路劲
    		{
    			temp=0;
    		    while(head)
    			{
    				p=pre[head];  //前一步的状态
    				q=step[head];  //从上一步来的方向
    				sol[temp++]=name[q];
    				head=p;
    			}
    			for(i=temp-1;i>=0;i--)
    			printf("%c",sol[i]);
    			printf("\n");
    			return 1;
    		}
            for(i=0;i<9;i++)  //找到0所在位置
    		if(a[head][i]==0)
    		{
    			x=i/3;
    			y=i%3;
    			z=i;
    			break;
    		}
            for(i=0;i<4;i++)
    		{
    			nx=x+dir[i][0];  //移动0元素
    			ny=y+dir[i][1];
    			nz=nx*3+ny;
    			if(0<=nx&&nx<3&&0<=ny&&ny<3)
    			{
    				for(j=0;j<9;j++)
    				a[tail][j]=a[head][j];
    				a[tail][z]=a[head][nz];  //做一次移动,即非0元素和0交换
    				a[tail][nz]=0;
                    t=find(a[tail]);
    				if(!visit[t])
    				{
    					visit[t]=1;
    					dis[tail]=dis[head]+1;
    					pre[tail]=head; //从上一步来的状态
    					step[tail]=i;  //从上一步来的方向
    					tail++;
    				}
    			}
    		}
    		head++;
    	}
    	return -1;
    }
    int main()
    {
    	int i,k,ans;
    	char ss[50];
    	k=0;
        gets(ss);
    	for(i=0;i<strlen(ss);i++)
    	{
    		if('0'<=ss[i]&&ss[i]<='9')
    		a[0][k++]=(ss[i]-'0');
    		else if(ss[i]=='x')
    		a[0][k++]=0;
    	}
    	init();
    	ans=bfs();
    	if(ans==-1)
    	printf("unsolvable\n");
        return 0;
    }
    
    



    展开全文
  • 8数码问题的C++解决方案

    千次阅读 2015-07-31 16:34:25
    8数码问题的一套完整C++解决方案,包括启发式函数、搜索策略、界面显示

    本博客已经搬家!我已经在CSDN上重新注册了一个博客,该博客将不再使用,新博客地址:

    http://blog.csdn.net/YU_Xianguo/article

    -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------


    引子:我接触8数码问题是在研一的时候上的《人工智能》课上,在某一章节介绍完深度优先搜索、广度优先搜索、贪婪搜索、A*搜索四种经典搜索策略以后,章节后面的一道习题便是让学生编程求解8数码问题。书上并未给出答案,我当时用不同的搜索策略分别实现了程序求解,但是普遍效率不高。这两天闲来无事,再把以前的程序翻出来看,决定重写一个。

    程序界面:下图是程序运行的界面,程序从用户指定的状态开始搜索,直到找到目标状态。


    在8数码问题中,只有空格(用数字0表示)可以移动,它每移动一步就是和相邻的一个数码交换一次位置。


    上图左边的控制台上显示得的是(空格的)移动过程,经过20步以后达到目标状态,如上图右侧所示。顺便说下,鄙人的电脑是11年的ThinkPad E520,2.2GHz的i3处理器,32位win7系统。

    代码细节:关于8数码问题的一个重要结论是[1]:两个不同的状态序列的逆序数,若奇偶性一致,则二状态可以互达,否则不能互达。示例:状态序列230148675的逆序数(0不考虑)是1+1+3+1+1=7.

    算法C++源代码和编译过的(win7&winXp)exe文件均上传到了csdn资源,点此下载

    程序提供3中搜索模式可以在函数调用中确定:第一种是宽度优先搜索,搜索效率低(意味着需要更多的搜索时间和内存空间),但是保证找到全局最优解(步数最少);第二种是完全的启发式搜索,根据每个节点当前状态到目标状态的相似性来决定优先扩展哪个节点,该方法速度最快,但是一般找不到全局最优解;第三种方法是结合宽度优先的启发式搜索,即在启发函数中加入节点深度信息,这样的话再选择某个节点时需同时考虑其节点深度以及和目标的相似性,该方法搜索时间介于前两种方法之间,但是有很大概率找到全局最优解。上图显示的结果就是使用的第三中搜索策略得到的。

    程序提供2种启发式函数:第一种是计算有多少个不在正确位置上的数码的个数来作为当前节点和目标节点的相似性度量;第二种是为每个错误放置的数码,计算其到正确位置的城市距离,由这些距离之和作为相似性度量。上图的示例程序就是采用第二种启发式。为了计算效率,我将启发式函数的选择用宏来定义,如果需要修改启发函数,则需要修改一个宏变量,并重新编译程序。

    程序中保留了大多的灵活性:除了搜索模式和启发式函数可以修改以外,还可以定义不同的目标状态,如果需要以任意状态为目标,则需要:1)修改一个宏变量并重新编译程序(修改方法代码中有说明),使得代码允许其它的目标状态;2)在运行时,在main函数里设置新的目标状态。

    需要说明的是:本文示例图中的目标状态在计算上是最快捷的,首先取数很方便,一般地查看目标在第i个位置上的值,则需要访问数组goal[i],而这里goal[i]==i,故而无需访问数组;第二,要想知道数码n的目标位置,则需要找到goal[i]==n,然后row=i/3,col=i%3. 但是这里的话,row=n/3,col=n%3. 当我们用8位无符号整型来表示各个数码值(0~8)时,n/3和n%3操作是非常快的,比访问数组还快。

    程序还提供一种玩游戏模式,即用户自己通过W,S,A,D四个键分别控制空格往上、下、左、右四个方向移动一步,功能很简单,界面部分是用opencv做的。界面部分和搜索部分是完全分离的,demo文件中main函数部分显示了如何将它们组合使用。

    参考文献:

    [1] 用MFC动态编程实现8数码问题求解

    展开全文
  • 8数码问题解决方案

    千次阅读 2013-04-27 20:23:30
    8数码问题 问题简介: 所谓八数码问题是指这样一种游戏:将分别标有数字1,2,3,…,8的八块正方形数码牌任意地放在一块3×3的数码盘上。放牌时要求不能重叠。于是,在 3×3的数码盘上出现了一个空格。现在要求...

    8数码问题

    问题简介:
    所谓八数码问题是指这样一种游戏:将分别标有数字1,2,3,…,8的八块正方形数码牌任意地放在一块3×3的数码盘上。放牌时要求不能重叠。于是,在 3×3的数码盘上出现了一个空格。现在要求按照每次只能将与空格相邻的数码牌与空格交换的原则,将任意摆放的数码盘逐步摆成某种特殊的排列。如下图表示了 一个具体的八数码问题求解。

    问题分析:
    首先,八数码问题包括一个初始状态(START) 和 目标状态(END),所谓解八数码问题就是在两个状态间寻找一系列可过渡状态 (START->STATE1->STATE2->...->END)。这个状态是否存在就是我们要解决的第一个问题:

    Q1:每一个状态及每一次操作的表示方法?
    有许多表示方法,比如一个3*3的八数码盘可以压缩成一个int值表示,但不适用于15 puzzle或大于8 的puzzle问题。如果对空间要求很高,应该还可以再压缩。本文采用一个int表示的方法。
    表示方法如下:由于int的表示范围大于1e9,所以我们取一个int的低9位,为了方便寻找空格的位置,int的个位我们用来放空格的位置(1-9)。而前8位,按照行从上到下,列从左到右的顺序依次记录对应位置上的数字。例如:
    可以表示成 2 3 1 5 8 4 6 7 5 ,个位的5表示空格在第5位,前八位数按顺序记录。坐标转换公式为:
    num(压缩后的int) x y(求x行y列,1记起)1e(n)为 1乘10的n次
    int temp=(x-1)*3+y
    if temp > num%10 then return (num / 1e(9-temp+1)) %10
    else return (num / 1e(9-temp) )%10

    为了方便本文介绍,取目标状态为:1 2 3 4 5 6 7 8 9 即-->

    操作本文用 u r d l 分别表示 空格的向上 向右 向下 向左 四个操作。比如,在简介中的图包括两步操作 l d ,可能与平时玩这类游戏的习惯不符合,但这是为了和ACM例题相统一。

    对应地,每种操作引起的状态变化如下:
    r :num值++ l :num值--
    u :有点复杂
    int t0 = 9-num%10 + 1
    int t1 = num / 1e(t0)
    int t2 = t1%1000
    t1= t1- t2 + (t2 % 100) * 10 + t2 / 100
    t1*= 1e(t0)
    return (t1 + ( (num % t0) - 3))
    d :return前面同u操作, return返回 (t1 + ( (num % t0) + 3))

    Q2:判断是否存在中间状态使START 到达END?
    用组合数学的方法可以快速地进行判断,例如SOJ 2061题 2360题中都是关于此类的问题。但八数码的判断方法比他们简单多了。

    本文用的方法是计算排列的逆序数值,以2 3 1 5 8 4 6 7 5 为例子,5表示的是空格,不计算,那么求23158467 的逆序值为
    0 + 0 + 2 (1<2 1<3 ) + 0 + 0 + 1 ( 4<5 ) + 1 ( 6<8 ) + 1 ( 7<8 ) = 5
    目标状态1 2 3 4 5 6 7 8 9 的逆序自然就是0。

    两个状态之间是否可达,可以通过计算两者的逆序值,若两者奇偶性相同则可达,不然两个状态不可达。

    简单证明一下:
    l 和 r 操作,不会影响状态的逆序值,因为只会改变个位数(空格的位置)。
    u和d操作是使某个位置的数字 右/左 移两位。 由于数字序列的每一次移动会使逆序值奇偶性改变,所以 移动两次后奇偶性不变。
    所以 四个操作均不会影响序列的奇偶性。

    Q3:如何寻找一系列的中间状态及遇到的问题?
    要寻找这一系列中间状态的方法是搜索,但搜索很容易遇到时间和空间上的问题。以下就是搜索的基本原理:

    由1 3 7 2 4 6 8 5 2 状态可以衍生三个状态,假如选择了1 2 3 7 4 6 8 5 5 ,则又衍生三个状态,继续按某策略进行选择,一直到衍生出的新状态为目标状态END 为止。
    容易看出,这样的搜索类似于从树根开始向茎再向叶搜索目标叶子一样的树型状。由于其规模的不断扩大,其叶子也愈加茂密,最终的规模会大到无法控制。这样在空间上会大大加大搜索难度,在时间上也要消耗许多。

    在普通搜索中遇到以下问题:
    a 搜索中易出现循环,即访问某一个状态后又来访问该状态。
    b 搜索路径不佳便无法得到较好的中间状态集(即中间状态集的元素数量过大)。
    c 搜索过程中访问了过多的无用状态,这些状态对最后的结果无帮助。


    以上三个问题中,a为致命问题,应该它可能导致程序死循环;b和c是非致命的,但若不处理好可能导致性能急剧下降。


    Q4:怎样避免重复访问一个状态?
    最直接的方法是记录每一个状态访问否,然后再衍生状态时不衍生那些已经访问的状态了。思想是,给每个状态标记一个flag,若该状态flag = true则不衍生,若为false则衍生并修改flag为true。
    在某些算法描述里,称有两个链表,一个为活链表(待访问),一个为死链表(访问完)。每一次衍生状态时,先判断它是否已在两个链表中,若存在,则不衍生;若不存在,将其放入活链表。对于被衍生的那个状态,放入死链表。

    为了记录每一个状态是否被访问过,我们需要有足够的空间。八数码问题一共有9!,这个数字并不是很大,但迎面而来的另一个问题是我们如何快速访问这些状 态,如果是单纯用链表的话,那么在规模相当大,查找的状态数目十分多的时候就不能快速找到状态,其复杂度为O(n),为了解决这个问题,本文将采用哈希函 数的方法,使复杂度减为O(1)。
    这里的哈希函数是用能对许多全排列问题适用的方法。取n!为基数,状态第n位的逆序值为哈希值第n位数。对于空格,取其(9-位置)再乘以8!。例如,1 3 7 2 4 6 8 5 8 的哈希值等于:
    0*0! + 0*1! + 0*2! + 2*3! + 1*4! + 1*5! + 0*6! + 3*7! + (9-8)*8! = 55596 <9!

    具体的原因可以去查查一些数学书,其中1 2 3 4 5 6 7 8 9 的哈希值是0 最小,8 7 6 5 4 3 2 1 0 的哈希值是(9!-1)最大,而其他值都在0 到 (9!-1) 中,且均唯一。

    Q5:如何使搜索只求得最佳的解?
    普通的搜索称为DFS(深度优先搜索)。除了DFS,还有BFS,从概念上讲,两者只是在扩展时的方向不同,DFS向深扩张,而BFS向广扩张。在八数码 问题的解集树中,树的深度就表示了从初始态到目标态的步数,DFS一味向深,所以很容易找出深度较大的解。
    BFS可以保证解的深度最少,因为在未将同一深度的状态全部访问完前,BFS不会去访问更深的状态,因此比较适合八数码问题,至少能解决求最佳解的难题。

    但是BFS和DFS一样不能解决问题c ,因为每个状态都需要扩张,所以广搜很容易使待搜状态的数目膨胀。最终影响效率。


    Q6:该如何减少因广搜所扩张的与目标状态及解无关的状态?
    前面所说的都是从START状态向END状态搜索,那么,将END状态与START状态倒一下,其实会有另一条搜索路径(Q8策略三讨论),但简单的交换 END与START并不能缩小状态膨胀的规模。我们可以将正向与反向的搜索结合起来,这就是双向广度搜索。
    双向广搜是指同时从START和END两端搜,当某一端所要访问的一个状态是被另一端访问过的时候,即找到解,搜索结束。它的好处是可以避免广搜后期状态的膨胀。
    采用双向广度搜索可以将空间和时间节省一半!


    Q7:决定一个快的检索策略?
    双向广搜能大大减少时间和空间,但在有的情况下我们并不需要空间的节省,比如在Q4中已经决定了我们需要使用的空间是9!,所以不需要节省。这样我们可以把重点放在时间的缩短上。
    启发式搜索是在路径搜索问题中很实用的搜索方式,通过设计一个好的启发式函数来计算状态的优先级,优先考虑优先级高的状态,可以提早搜索到达目标态的时 间。A*是一种启发式搜索的,他的启发式函数f ' ()=g' () + h' () 能够应用到八数码问题中来。
    g' () ----- 从起始状态到当前状态的实际代价g*()的估计值,g' () >= g*()
    h' () ----- 从当前状态到目标状态的实际代价h*()的估计值,h' () <= h*()
    注意两个限制条件:
    (1)h' () <= h*() (2)任意状态的f '()值必须大于其父状态的f '()值,即f '()单调递增。

    其中,g' () 是搜索的深度, h' () 则是一个估计函数,用以估计当前态到目标态可能的步数。解八数码问题时一般有两种估计函数。比较简单的是difference ( Status a, Status b ), 其返回值是a 和b状态各位置上数字不同的次数。另一种比较经典的是曼哈顿距离 manhattan ( Status a, Status b ),其返回的是各个数字从a的位置到b的位置的距离(见例子)。

    例如状态 1 3 7 2 4 6 8 5 2 和状态 1 2 3 4 5 6 7 8 9 的difference 是5(不含空格)。而他的manhattan 距离是:
    1 (7d一次) + 1 (2u一次) + 2 (4l两次) + 3 (6r两次u一次) + 2 (5u一次l一次) = 9
    单个数字的manhattan应该小于5,因为对角的距离才4,若大于4则说明计算有误。

    无论是difference还是manhattan,估计为越小越接近END,所以优先级高。
    在计算difference和manhattan时,推荐都将空格忽略,因为在difference中空格可有可无,对整体搜索影响不大。

    本文后面的实现将使用manhattan 不计空格的方法。其实,每移动一步,不计空格,相当于移动一个数字。如果每次移动都是完美的,即把一个数字归位,那么START态到END态的距离就是 manhattan。反过来说,manhattan是START到END态的至少走的步数。
    回到f '()=g' ()+ h' (),其实广度搜索是h' ()=0的一种启发式搜索的特例,而深度搜索是 f ' ()=0 的一般搜索。h' ()对于优化搜索速度有很重要的作用。

    Q8:能否进一步优化检索策略?
    答案是肯定的。
    A*搜索策略的优劣就是看h' ()的决定好坏。前面列举了两个h' ()的函数,但光有这两个是不够的。经过实验分析,在f '()中,g '()决定的是START态到END态中求得的解距离最优解的距离。 而h' () 能影响搜索的速度。
    所以优化的第一条策略是,放大h' (),比如,让h '()= 10* manhattan(),那么f '()= g' ()+10*manhattan(),可能提高搜索速度。可惜的是所得的解将不再会是最优的了。
    为什么放大h'()能加快搜索速度,我们可以想象一下,h'()描述的是本状态到END态的估计距离,估计距离越短自然快一点到达END态。而 g' ()描述的是目前的深度,放大h' ()的目的是尽量忽略深度的因素,是一种带策略的深搜,自然速度会比广搜和深搜都快,而因为减少考虑了深度因素,所以离最优解就越来越远了。关于h' ()放大多少,是很有趣的问题,有兴趣可以做些实验试试。

    第二条是更新待检查的状态,由于A*搜索会需要一个待检查的序列。首先,在Q4已经提到用哈希避免重复访问同一状态。而在待检查队列中的状态是未完成扩张 的状态,如果出现了状态相同但其g '()比原g '()出色的情况,那么我们更希望的是搜索新状态,而不是原状态。这样,在待检查队列中出现重复状态时,只需更新其g'() 就可以了。

    第三条是注意实现程序的方法,在起初我用sort排序f '()后再找出权值最大的状态,而后发现用make_heap要更快。想一想,由于需要访问的接点较多,待访问队列一大那么自然反复排序对速度会有影响, 而堆操作则比排序更好。另一点是,实现更新待检查队列时的搜索也要用比较好的方法实现。我在JAVA的演示程序中用的PriorityQueue,可是结 果不是很令人满意。

    第四条优化策略是使用IDA*的算法,这是A*算法的一种,ID名为Iterative deepening是迭代加深的意思。思想是如下:
    顺便准备一个记录一次循环最小值的temp=MAX, h' 取 manhattan距离
    先估算从START态到END态的h'() 记录为MIN,将START放入待访问队列
    读取队列下一个状态,到队列尾则GOTO⑦
    若g'() > MIN GOTO ⑥
    若g'() + h'() > MIN 是否为真,真GOTO ⑥,否 GOTO ⑤
    扩展该状态,并标记此状态已访问。找到END态的话就结束该算法。GOTO ②
    temp = min(manhattan , temp),GOTO ③
    若无扩展过状态,MIN=temp (ID的意思在这里体现)从头开始循环GOTO ②

    第五条优化策略本身与搜索无关,在做题时也没能帮上忙,不过从理论上讲是有参考价值的。记得Q6中介绍的从END开始搜起吗?如果我们的任务是对多个 START 与END进行搜索,那么我们可以在每搜索完一次后记录下路径,这个路径很重要,因为在以后的搜索中如果存在START和END的路径已经被记录过了,那么 可以直接调出结果。
    从END搜起,可以方便判断下一次的START是否已经有路径到END了。当前一次搜索完时,其已访问状态是可以直接使用的,若START不在其中,则从待访问的状态链表中按搜索策略找下一个状态,等于接着上一次的搜索结果开始找。
    之所以没能在速度上帮上忙,是因为这个优化策略需要加大g' ()的比重,否则很容易出现深度相当大的情况,由于前一次搜索的策略与下一次的基本无关,导致前一次的路径无法预料,所以就会出现深度过大的情况。解决方法是加大g' ()。
    策略五类似给程序加一个缓冲区,避免重复计算。如果要做八数码的应用,缓冲区会帮上忙的。

    Q10:怎样记录找到的路径?
    当找到解的时候我们就需要有类似回退的工作来整理一条解路径,由于使用了不是简单的DFS,所以不能借助通过函数调用所是使用的程序栈。
    我们可以手工加一个模拟栈。在Q4中解决了哈希的问题,利用哈希表就能快速访问状态对应的值,在这里,我们把原来的bool值改为char或其他能表示一次操作(至少需要5种状态,除了u r l d 外还要能表示状态已访问)的值就行了。
    在搜索到解时,记录下最后一个访问的状态值,然后从读取该状态对应的操作开始,就像栈操作的退栈一样,不停往回搜,直到找到搜索起点为止。记录好栈退出来的操作值,就是一条路径。

    展开全文
  • 实验一 A*算法求解8数码问题 一、实验目的 熟悉和掌握启发式搜索的定义、估价函数和算法过程,并利用A*算法求解N数码难题,理解求解流程和搜索顺序。 二、实验原理 A*算法是一种启发式图搜索算法,其特点在于对...

    目录

    实验一 A*算法求解8数码问题

    一、实验目的

    二、实验原理

    三、实验结果

    四、实验总结

    附录代码

    推荐文章


    实验一 A*算法求解8数码问题

    一、实验目的

    熟悉和掌握启发式搜索的定义、估价函数和算法过程,并利用A*算法求解N数码难题,理解求解流程和搜索顺序。

    二、实验原理

    A*算法是一种启发式图搜索算法,其特点在于对估价函数的定义上。对于一般的启发式图搜索,总是选择估价函数f值最小的节点作为扩展节点。因此,f是根据需要找到一条最小代价路径的观点来估算节点的,所以,可考虑每个节点n的估价函数值为两个分量:从起始节点到节点n的实际代价g(n)以及从节点n到达目标节点的估价代价h(n),且hn≤h*n , h*n 为n节点到目的结点的最优路径的代价。

    图2.1  八数码问题的求解
    八数码问题是在3×3的九宫格棋盘上,摆有8个刻有1~8数码的将牌。棋盘中有一个空格,允许紧邻空格的某一将牌可以移到空格中,这样通过平移将牌可以将某一将牌布局变换为另一布局。针对给定的一种初始布局或结构(目标状态),问如何移动将牌,实现从初始状态到目标状态的转变。如下图2.1表示了一个具体的八数码问题求解。

    三、实验结果

    表3.1 不同启发函数h(n)求解8数码问题的结果比较

     

    启发函数h(n)

    不在位数

    将牌“不在位”的距离和

    0

    初始状态

    283604175

    283604175

    283604175

    目标状态

    123804765

    123804765

    123804765

    最优解

    最佳路径长度

    为:8

    最佳路径为:

    第1层的状态:

    2 8 3

    0 6 4

    1 7 5

    第2层的状态:

    2 8 3

    1 6 4

    0 7 5

    第3层的状态:

    2 8 3

    1 6 4

    7 0 5

    第4层的状态:

    2 8 3

    1 0 4

    7 6 5

    第5层的状态:

    2 0 3

    1 8 4

    7 6 5

    第6层的状态:

    0 2 3

    1 8 4

    7 6 5

    第7层的状态:

    1 2 3

    0 8 4

    7 6 5

    第8层的状态:

    1 2 3

    8 0 4

    7 6 5

    最佳路径长度

    为:8

    最佳路径为:

    第1层的状态:

    2 8 3

    0 6 4

    1 7 5

    第2层的状态:

    2 8 3

    1 6 4

    0 7 5

    第3层的状态:

    2 8 3

    1 6 4

    7 0 5

    第4层的状态:

    2 8 3

    1 0 4

    7 6 5

    第5层的状态:

    2 0 3

    1 8 4

    7 6 5

    第6层的状态:

    0 2 3

    1 8 4

    7 6 5

    第7层的状态:

    1 2 3

    0 8 4

    7 6 5

    第8层的状态:

    1 2 3

    8 0 4

    7 6 5

    最佳路径长度为:8

    最佳路径为:

    第1层的状态:

    2 8 3

    0 6 4

    1 7 5

    第2层的状态:

    2 8 3

    1 6 4

    0 7 5

    第3层的状态:

    2 8 3

    1 6 4

    7 0 5

    第4层的状态:

    2 8 3

    1 0 4

    7 6 5

    第5层的状态:

    2 0 3

    1 8 4

    7 6 5

    第6层的状态:

    0 2 3

    1 8 4

    7 6 5

    第7层的状态:

    1 2 3

    0 8 4

    7 6 5

    第8层的状态:

    1 2 3

    8 0 4

    7 6 5

    扩展节点数

    (不包括叶子节点)

    17

    8

    294

    生成节点数

    (包含叶子节点)

    33

    17

    470

    运行时间

    (迭代次数)

    220.00ms

    120.00ms

    1469.00ms

    四、实验总结

    1、画出A*算法求解N数码问题的流程图。

    根据A*算法的实验原理,f=g(n) +h(n) ;这样估价函数f(n)在g(n)一定的情况下,会或多或少的受距离估计值h(n)的制约,节点距目标点近,h值小,f值相对就小,能保证最短路的搜索向终点的方向进行, 因此f是根据需要找到一条最小代价路径的观点来估算节点的。设计A*算法的流程图如图4.1.1所示,按照流程图编写伪代码,进而编写完整的程序。其中OPEN表保存所有已生成而未考察的节点,CLOSED表中记录已访问过的节点。在扩展结点时,还需要考虑两个表即OPEN表和CLOSED表中是否存在了该节点的后继节点。具体编程思路参照算法4.1

    图4.1.1 A*算法求解八数码问题的流程图

     

    算法4.1

    将起始点加入open表

         当open表不为空时:

           寻找open表中f值最小的点current

           它是终止点,则找到结果,程序结束。

           否则,Open表移出current,对current表中的每一个临近点

               若它不可走或在close表中,略过

               若它不在open表中,加入。

               若它在open表中,计算g值,若g值更小,替换其父节点为current,更新

    它的g值。

         若open表为空,则路径不存在。

     

    2、分析不同的估价函数对A*算法性能的影响。

    对于同一问题启发函数h(n)可以有多种设计方法。在本次时实验中,通过选用“将牌不在位数”和“将牌‘不在位’的距离和”两种不同的启发函数,同时还编写了不考虑h值进行搜索,即不采用启发性搜索的算法(按照广度优先搜索的策略)。正如表3.1所示,我们通过将第一种和第二种启发函数对比,发现第二种启发函数优于第一种启发函数,将采用启发函数与不采用启发性函数对比发现,采用启发性函数远远优于不采用启发性函数。

    下面,以图4.2.2为例,分析第二种启发函数求解的过程。第二种启发函数为h(n)=将牌‘不在位’的距离和,初始时的值为6,将牌1:2,将牌2:1,将牌6:2,将牌7:1,将牌8:2。在实验结果演示(表3.1)时,并没有选取图4.3初始状态来比较不同启发函数以及不采用启发函数对求解效率的影响,而是选取了图4.2.1初始状态进行演示,因为图4.2.2的步骤较为复杂,对于不同启发函数对于实验结果和实验效率的影响较为明显。第三种启发函数是按照广度优先搜索的策略。

        

    图4.2.1 初始状态                 图4.2.2 A*算法求解八数码示意图

    3根据宽度优先搜索算法和A*算法求解八数码问题的结果,分析启发式搜索的特点。

    根据表3-1的结果,我们可以发现采用A*算法求解八数码问题时间以及搜索的节点数目远远小于采用宽度优先搜索算法,这说明对于八数码问题,选用的启发性信息有利于搜索效率的提高。但是理论上来讲,如果选用的启发性信息过强,则可能找不到最优解。

    4实验心得体会

    当时面对300行的代码时,不知从何处下手,通过查阅资料和请教老师,以及与同学深入探讨,仔细研究A*算法之后,才明白程序如何编写,各部分的函数如何构成。同时,通过本次实验,发现选用不同的启发函数,对于实验的结果有较大的影响。正如表3-1所示,选用第一或第二种(也就是采用A*算法)远远优于普通的广度优先搜索,同时,明显的感觉到第二种启发函数效率更高,更快的找到最优解。但是,在实验过程中,也遇到了一些问题,比如初始值的八数码初始值的选择对于实验结果的影响很大,在选取一些样例时,比如1,3,0,2,8,4,7,6,5,实验结果达到20000次依然没有停止,无法比较两种启发函数的优越性,鉴于时间原因,选取一些迭代次数较小就可以达到目标状态的样例进行验证,发现第二种结果优于第一种启发函数的结果。总的来说,实践出真知,只有把书上的理论知识运用到实践,才是真正地掌握。本次实验顺利完成,还是挺开心的。

    附录代码

    #include "iostream"  
    #include "stdlib.h"  
    #include "conio.h"  
    #include <math.h>
    #include <windows.h>
    #define size 3  
    using namespace std;  
    //定义二维数组来存储数据表示某一个特定状态  
    typedef int status[size][size];  
    struct SpringLink;  
      
    //定义状态图中的结点数据结构  
    typedef struct Node  
    {  
        status data;//结点所存储的状态 ,一个3*3矩阵 
        struct Node *parent;//指向结点的父亲结点  
        struct SpringLink *child;//指向结点的后继结点  
        struct Node *next;//指向open或者closed表中的后一个结点  
        int fvalue;//结点的总的路径  
        int gvalue;//结点的实际路径  
        int hvalue;//结点的到达目标的困难程度  
    }NNode , *PNode;  
      
      
    //定义存储指向结点后继结点的指针的地址  
    typedef struct SpringLink  
    {  
        struct Node *pointData;//指向结点的指针  
        struct SpringLink *next;//指向兄第结点  
    }SPLink , *PSPLink;  
      
      
    PNode open;  
    PNode closed;  
    //OPEN表保存所有已生成而未考察的节点,CLOSED表中记录已访问过的节点
      
    //开始状态与目标状态  
    /*
    status startt = {1,3,0,8,2,4,7,6,5};最佳路径为2   
    status startt = {1,3,0,2,8,4,7,6,5};迭代超过20000次,手动停止 
    status startt = {2,8,3,1,6,4,7,0,5}; 
    status startt = {2,8,3,6,0,4,1,7,5}; //实验报告
    */ 
    int t=0; //迭代次数,相当于运行时间 
    int count_extendnode=0;//扩展结点 
    int count_sumnode=0; //生成节点 
    status startt = {2,8,3,6,0,4,1,7,5}; //实验报告
    status target = {1,2,3,8,0,4,7,6,5};  
    //初始化一个空链表  
    void initLink(PNode &Head)  
    {  
        Head = (PNode)malloc(sizeof(NNode));  
        Head->next = NULL;  
    }  
      
      
    //判断链表是否为空  
    bool isEmpty(PNode Head)  
    {  
        if(Head->next == NULL)  
            return true;  
        else  
            return false;  
    }  
      
      
    //从链表中拿出一个数据  
    void popNode(PNode &Head , PNode &FNode)  
    {  
        if(isEmpty(Head))  
        {  
            FNode = NULL;  
            return;  
        }  
        FNode = Head->next;  
        Head->next = Head->next->next;  
        FNode->next = NULL;  
    }  
      
      
      
    //向结点的最终后继结点链表中添加新的子结点  
    void addSpringNode(PNode &Head , PNode newData)  
    {  
        PSPLink newNode = (PSPLink)malloc(sizeof(SPLink));  
        newNode->pointData = newData;  
      
        newNode->next = Head->child;  
        Head->child = newNode;  
    }  
      
      
    //释放状态图中存放结点后继结点地址的空间  
    void freeSpringLink(PSPLink &Head)  
    {  
        PSPLink tmm;  
      
        while(Head != NULL)  
        {  
            tmm = Head;  
            Head = Head->next;  
            free(tmm);  
        }  
    }  
      
      
    //释放open表与closed表中的资源  
    void freeLink(PNode &Head)  
    {  
        PNode tmn;  
      
        tmn = Head;  
        Head = Head->next;  
        free(tmn);  
      
        while(Head != NULL)  
        {  
            //首先释放存放结点后继结点地址的空间  
            freeSpringLink(Head->child);  
            tmn = Head;  
            Head = Head->next;  
            free(tmn);  
        }  
    }  
      
      
    //向普通链表中添加一个结点  
    void addNode(PNode &Head , PNode &newNode)  
    {  
        newNode->next = Head->next;  
        Head->next = newNode;  
    }  
      
      
    //向非递减排列的链表中添加一个结点(已经按照权值进行排序)  
    void addAscNode(PNode &Head , PNode &newNode)  
    {  
        
        PNode P;  
        PNode Q;  
      
        P = Head->next;  
        Q = Head;  
        while(P != NULL && P->fvalue < newNode->fvalue)  
        {  
            Q = P;  
            P = P->next;  
        }  
        //上面判断好位置之后,下面就是简单的插入了  
        newNode->next = Q->next;  
        Q->next = newNode;  
    }  
      
    /*
    //计算结点的 h 值  f=g+h. 按照不在位的个数进行计算 
    int computeHValue(PNode theNode)  
    {  
        int num = 0;  
      
        for(int i = 0 ; i < 3 ; i++)  
        {  
            for(int j = 0 ; j < 3 ; j++)  
            {  
                if(theNode->data[i][j] != target[i][j])  
                    num++;  
            }  
        }  
        return num;  
    }   
    
    //计算结点的 h 值  f=g+h. 按照将牌不在位的距离和进行计算 
    int computeHValue(PNode theNode)  
    {  
        int num = 0;  
      
        for(int i = 0 ; i < 3 ; i++)  
        {  
            for(int j = 0 ; j < 3 ; j++)  
            {  
                if(theNode->data[i][j] != target[i][j]&&theNode->data[i][j] !=0){
                	for(int ii=0;ii<3;ii++){
                		for(int jj=0;jj<3;jj++){
                			if(theNode->data[i][j] == target[ii][jj]){
                				num+=abs(ii-i)+abs(jj-j);
    							break; 
    						}
    					}
    				}
    			}
    			
            }  
        }  
        return num;  
    }  */ 
      
    //计算结点的f,g,h值  
    void computeAllValue(PNode &theNode , PNode parentNode)  
    {  
        if(parentNode == NULL)  
            theNode->gvalue = 0;  
        else  
            theNode->gvalue = parentNode->gvalue + 1;  
      
    //    theNode->hvalue = computeHValue(theNode);  
        theNode->hvalue = 0;  
        theNode->fvalue = theNode->gvalue + theNode->hvalue;  
    }  
      
      
      
    //初始化函数,进行算法初始条件的设置  
    void initial()  
    {  
        //初始化open以及closed表  
        initLink(open);  
        initLink(closed);  
      
        //初始化起始结点,令初始结点的父节点为空结点  
        PNode NULLNode = NULL;  
        PNode Start = (PNode)malloc(sizeof(NNode));  
        for(int i = 0 ; i < 3 ; i++)  
        {  
            for(int j = 0 ; j < 3 ; j++)  
            {  
                Start->data[i][j] = startt[i][j];  
            }  
        }  
        Start->parent = NULL;  
        Start->child = NULL;  
        Start->next = NULL;  
        computeAllValue(Start , NULLNode);  
      
        //起始结点进入open表	  
        addAscNode(open , Start);  
        
    }  
      
      
    //将B节点的状态赋值给A结点  
    void statusAEB(PNode &ANode , PNode BNode)  
    {  
        for(int i = 0 ; i < 3 ; i++)  
        {  
            for(int j = 0 ; j < 3 ; j++)  
            {  
                ANode->data[i][j] = BNode->data[i][j];  
            }  
        }  
    }  
      
      
    //两个结点是否有相同的状态  
    bool hasSameStatus(PNode ANode , PNode BNode)  
    {  
        for(int i = 0 ; i < 3 ; i++)  
        {  
            for(int j = 0 ; j < 3 ; j++)  
            {  
                if(ANode->data[i][j] != BNode->data[i][j])  
                    return false;  
            }  
        }  
        return true;  
    }  
      
      
      
    //结点与其祖先结点是否有相同的状态  
    bool hasAnceSameStatus(PNode OrigiNode , PNode AnceNode)  
    {  
        while(AnceNode != NULL)  
        {  
            if(hasSameStatus(OrigiNode , AnceNode))  
                return true;  
            AnceNode = AnceNode->parent;  
        }  
        return false;  
    }  
      
      
    //取得方格中空的格子的位置  
    void getPosition(PNode theNode , int &row , int &col)  
    {  
        for(int i = 0 ; i < 3 ; i++)  
        {  
            for(int j = 0 ; j < 3 ; j++)  
            {  
                if(theNode->data[i][j] == 0)  
                {  
                    row = i;  
                    col = j;  
                    return;  
                }  
            }  
        }  
    }  
      
      
    //交换两个数字的值  
    void changeAB(int &A , int &B)  
    {  
        int C;  
        C = B;  
        B = A;  
        A = C;  
    }  
      
      
    //检查相应的状态是否在某一个链表中  
    bool inLink(PNode spciNode , PNode theLink , PNode &theNodeLink , PNode &preNode)  
    {  
        preNode = theLink;  
        theLink = theLink->next;  
      
        while(theLink != NULL)  
        {  
            if(hasSameStatus(spciNode , theLink))  
            {  
                theNodeLink = theLink;  
                return true;  
            }  
            preNode = theLink;  
            theLink = theLink->next;  
        }  
        return false;  
    }  
      
      
      
    //产生结点的后继结点(与祖先状态不同)链表  
    void SpringLink(PNode theNode , PNode &spring)  
    {  
        int row;  
        int col;  
      
        getPosition(theNode , row , col);  
      
        //空的格子右边的格子向左移动  
        if(col != 2)  
        {  
            PNode rlNewNode = (PNode)malloc(sizeof(NNode));  
            statusAEB(rlNewNode , theNode);  
            changeAB(rlNewNode->data[row][col] , rlNewNode->data[row][col + 1]);  
            if(hasAnceSameStatus(rlNewNode , theNode->parent))  
            {  
                free(rlNewNode);//与父辈相同,丢弃本结点  
            }  
            else  
            {  
                rlNewNode->parent = theNode;  
                rlNewNode->child = NULL;  
                rlNewNode->next = NULL;  
                computeAllValue(rlNewNode , theNode);  
                //将本结点加入后继结点链表  
                addNode(spring , rlNewNode);  
            }  
        }  
        //空的格子左边的格子向右移动  
        if(col != 0)  
        {  
            PNode lrNewNode = (PNode)malloc(sizeof(NNode));  
            statusAEB(lrNewNode , theNode);  
            changeAB(lrNewNode->data[row][col] , lrNewNode->data[row][col - 1]);  
            if(hasAnceSameStatus(lrNewNode , theNode->parent))  
            {  
                free(lrNewNode);//与父辈相同,丢弃本结点  
            }  
            else  
            {  
                lrNewNode->parent = theNode;  
                lrNewNode->child = NULL;  
                lrNewNode->next = NULL;  
                computeAllValue(lrNewNode , theNode);  
                //将本结点加入后继结点链表  
                addNode(spring , lrNewNode);  
            }  
        }  
        //空的格子上边的格子向下移动  
        if(row != 0)  
        {  
            PNode udNewNode = (PNode)malloc(sizeof(NNode));  
            statusAEB(udNewNode , theNode);  
            changeAB(udNewNode->data[row][col] , udNewNode->data[row - 1][col]);  
            if(hasAnceSameStatus(udNewNode , theNode->parent))  
            {  
                free(udNewNode);//与父辈相同,丢弃本结点  
            }  
            else  
            {  
                udNewNode->parent = theNode;  
                udNewNode->child = NULL;  
                udNewNode->next = NULL;  
                computeAllValue(udNewNode , theNode);  
                //将本结点加入后继结点链表  
                addNode(spring , udNewNode);  
            }  
        }  
        //空的格子下边的格子向上移动  
        if(row != 2)  
        {  
            PNode duNewNode = (PNode)malloc(sizeof(NNode));  
            statusAEB(duNewNode , theNode);  
            changeAB(duNewNode->data[row][col] , duNewNode->data[row + 1][col]);  
            if(hasAnceSameStatus(duNewNode , theNode->parent))  
            {  
                free(duNewNode);//与父辈相同,丢弃本结点  
            }  
            else  
            {  
                duNewNode->parent = theNode;  
                duNewNode->child = NULL;  
                duNewNode->next = NULL;  
                computeAllValue(duNewNode , theNode);  
                //将本结点加入后继结点链表  
                addNode(spring , duNewNode);  
            }  
        }  
    }  
      
      
    //输出给定结点的状态  
    void outputStatus(PNode stat)  
    {  
        for(int i = 0 ; i < 3 ; i++)  
        {  
            for(int j = 0 ; j < 3 ; j++)  
            {  
                cout << stat->data[i][j] << " ";  
            }  
            cout << endl;  
        }  
    }  
      
      
      
    //输出最佳的路径  
    void outputBestRoad(PNode goal)  
    {  
        int deepnum = goal->gvalue;  
      
        if(goal->parent != NULL)  
        {  
            outputBestRoad(goal->parent);  
        }  
        cout << "第" << deepnum-- << "层的状态:" << endl;  
        outputStatus(goal);  
    }  
      
      
    void AStar()  
    {  
    
        PNode tmpNode;//指向从open表中拿出并放到closed表中的结点的指针  
        PNode spring;//tmpNode的后继结点链  
        PNode tmpLNode;//tmpNode的某一个后继结点  
        PNode tmpChartNode; 
    	 
        PNode thePreNode;//指向将要从closed表中移到open表中的结点的前一个结点的指针  
        bool getGoal = false;//标识是否达到目标状态  
        long numcount = 1;//记录从open表中拿出结点的序号  
      	
        initial();//对函数进行初始化  
        initLink(spring);//对后继链表的初始化  
        tmpChartNode = NULL;  
        //Target.data=target;
        	cout<<"1"<<endl;
        PNode Target = (PNode)malloc(sizeof(NNode)); 
        for(int i = 0 ; i < 3 ; i++)  
        {  
            for(int j = 0 ; j < 3 ; j++)  
            {  
                Target->data[i][j] =target[i][j];  
            }  
        }
      	cout<<"1"<<endl;
        cout << "从open表中拿出的结点的状态及相应的值" << endl;
     
        while(!isEmpty(open))  
        {  
        	t++;
            //从open表中拿出f值最小的元素,并将拿出的元素放入closed表中  
            popNode(open , tmpNode); 
            addNode(closed , tmpNode);
    		count_extendnode=count_extendnode+1;    
    		  
            cout << "第" << numcount++ << "个状态是:" << endl;  
            outputStatus(tmpNode);  
            cout << "其f值为:" << tmpNode->fvalue << endl;  
            cout << "其g值为:" << tmpNode->gvalue << endl;  
            cout << "其h值为:" << tmpNode->hvalue << endl;  
      
      
           /* //如果拿出的元素是目标状态则跳出循环  
            if(computeHValue(tmpNode) == 0)  
            {  count_extendnode=count_extendnode-1;
                getGoal = true;  
                break;  
            }*/ 
    		//如果拿出的元素是目标状态则跳出循环  
            if(hasSameStatus(tmpNode,Target)== true)  
            {  count_extendnode=count_extendnode-1;
                getGoal = true;  
                break;  
            }  
      
            //产生当前检测结点的后继(与祖先不同)结点列表,产生的后继结点的parent属性指向当前检测的结点  
            SpringLink(tmpNode , spring);  
      
            //遍历检测结点的后继结点链表  
            while(!isEmpty(spring))  
            {  
                popNode(spring , tmpLNode);  
                //状态在open表中已经存在,thePreNode参数在这里并不起作用  
                if(inLink(tmpLNode , open , tmpChartNode , thePreNode))  
                {  
                    addSpringNode(tmpNode , tmpChartNode);  
                    if(tmpLNode->gvalue < tmpChartNode->gvalue)  
                    {  
                        tmpChartNode->parent = tmpLNode->parent;  
                        tmpChartNode->gvalue = tmpLNode->gvalue;  
                        tmpChartNode->fvalue = tmpLNode->fvalue;  
                    }  
                    free(tmpLNode);  
                }  
                //状态在closed表中已经存在  
                else if(inLink(tmpLNode , closed , tmpChartNode , thePreNode))  
                {  
                    addSpringNode(tmpNode , tmpChartNode);  
                    if(tmpLNode->gvalue < tmpChartNode->gvalue)  
                    {  
                        PNode commu;  
                        tmpChartNode->parent = tmpLNode->parent;  
                        tmpChartNode->gvalue = tmpLNode->gvalue;  
                        tmpChartNode->fvalue = tmpLNode->fvalue;  
                        freeSpringLink(tmpChartNode->child);  
                        tmpChartNode->child = NULL;  
                        popNode(thePreNode , commu);  
                        addAscNode(open , commu);  
                    }  
                    free(tmpLNode);  
                }  
                //新的状态即此状态既不在open表中也不在closed表中  
                else  
                {  
                    addSpringNode(tmpNode , tmpLNode);  
                    addAscNode(open , tmpLNode); 	
    				count_sumnode+=1;//生成节点			 
                }  
            }  
        }  
      
        //目标可达的话,输出最佳的路径  
        if(getGoal)  
        {  
            cout << endl;  
            cout << "最佳路径长度为:" << tmpNode->gvalue << endl;
    		cout << "最佳路径为:" <<endl;
            outputBestRoad(tmpNode);  
        }  
      
        //释放结点所占的内存  
        freeLink(open);  
        freeLink(closed);  
    //    getch();  
    }  
      
      
    int main()  
    { 	double start = GetTickCount(); 
        AStar();  
        printf("生成节点数目:%d\n",count_sumnode);	
        printf("扩展节点数目:%d\n",count_extendnode); 
        printf("运行时间:%f\n",GetTickCount()-start); 
        return 0;  
    }  

    推荐文章

    欢迎大家关注【小果果学长】微信公众号,期待你的点赞和支持!

    展开全文
  • A*算法解决8数码问题python实现

    千次阅读 2020-06-08 22:03:23
    对于A星算法的具体理解可以参考下面这篇文章,本文着重讲解A星算法,在解决8数码问题的思路以及代码 A*算法的通俗理解 2.8数码问题 首先:估价函数对求解八数码问题有不同的影响。 这里我们介绍4种不同启发函数,...
  • 广度优先搜索——经典的8数码问题

    千次阅读 2014-09-21 00:36:00
    //广度搜索-8数码问题 #include #include using namespace std; const int Max = 8; const int All = 363000; //总的个数有9!= 362880,故取363000 int Fac[Max] = {1}; //康托展开需要用到的工具 char a...
  • 8 Puzzle/8 数码问题

    千次阅读 2010-01-23 10:54:00
    这些天一直在研究8数码问题,用C++实现了A*。并且用了C++的模板使得它也能够处理15数码的问题。但是15数码的问题的难度超乎了我的想象。A*不管用了。一个更好方案是使用IDA*算法。前几天看了篇论文,发现了一个增强...
  • 问题描述:   有一个3×3的棋盘,其中有0~8九个数字,0表示空格,其他的数字可以和0交换位置。求由初始状态到达目标...8数码问题源于一古老的智力游戏,随着人工智能的发展,产生了许多可以使用计算机对8数码求解的算
  • qq三国里面的小游戏,不是正经的华容道,貌似学名叫n数码问题,搜的时候好像也有人叫它拼图问题,九宫问题。。...引出了8数码问题的奇偶性互相转换问题。真是6666。 n数码也可以借鉴这个思路,但是
  • 8数码问题-深搜-广搜

    千次阅读 2014-05-20 22:45:17
    8数码问题的广搜在网上可以找到
  • A*算法求解8数码问题

    万次阅读 2012-05-05 19:12:06
    网上很多都是用A*算法解的,但是版本可以说各有千秋,自己一时间看看各个版本的代码,也弄的头昏脑涨的,这两天一直研究A*算法,然后想通过一个实例来好好学习下A*问题,这样如果能够很好的解决典型的8数码问题,对...
  • 一个8数码问题是将如图所示的初始格局中的小格子的数字经过若干步移动后(只能水平和垂直移动到一个空白处)形成如图所示的目标格局。 例: 2 8 3 1 2 3 1 0 4 ---->8 0 4 7 6 5 7 6 5 利用分支限界法解决 在线等待...
  • 8数码问题的A星算法

    千次阅读 2013-03-11 16:58:47
    该算法都够成功地解决8/15数码问题。选择的启发式函数可以是当前状态和目标状态之间的城市距离,也可以是当前状态不在目标位置的数字的和(事实证明,该启发式函数很差)。  有兴趣的同学可以从我的资源中下载源...
  • 启发式搜索解决8数码问题

    千次阅读 2013-05-26 09:49:53
    启发式搜索就是在状态空间中的搜索对每一个搜索的...8数码中的启发式函数h(x)为节点x的格局与目标格局相比数码不同的位置个数 首先把初始节点S0放入open表中,然后每次从open表中取出未搜索过并且启发式函数值最小的
  • 通过Astar算法实现8数码问题(C语言)

    千次阅读 2012-12-19 18:59:43
    在3×3的棋盘,摆有八个棋子,每个棋子上标有1至8的某一数字,不同棋子上标的数字不相同。棋盘上还有一个空格,与空格相邻的棋子可以移到空格中。要求解决的问题是:给出一个初始状态和一个目标状态,找出一种从...
  • 引理3:逆序数为偶数的序列都能转换为[1,2,3,4,5,6,7,8,@],逆序数为奇数数的序列都能转换为[1,2,3,4,5,6,8,7,@] 1.对于任意[@,a,b,c],a,b,c都能交换到最前面(a,b,c在1-8之间且a,b,c互不相等) 对于a,[@,a,b,c]...
  • //8数码类class Eight{ int e[][] = {{2,8,3},{1,6,4},{7,0,5}}; //默认的起始状态 int faX ,faY; //保存父状态中0的位置 int f; //估价函数值 E
  • A*算法求解八数码问题

    千次阅读 2019-07-07 19:00:20
    1 参考A算法核心代码,以8数码问题为例实现A算法的求解程序(编程语言不限),要求设计两种不同的估价函数。 2 在求解8数码问题的A算法程序中,设置相同的初始状态和目标状态,针对不同的估价函数,求得问题的解,并...
  • 数码问题

    千次阅读 2017-02-13 17:13:30
    数码问题: 我想大家小时候一定玩过八数码的游戏,如下图:在一个九宫格里面放入8个数字,数字只能上下左右移动,并且只能移动到空白处。通过若干此移动后,能把数字移动成图1.1右方所示图案。  图1.1(左边...
  • 数码问题-8重境界

    千次阅读 2015-08-28 22:01:43
    八数码的八境界    研究经典问题,空说不好,我们拿出一个...八数码问题在北大在线测评系统中有一个对应的题,题目描述如下: Eight Time Limit: 1000MS Memory Limit: 65536K Special Judge Description
  • A*算法求解八数码问题 Github仓库:https://github.com/dick20/Artificial-Intelligence 问题介绍   八数码问题也称为九宫问题。在3x3的棋盘,摆有八个棋子,每个棋子上标有1至8的某一数字,不同棋子上标的数字不...
  • 数码问题求解

    千次阅读 2018-03-26 12:26:19
    (一)问题描述在一个3*3的方棋盘上放置着1,2,3,4,5,6,7,8八个数码,每个数码占一格,且有...(二)问题分析八数码问题是个典型的状态图搜索问题。搜索方式有两种基本的方式,即树式搜索和线式搜索。搜索策略大体有盲...
  • 数码问题 BFS+A* 到N数码问题

    千次阅读 2018-11-12 15:27:58
    数码问题 在3×3的棋盘上,摆有八个棋子,每个棋子上标有1至8的某一数字。棋盘中留有一个空格,空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是:给出一种初始布局(初始状态)和目标布局(为了使...
  • 人工智能八数码问题

    千次阅读 2019-06-01 16:23:32
    人工智能八数码问题 在Visual C++环境(或者其他高级编程语言)下,利用状态空间法解决两个简单的走迷宫游戏问题。 人工智能大作业 有需要的联系QQ:2558957494 ...
  • A*搜索解决八数码问题&&15数码问题

    千次阅读 2019-11-01 08:18:00
    针对八数码问题的各个状态,由于数据量并不大,根据康托展开,我们可以用400000以内的数字来判断它的各个状态。这样我们就可以将各个状态装换为数字,这样的话,我们来判断是否到达目标状态的时候,就容易了一些。 ...
  • 使用C++解决八数码问题

    千次阅读 多人点赞 2018-08-01 16:35:06
    数码问题 问题描述:通过单步移动把下面的矩阵移动成1-8环绕一周的矩阵(即0在中间,1-8顺序排成一圈,1在哪无所谓) 217860345283164705 \begin{matrix} 2 & 8 & 3 \\ 1 & 6 & 4 \\ 7 &...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 31,726
精华内容 12,690
关键字:

8数码问题