BFS:
#include <iostream>
using namespace std
int fac[10]={1,1}
bool tflag[9]
struct bbit{
unsigned int val:4
}
struct bbbit
{
unsigned int val:2
}
struct Node
{
bbit s[9],pos
int step
bbbit path[21],tag
int hashval()
{
int ret=0,i,j,tmp
memset(tflag,false,sizeof(tflag))
for(i=0i<8i++)
{
tmp=0
for(j=0j<s[i].valj++)
if(!tflag[j])
tmp++
ret+=tmp*fac[8-i]
tflag[s[i].val]=true
}
return ret
}
bool up()
{
if(pos.val<=2)return false
s[pos.val].val^=s[pos.val-3].val
s[pos.val-3].val^=s[pos.val].val
s[pos.val].val^=s[pos.val-3].val
path[step].val=0
pos.val-=3
return true
}
bool down()
{
if(pos.val>=6)return false
s[pos.val].val^=s[pos.val+3].val
s[pos.val+3].val^=s[pos.val].val
s[pos.val].val^=s[pos.val+3].val
path[step].val=1
pos.val+=3
return true
}
bool left()
{
if(pos.val==0||pos.val==3||pos.val==6)return false
s[pos.val].val^=s[pos.val-1].val
s[pos.val-1].val^=s[pos.val].val
s[pos.val].val^=s[pos.val-1].val
path[step].val=2
pos.val--
return true
}
bool right()
{
if(pos.val==2||pos.val==5||pos.val==8)return false
s[pos.val].val^=s[pos.val+1].val
s[pos.val+1].val^=s[pos.val].val
s[pos.val].val^=s[pos.val+1].val
path[step].val=3
pos.val++
return true
}
bool operator==(const Node&x)const
{
int i
for(i=0i<9i++)if(s[i].val!=x.s[i].val)return false
return true
}
}Q[362880],S,A,tmp,top
struct Hash
{
bool d1,d2
Node D
}hash[362880]
inline void mkfac(){int ifor(i=2i<=9i++)fac[i]=fac[i-1]*i}
inline int eval(char c){return c=='x'?0:c-'0'}
void o(Node x,Node y)
{
int i
for(i=1i<=x.stepi++)
{
switch(x.path[i].val)
{
case 0:putchar('u')break
case 1:putchar('d')break
case 2:putchar('l')break
case 3:putchar('r')break
}
}
for(i=y.stepi>=1i--)
switch(y.path[i].val){
case 0:putchar('d')break
case 1:putchar('u')break
case 2:putchar('r')break
case 3:putchar('l')break
}
puts("")
}
int main()
{
char buf[11]
int i,t,l,r
bool flag
mkfac()
while(NULL!=gets(buf))
{
t=0
for(i=0i<=7i++)A.s[i].val=i+1A.s[8].val=0A.pos.val=8
for(i=0buf[i]i++)
{
if(buf[i]==' ')continue
S.s[t].val=eval(buf[i])
if(S.s[t].val==0)
S.pos.val=t
t++
}
l=r=0
flag=false
for(i=0i<362880i++)hash[i].d1=hash[i].d2=false
S.step=0S.tag.val=1
A.step=0A.tag.val=2
Q[r++]=S//tag.val:1
Q[r++]=A//tag.val:2
while(l<=r)
{
top=Q[l++]
top.step++
tmp=top
if(tmp.up())
{
if(tmp.tag.val==1)
{
if(!hash[t=tmp.hashval()].d1)
{
hash[t].d1=true
Q[r++]=tmp
if(hash[t].d2&&hash[t].D==tmp)
{
//find ans...
o(tmp,hash[t].D)
goto AA
}
if(!hash[t].d2)hash[t].D=tmp
}
}
else
{
if(!hash[t=tmp.hashval()].d2)
{
hash[t].d2=true
Q[r++]=tmp
if(hash[t].d1&&hash[t].D==tmp)
{
//find ans...
o(hash[t].D,tmp)
goto AA
}
if(!hash[t].d1)hash[t].D=tmp
}
}
}
tmp=top
if(tmp.down())
{
if(tmp.tag.val==1)
{
if(!hash[t=tmp.hashval()].d1)
{
hash[t].d1=true
Q[r++]=tmp
if(hash[t].d2&&hash[t].D==tmp)
{
//find ans...
o(tmp,hash[t].D)
goto AA
}
if(!hash[t].d2)hash[t].D=tmp
}
}
else
{
if(!hash[t=tmp.hashval()].d2)
{
hash[t].d2=true
Q[r++]=tmp
if(hash[t].d1&&hash[t].D==tmp)
{
//find ans...
o(hash[t].D,tmp)
goto AA
}
if(!hash[t].d1)hash[t].D=tmp
}
}
}
tmp=top
if(tmp.left())
{
if(tmp.tag.val==1)
{
if(!hash[t=tmp.hashval()].d1)
{
hash[t].d1=true
Q[r++]=tmp
if(hash[t].d2&&hash[t].D==tmp)
{
//find ans...
o(tmp,hash[t].D)
goto AA
}
if(!hash[t].d2)hash[t].D=tmp
}
}
else
{
if(!hash[t=tmp.hashval()].d2)
{
hash[t].d2=true
Q[r++]=tmp
if(hash[t].d1&&hash[t].D==tmp)
{
//find ans...
o(hash[t].D,tmp)
goto AA
}
if(!hash[t].d1)hash[t].D=tmp
}
}
}
tmp=top
if(tmp.right())
{
if(tmp.tag.val==1)
{
if(!hash[t=tmp.hashval()].d1)
{
hash[t].d1=true
Q[r++]=tmp
if(hash[t].d2&&hash[t].D==tmp)
{
//find ans...
o(tmp,hash[t].D)
goto AA
}
if(!hash[t].d2)hash[t].D=tmp
}
}
else
{
if(!hash[t=tmp.hashval()].d2)
{
hash[t].d2=true
Q[r++]=tmp
if(hash[t].d1&&hash[t].D==tmp)
{
//find ans...
o(hash[t].D,tmp)
goto AA
}
if(!hash[t].d1)hash[t].D=tmp
}
}
}
}
AA:flag=true
if(!flag)
puts("unsolvable")
}
return 0
}
A*:
#include <iostream>
#include <queue>
using namespace std
int fac[10]={1,1}
struct Node
{
int s[9],step,pos
char path[501]
int hashval()
{
int ret=0,i,j,tmp
bool flag[9]
memset(flag,false,sizeof(flag))
for(i=0i<8i++)
{
tmp=0
for(j=0j<s[i]j++)
if(!flag[j])
tmp++
ret+=tmp*fac[8-i]
flag[s[i]]=true
}
return ret
}
bool up()
{
if(pos<=2)return false
s[pos]^=s[pos-3]
s[pos-3]^=s[pos]
s[pos]^=s[pos-3]
path[step]='u'
pos-=3
return true
}
bool down()
{
if(pos>=6)return false
s[pos]^=s[pos+3]
s[pos+3]^=s[pos]
s[pos]^=s[pos+3]
path[step]='d'
pos+=3
return true
}
bool left()
{
if(pos==0||pos==3||pos==6)return false
s[pos]^=s[pos-1]
s[pos-1]^=s[pos]
s[pos]^=s[pos-1]
path[step]='l'
pos--
return true
}
bool right()
{
if(pos==2||pos==5||pos==8)return false
s[pos]^=s[pos+1]
s[pos+1]^=s[pos]
s[pos]^=s[pos+1]
path[step]='r'
pos++
return true
}
bool operator==(const Node&x)const
{
int i
for(i=0i<9i++)if(s[i]!=x.s[i])return false
return true
}
void show()
{
int i,j
for(i=0i<=6i+=3,cout<<endl)
for(j=ij<=i+2j++)
cout<<s[j]
}
bool operator<(const Node&x)const
{
int la=0,lb=0,i
for(i=0i<8i++)if(s[i]!=i+1)la++la+=(s[8]!=0)
for(i=0i<8i++)if(x.s[i]!=i+1)lb++lb+=(x.s[8]!=0)
return la>lb
}
}S,A,tmp,top
priority_queue<Node>Q
bool hash[362880]
void mkfac(){int ifor(i=2i<=9i++)fac[i]=fac[i-1]*i}
int eval(char c){return c=='x'?0:c-'0'}
void output(Node x)
{
int i
for(i=1i<=x.stepi++)
putchar(x.path[i])
puts("")
}
int main()
{
char buf[11]
int i,t,l,r
bool flag
mkfac()
while(NULL!=gets(buf))
{
t=0
for(i=0i<=7i++)A.s[i]=i+1A.s[8]=0A.pos=8
for(i=0buf[i]i++)
{
if(buf[i]==' ')continue
S.s[t]=eval(buf[i])
if(S.s[t]==0)
S.pos=t
t++
}
l=r=0
flag=false
memset(hash,false,sizeof(hash))
S.step=0
while(!Q.empty())Q.pop()
Q.push(S)
while(!Q.empty())
{
top=Q.top()
Q.pop()
top.step++
tmp=top
if(tmp.up())
{
if(!hash[t=tmp.hashval()])
{
hash[t]=true
Q.push(tmp)
if(tmp==A)
{
//find ans...
output(tmp)
goto AA
}
}
}
tmp=top
if(tmp.down())
{
if(!hash[t=tmp.hashval()])
{
hash[t]=true
Q.push(tmp)
if(tmp==A)
{
//find ans...
output(tmp)
goto AA
}
}
}
tmp=top
if(tmp.left())
{
if(!hash[t=tmp.hashval()])
{
hash[t]=true
Q.push(tmp)
if(tmp==A)
{
//find ans...
output(tmp)
goto AA
}
}
}
tmp=top
if(tmp.right())
{
if(!hash[t=tmp.hashval()])
{
hash[t]=true
Q.push(tmp)
if(tmp==A)
{
//find ans...
output(tmp)
goto AA
}
}
}
}
AA:flag=true
if(!flag)
puts("unsolvable")
}
return 0
}
八数码问题：
取一个 3*3 的矩阵，将1-8(或者任意从小到大的八个数字)，随机分布在矩阵中，留下一个空格(可以用0代替)，作为初始状态；再去一个3*3的矩阵，将1-8(或者任意从小到大的八个数字，其取值必须与初始状态相同)，随机分布在矩阵中，留下一个空格(可以用0代替)，作为目标状态；对初始状态进行 *** 作，其允许的 *** 作是：将空格向上，下，左，右移动(即将空格与周边的数字进行交换)， *** 作初始状态的矩阵，在若干步后达目标状态。求解其过程为八数码问题。如图：
八数码问题的有解条件：
将矩阵从上到下从左到右的顺序分布成一个数列，并去掉空格，例如：
2 8 3 (0为空格) 分布成数列后：
1 0 4 2 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)判断此父节点是否为目标状态：
①是，退出，打印答案
②不是，回到步骤(4)
问题：
(1)如果不用数字，而是用毫无关系的符号来填充矩阵，怎么判断是否有解呢？
想法：将初始状态作为参考，将其不同的符号的顺序作为其符号的值的大小，计算出初始状态的逆序数为0，按照初始状态的值大小来判断目标状态的逆序数，然后判断奇偶性进而判断是否有解。
#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=1i<=9i++)
{
cout<<data[k][i]<<" "
if(i==3||i==6) cout<<endl
}
cout<<endl<<endl
}
int hash(int a)
{
int x=0
for(int i=1i<=9i++)
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=1i<=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=1i<=9i++) //将出发状态直接装入队列
{
cin>>data[1][i]
if(data[1][i]==0) z[1]=i
}
f[1]=0
step[1]=0
for(int i=1i<=9i++) //存储目标状态
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
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）