八数码问题

二叉树中双分支结点就是度为2的结点,叶子就是度为0的结点 根据二叉树的性质:n0 = n2 + 1 所以叶子结点个数= 15+1 = 16个

八数码 估价函数可以选h(s)=ΣΣ[|i-u230as[i,j]-1)/3u230b| + |j-(s[i,j]-1)mod3|]

求逆序数的时候不要算0的。如果算上零的逆序数，对换之后奇偶性可能改变。

其实A*算法也是一种最好优先的算法只不过要加上一些约束条件罢了。由于在一些问题求解时，我们希望能够求解出状态空间搜索的最短路径，也就是用最快的方法求解问题，A*就是干这种事情的！我们先下个定义，如果一个估价函数可以找出最短的路径，我们称之为可采纳性。A*算法是一个可采纳的最好优先算法。A*算法的估价函数可表示为：f"(n)=g"(n)+h"(n)这里，f"(n)是估价函数，g"(n)是起点到节点n的最短路径值，h"(n)是n到目标的最短路经的启发值。由于这个f"(n)其实是无法预先知道的，所以我们用前面的估价函数f(n)做近似。g(n)代替g"(n)，但g(n)>=g"(n)才可（大多数情况下都是满足的，可以不用考虑），h(n)代替h"(n)，但h(n)<=h"(n)才可（这一点特别的重要）。可以证明应用这样的估价函数是可以找到最短路径的，也就是可采纳的。我们说应用这种估价函数的最好优先算法就是A*算法。举一个例子，其实广度优先算法就是A*算法的特例。其中g(n)是节点所在的层数，h(n)=0，这种h(n)肯定小于h"(n)，所以由前述可知广度优先算法是一种可采纳的。实际也是。当然它是一种最臭的A*算法。再说一个问题，就是有关h(n)启发函数的信息性。h(n)的信息性通俗点说其实就是在估计一个节点的值时的约束条件，如果信息越多或约束条件越多则排除的节点就越多，估价函数越好或说这个算法越好。这就是为什么广度优先算法的那么臭的原因了，谁叫它的h(n)=0，一点启发信息都没有。但在游戏开发中由于实时性的问题，h(n)的信息越多，它的计算量就越大，耗费的时间就越多。就应该适当的减小h(n)的信息，即减小约束条件。但算法的准确性就差了，这里就有一个平衡的问题。

nclude "stdio.h"typedef int datatype; /*假定线性表元素的类型为整型*/#define maxsize 1024 /*假定线性表的最大长度为1024*/# define n 100 /* 图的顶点最大个数 */typedef char VEXTYPE; /* 顶点的数据类型 */typedef float ADJTYPE; /* 权值类型 */typedef struct{ VEXTYPE vexs[n] ; /* 顶点信息数组 */ ADJTYPE arcs[n][n] ; /* 边权数组 */ int num ; /* 顶点的实际个数 */}GRAPH;/***********************1。置空图**********************/void GraphInit(GRAPH *L){ L->num=0;}/***********************2。求结点数**********************/int GraphVexs(GRAPH *L){ return(L->num);}/***********************3。创建图**********************/void GraphCreate(GRAPH *L){ int i,j; GraphInit(L); printf("请输入顶点数目："); scanf("%d",&L->num); printf("请输入各顶点的信息(单个符号）："); for(i=0;i<L->num;i++) { fflush(stdin); scanf("%c",&L->vexs[i]); } printf("请输入边权矩阵的信息："); for(i=0;i<L->num;i++) { for(j=0;j<L->num;j++) { scanf("%f",&L->arcs[i][j]); } } printf("图已经创建完毕！");}/***********************4。图的输出**********************/void GraphOut(GRAPH L){ int i,j; printf(" 图的顶点数目为：%d",L.num); printf(" 图的各顶点的信息为： "); for(i=0;i<L.num;i++) printf("%c ",L.vexs[i]); printf(" 图的边权矩阵的信息为： "); for(i=0;i<L.num;i++) { for(j=0;j<L.num;j++) { printf("%6.2f ",L.arcs[i][j]); } printf(" "); } printf("图已经输出完毕！");}/***********************5。图的深度周游**********************/void DFS(GRAPH g,int qidian,int mark[])//从第qidian个点出发深度优先周游图g中能访问的各个顶点{ int v1; mark[qidian]=1; printf("%c ",g.vexs[qidian]); for(v1=0;v1<g.num;v1++) { if(g.arcs[qidian][v1]!=0&&mark[v1]==0) DFS(g,v1,mark); }}/***********************6。图的深度周游**********************/void GraphDFS(GRAPH g)//深度优先周游图g中能访问的各个顶点{ int qidian,v,v1,mark[maxsize]; printf(" 深度周游："); printf(" 请输入起点的下标："); scanf("%d",&qidian); for(v=0;v<g.num;v++) { mark[v]=0; } for(v=qidian;v<g.num+qidian;v++) { //printf("v=%d ",v); v1=v%g.num; if(mark[v1]==0) DFS(g,v1,mark); }}typedef int DATATYPE; //队列元素的数据类型typedef struct{ DATATYPE data[maxsize]; //队中元素 int front,rear; //队头元素下标、队尾元素后面位置的下标} SEQQUEUE;/*****************************************************************************/void QueueInit(SEQQUEUE *sq)//将顺序循环队列sq置空（初始化）{ sq->front=0; sq->rear=0;}/*****************************************************************************/int QueueIsEmpty(SEQQUEUE sq)//如果顺序循环队列sq为空，成功返回1，否则返回0{ if (sq.rear==sq.front) return(1); else return(0);} /*****************************************************************************/int QueueFront(SEQQUEUE sq,DATATYPE *e)//将顺序循环队列sq的队头元素保存到e所指地址，成功返回1，失败返回0{ if (QueueIsEmpty(sq)) else}/*****************************************************************************/int QueueIn (SEQQUEUE *sq,DATATYPE x)//将元素x入队列sq的队尾，成功返回1，失败返回0{ if (sq->front==(sq->rear+1)%maxsize) { printf("queue is full! "); return 0; } else { sq->data[sq->rear]=x; sq->rear=(sq->rear+1)%maxsize; return(1); }}/*****************************************************************************/int QueueOut(SEQQUEUE *sq)//将队列sq队首元素出队列，成功返回1,失败返回0{ if (QueueIsEmpty(*sq)) { printf("queue is empty! "); return 0; } else { sq->front=(sq->front+1)%maxsize; return 1; }}/***********************7。图的广度周游**********************/void BFS(GRAPH g,int v,int mark[])//从v出发广度优先周游图g中能访问的各个顶点{ int v1,v2; SEQQUEUE q; QueueInit(&q); QueueIn(&q,v); mark[v]=1; printf("%c ",g.vexs[v]); while(QueueIsEmpty(q)==0) { QueueFront(q,&v1); QueueOut(&q); for(v2=0;v2<g.num;v2++) { if(g.arcs[v1][v2]!=0&&mark[v2]==0) { QueueIn(&q,v2); mark[v2]=1; printf("%c ",g.vexs[v2]); } } }}/***********************8。图的广度周游**********************/void GraphBFS(GRAPH g)//深度优先周游图g中能访问的各个顶点{ int qidian,v,v1,mark[maxsize]; printf(" 广度周游："); printf(" 请输入起点的下标："); scanf("%d",&qidian); for(v=0;v<g.num;v++) { mark[v]=0; } for(v=qidian;v<g.num+qidian;v++) { v1=v%g.num; if(mark[v1]==0) BFS(g,v1,mark); }}/***********************主函数**********************/void main(){ GRAPH tu; GraphCreate(&tu); GraphOut(tu); GraphDFS(tu); GraphBFS(tu);}另外,虚机团上产品团购,超级便宜

可以给你看看我的程序，已发送，记得给分喔

基于51的程序：#include <reg52.h>sbit sda=P0^5;sbit scl=P0^6;code char led_code[19]={0x11,0xd7,0x32,0x92,0xd4, // 0,1,2,3,4 0x98,0x18,0xd3,0x10,0x90, // 5,6,7,8,9 0x50,0x1c,0x39,0x16,0x38, // a,b,c,d,e, 0x78,0xfe,0xef,0xff}; // f - dot dark void seperate(unsigned char second,minute,hour); //1调用拆分函数void display(unsigned char second,minute,hour); // 2调用显示函数 一定要在各处强调unsignde吗？void shift(unsigned char); //3调用移位函数void delay_1s(unsigned int x); //4调用延时函数unsigned char second,minute,hour;unsigned char second0,second1, minute0,minute1, hour0,hour1; // 这三行表示了时、分、秒所占数码管的个数和位置。 叫形参？void main(){ while(1) { for(hour=0;hour<24;hour++) //三个for语句的安排妙啊！ 我们看到的钟表时分秒的变化！ { for(minute=0;minute<60;minute++) { for(second=0;second<60;second++) { display(second,minute,hour); delay_1s(65535); } } } }}void display(unsigned char second,minute,hour) //2对显示函数的说明{ seperate(second,minute,hour); shift(second0); shift(second1); shift(16); shift(minute0); shift(minute1); shift(16); shift(hour0); shift(hour1);}void seperate(unsigned char second,minute,hour) //1对拆分函数的说明{ second0=second%10; second1=second/10; minute0=minute%10; minute1=minute/10; hour0=hour%10; hour1=hour/10;}void shift(unsigned char n) //3对移位函数的说明{ unsigned char dat,minute; dat=led_code[n]; scl=0; for(minute=0;minute<8;minute++) { if (dat&0x80) sda=1; else sda=0; scl=1; scl=0; dat<<=1; }}void delay_1s(unsigned int a) //4对延时函数的说明{ while(a--);}

#include<iostream>#include<cstdio>#include<cstring> using namespace std;const int N=370000,HN=1000003;int data[N][10],f[N],step[N],z[N];//data用于BFS队列存储，f记录节点的父亲，step记录节点的步数 int mv[10][5]={0,0,0,0,0, 2,2,4,0,0,3,3,1,5,0,2,2,6,0,0,3,1,5,7,0,4,2,4,6,8,3,3,5,9,0,2,4,8,0,0,3,5,7,9,0,2,6,8,0,0,};int en[10],head[HN],next[N];//en记录目标状态，head记录hash表头，next记录hash后继指针 void shuchu(int k) //输出路径 {if(f[k]!=0) shuchu(f[k]);for(int i=1;i<=9;i++){cout<<data[k][i]<<" ";if(i==3||i==6) cout<<endl;}cout<<endl<<endl; }int hash(int a){int x=0;for(int i=1;i<=9;i++)x=x*10+data[a][i]; //将新节点的状态映射成9位整数return x%HN; //确保hash值不超过hash表的大小； }bool can(int a){int h=hash(a);//取回当前节点的hash值 int u=head[h];//取回当前节点hash值的链表的表头 while(u){if(memcmp(data[u],data[a],sizeof(data[0]))==0) return 0; //状态重复，返回假 u=next[u]; //利用链表找到下一个余数相同的节点 }next[a]=head[h]; //新节点的next指针指向原来的hash值的表头 head[h]=a; //新节点成为新的hash值的表头 return 1; //合法的新节点 }void bfs(){int h=0,t=1; while(h<t){h++; //扩展队首 for(int i=1;i<=mv[z[h]][0];i++) //z[h]队头（当前扩展节点）空格所在位置 {memcpy(&data[t+1],&data[h],sizeof(data[h]));//把父节点的内容复制到扩展节点中 data[t+1][z[h]]=data[h][mv[z[h]][i]]; //原来（父节点）空格位置填值（交换） data[t+1][mv[z[h]][i]]=0; //新的（子节点）空格置空 z[t+1]=mv[z[h]][i]; //记录新的空格位置 if(can(t+1)){t++; //增加新节点 f[t]=h;step[t]=step[h]+1; if(memcmp(data[t],en,sizeof(en))==0){cout<<step[t]<<endl;shuchu(t);fclose(stdin);fclose(stdout);exit(0);}} } }}int main(){freopen("eight.in","r",stdin);freopen("eight.out","w",stdout);for(int i=1;i<=9;i++) //将出发状态直接装入队列 {cin>>data[1][i]; if(data[1][i]==0) z[1]=i;} f[1]=0;step[1]=0;for(int i=1;i<=9;i++) //存储目标状态 cin>>en[i];if(memcmp(data[1],en,sizeof(en))==0) //memcmp是比较内存区域buf1和buf2的前count个字节。该函数是按字节比较的{ //特殊情况，出发状态跟目标状态一样 cout<<0<<endl;shuchu(1);fclose(stdin);fclose(stdout);return 0;} bfs();return 0; }

利用奇偶性判断所给出的初始状态有无解.判别方法是：以数组为一维的举例子.将八数码的一个结点表示成一个数组a[9]，空格用0表示，设临时函数p(x)定义为：x数所在位置前面的数比x小的数的个数，其中0空格不算在之内，那设目标状态为b[9]，那r=sigma(p(x)) sigma()表示取所有的x:1-8并求和，那对于初始状态a[9]，t=sigma(p(x))，如果r和t同为奇数或者同为偶数，那么该状态有解，否则无解。考虑到四种移动方法对sigma(p(x))的影响，左移和右移是不会影响它的值的，更不会影响奇偶性，如果是上移或者下移就会影响：上移:一次上移会使一个元素向前跳两个数字的位置，设这两个数字为a1,a2，不妨设a1<a2，移的这个数字设为a0，那无非只有以下三次情况：1，a0<a1<a2，考虑它们三者的p(x)值，p(a0)不变，p(a1)++，p(a2)++，总体增加了22，a1<a0<a2，p(a0)--,p(a1)不变,p(a2)++，总体不变3，a1<a2<a0，p(a0)-=2,p(a1),p(a2)不变，总体减小了2综合起来的结论就是不会影响sigma(p(x))的奇偶性。

八数码问题有一个3*3的棋盘，其中有0-8 9个数字，0表示空格，其他的数字可以和0交换位置。求由初始状态1 2 34 5 67 8 0到达目标状态步数最少的解。其典型算法是广度优先搜索，具体算法是：struct 类名 m_ar[可能结点数];int h,rmain(){ h=0;r=1; while ((h<r)&&(r<可能结点数)) { if (判断每一种可能性，如果某一种操作符合要求)&nbs……

八数码问题： 取一个 3*3 的矩阵，将1-8(或者任意从小到大的八个数字)，随机分布在矩阵中，留下一个空格(可以用0代替)，作为初始状态；再去一个3*3的矩阵，将1-8(或者任意从小到大的八个数字，其取值必须与初始状态相同)，随机分布在矩阵中，留下一个空格(可以用0代替)，作为目标状态；对初始状态进行操作，其允许的操作是：将空格向上，下，左，右移动(即将空格与周边的数字进行交换)，操作初始状态的矩阵，在若干步后达目标状态。求解其过程为八数码问题。如图： 八数码问题的有解条件： 将矩阵从上到下从左到右的顺序分布成一个数列，并去掉空格，例如： 2 8 3 (0为空格) 分布成数列后： 1 0 4 u2003u2003u2003u20032 8 3 1 4 7 6 5 7 6 5 如果此 初始状态的数列(矩阵) 的 逆序数 与 目标状态的数列(矩阵) 的 逆序数 的 奇偶性一样 ，则此问题有解。 逆序数 的定义： 有一个数列，在这个数列中任意取一对数字(两个数字)，其两个数字在数列中的(从前到后)顺序与数字数值的大小相反，称其为一个逆序。这个数列中所有的逆序的和为逆序数。 证明 ： 空格向左右移动时，不改变逆序数的大小；空格向上下移动时，会改变逆序数，改变的幅度为±2或者0 (1)。所以±2或者0的改变幅度不会对逆序数造成奇偶性的改变。所以如果两个矩阵状态如果能互相到达，则必须有其逆序数的奇偶性一样。 (1) 在矩阵中操作空格上下移动时，在数列中的表现是将被交换的数字提前到他前面两个数字之前或者推后到他后面两个数字之后；例如，被交换的数字的下标是 Z 的话，空格向下移动(即被交换数向上移动)后，被交换数在数列中的位置是 Z-2 ；空格向上移动(即被交换数向下移动)后，则被交换数在数列中的位置是 Z+2。这种交换不会影响到被交换数与被它跨过的两个数以外的数字的顺序。比如说：被交换数的位置 Z ，如果空格向上移动，被交换数位置变成 Z+2，但是Z-1处的数字 与 Z 的顺序没有因为 Z 变成 Z+2 而失去了Z-1 在 Z 的前面的顺序，Z-1在Z前面，也在Z+2前面，同样的，Z变成Z+2也不会改变Z与Z+3的顺序。并且，如果有顺序 2 3 4 ，这个顺序的逆序数为0，如果我把4放到2 3前面，变成4 2 3，其逆序数就变成了+2，逆序数就增长了2；如果有顺序 4 2 3，其逆序数为+2，如果我把4放到2 3后面，变成2 3 4，其逆序数就变成了0，逆序数减少了2；如果有6 4 5，其逆序数为+2，如果我把5放在6 4 的前面，变成5 6 4，其逆序数为2，逆序数改变为0。所以改变的幅度为±2，或者0。 八数码问题的解法以及算法(宽度优先)： 解法： 空格可以上下左右移动，则父状态可以衍生出若干个子状态(考虑其空格不能越3*3的界以及其不返回到父状态或者父父状态等等之类的情况的话，最大的子状态数量为4 最小为0)，这种思路的话实际上这个问题就是一个树的搜索问题，所以用搜索的算法可以解决。 算法(宽度优先)： (1)判断初始状态与目标状态的逆序数的奇偶性来判断是否有解 (2)建立一个OPEN表(队列)，用于存放待展开子节点(状态)的父节点 (3)建立一个CLOSED表(队列)，用于存放已经展开了子节点的父节点 (4)将初始状态放到OPEN表中，作为第一个 (5)将OPEN表中第一个节点取出(并在OPEN表中删除这个节点)，放到CLOSED表中，排在CLOSED表中最后一个，整理好OPEN表 (6)把CLOSED表最后一个节点按照条件(不越界，不返回到父节点)展开其子节点，并且将可能的子节点按照顺序存入OPEN表中 (7)判断此父节点是否为目标状态： u2003①是，退出，打印答案 u2003②不是，回到步骤(4) 问题： (1)如果不用数字，而是用毫无关系的符号来填充矩阵，怎么判断是否有解呢？ 想法：将初始状态作为参考，将其不同的符号的顺序作为其符号的值的大小，计算出初始状态的逆序数为0，按照初始状态的值大小来判断目标状态的逆序数，然后判断奇偶性进而判断是否有解。