python---A*搜索算法解决八数码问题
程序员文章站
2024-01-08 13:26:58
...
问题内容
【传教士和食人者问题】
在一个３×３的九宫中有1-8这８个数字以及一个空格随机摆放在其中的格子里。将该九宫格调整到目标状态。
规则：每次只能将与空格（上、下、左、右）相邻的一个数字移动到空格中。试编程实现这一问题的求解。
备注：为了程序中表示方便，用0代替空格。
初始状态和目标状态：均由用户通过键盘手工输入或者从文件读入（不可以写死在程序里面）。
算法流程
相关设置
其实和之前的传教士问题的设置差不多，都有用到open表和closed表。
（1）状态用字符串表示 ，如“513708246”；
（2）对状态结点展开所用到的open表和closed表，就用列表 opened=[ ]，closed=[ ]；
（3）为了保存每一个状态的父结点，使用字典parent={ key：value }，key必须不可变，且唯一，和状态的特性相似，value即为每个状态对应的父结点；
（4）为了计算估价函数值，使用Gn={}和Fn={}，用来存储状态和对应的估价函数值；
（5）这里的估价函数值中的H(n) 是和目标状态相比错位的数目。
关于程序中用到的函数：
THEnum()–用来计算状态的逆序数；
Hn()–用来计算估价函数中的值，即为当前状态和目标状态的错位数；
Expand()–对结点进行拓展；
MIN()–从opened表中选择估价函数值最小的一个状态；
PRINT()–按格式输出结果。
具体程序
本人来自江南大学，同校的小伙伴们记得修改修改，以免查重
# -*- coding: utf-8 -*-
"""
Created on Thu Apr 2 21:58:44 2020
@author:jn
"""
#计算状态对应的逆序数
def THEnum(node):
Sum=0
for i in range(1,9):
num=0
for j in range(0,i):
if node[j]>node[i] and node[i]!='0':
num=num+1
Sum+=num
return Sum
#h(n)函数，用于计算估价函数f(n)，这里的h(n)选择的是与目标相比错位的数目
def Hn(node):
global goal
hn=0
for i in range(0,9):
if node[i]!=goal[i]:
hn+=1
return hn
#拓展node状态对应的子结点
def Expand(node):
global expand
tnode=[]
state = node.index("0")
elist= expand[state]
j=state
for i in elist:
j=state
if i>j:
i,j = j,i
re= node[:i] + node[j] + node[i+1:j] + node[i] + node[j+1:]
tnode.append(re)
return tnode
#将最后的结果按格式输出
def PRINT(result):
for i in range(len(result)):
print("step--" + str(i+ 1))
print(result[i][:3])
print(result[i][3:6])
print(result[i][6:])
#选择opened表中的最小的估价函数值对应的状态
def MIN(opened):
ll={}
for node in opened:
k=Fn[node]
ll[node]=k
kk=min(ll,key=ll.get)
return kk
#主程序开始
opened=[]
closed=[]
Gn={}#用来存储状态和对应的深度，也就是初始结点到当前结点的路径长度
Fn={}#用来存放状态对应的估价函数值
parent={}#用来存储状态对应的父结点
#expand中存储的是九宫格中每个位置对应的可以移动的情况
#当定位了0的位置就可以得知可以移动的情况
expand = {0:[1, 3], 1:[0, 2, 4], 2:[1, 5],
3:[0,4,6], 4:[3,1,5,7], 5:[4,2,8],
6:[3,7], 7:[6,4,8], 8:[7,5]}
start=input("请输入初始状态(从左至右，从上到下，如：102345678)：")
goal =input("请输入目标状态(从左至右，从上到下，如：123456780)：")
if start==goal:
print("初始状态和目标状态一致！")
#判断从初始状态是否可以达到目标状态
if (THEnum(start)%2)!=(THEnum(goal)%2):
print("该目标状态不可达！")
else:
parent[start]=-1#初始结点的父结点存储为-1
Gn[start]=0#初始结点的g(n)为0
Fn[start]=Gn[start]+Hn(start)#计算初始结点的估价函数值
opened.append(start)#将初始结点存入opened表
while opened:
current=MIN(opened)#选择估价函数值最小的状态
del Fn[current]
opened.remove(current)#将要遍历的结点取出opened表
if current==goal:
break
if current not in closed:
closed.append(current)#存入closed表
Tnode=Expand(current)#扩展子结点
for node in Tnode:
#如果子结点在opened和closed表中都未出现，则存入opened表
#并求出对应的估价函数值
if node not in opened and node not in closed:
Gn[node]=Gn[current]+1
Fn[node]=Gn[node]+Hn(node)
parent[node]=current
opened.append(node)
else:
#若子结点已经在opened表中，则判断估价函数值更小的一个路径
#同时改变parent字典和Fn字典中的值
if node in opened:
fn=Gn[current]+1+Hn(node)
if fn<Fn[node]:
Fn[node]=fn
parent[node]=current
result=[]#用来存放路径
result.append(current)
while parent[current] != -1:#根据parent字典中存储的父结点提取路径中的结点
current =parent[current]
result.append(current)
result.reverse()#逆序
PRINT(result)#按格式输出结果
运行结果
遇到的问题
没遇到什么问题，哈哈哈哈
完结
撒花~~~~~~~~~