首页 > Python资料 博客日记
【Python】A*八数码问题_求解思路与代码实现
2024-10-04 02:00:05Python资料围观52次
#创作灵感#
人工智能导论课,要求用代码,实现八数码问题的求解。由于算法基础不扎实,除了课上老师的讲解,还去B站,搜集了相关资源,最后顺利完成课程实验。在这里做个分享,也是梳理一遍求解思路。
一、逻辑结构
空格可以往四个方向移动,给定初始状态、目标状态,求两个状态的最短路径、最短路径的长度。无法到达,则输出-1。空格上的数字,用0表示。
用一维数组,表示一个盘面,需要进行上下左右移动时,转换为二维数组,操作完成后,再转换为一维数组。一维数组下标,与二维数组下标的关系:A[6] = A[6//3][6%3],A[1][2] = A[1*3+2]。
每次空格只能往四个方向移动一格,移动后的状态数组,与之前的状态数组,只有两个元素不同。四个方向的移动,对二维坐标的影响:
用两个数组,来记录X、Y的改变量,方便快速计算空格的二维新坐标:
另外,如果不加以管控,八数码问题的状态空间是图,因为可能会出现重复结点,并进入死循环,求无权图的最短路径更适合BFS,找到目标状态就可以退出循环:
为避免死循环,需要对新入队结点,进行排重,可以定义查找列表。如果当前结点,在查找表中没有出现过,插入查找列表并入队,如果已经出现过,则不入队。没有重复结点产生,八数码的状态空间就可以看成树。
A*是用结点的估价函数值,决定访问的优先次序。估价函数为:f(x) = p(x) +s(x)。p(x)代表前半段距离(从初始状态,到该节点的距离,即结点深度)。s(x)代表后半段距离(从当前节点,到目标状态的估计距离)。s(x)设计的是否合理,决定搜索效率,这里用3倍当前结点到目标状态的曼哈顿距离,作为后半段距离s(x)的估计值。(两个盘面的曼哈顿距离,等于0除外的每个元素的曼哈顿距离之和,每个元素的曼哈顿距离,等于两个盘面中,该元素的横坐标之差+纵坐标之差,具体可以看一下这个视频:A*算法的书面求解步骤)
为了方便求曼哈顿距离,可以对目标状态”打表“,把每个数字的坐标打成二维形式,比如目标状态为goal = "436708125",那么可以定义列表x,y,就可以快速查到目标状态中相应数字的X、Y坐标:
大致的求解思路:先计算初始状态、目标状态的逆序数,如果奇偶性不相同,那么无解,返回-1( 相关的理论证明,在这个链接里:深入理解逆序数+八数码原理)。奇偶性相同,那么计算初始状态的代价f,并入队,进入循环,循环条件:如果队列不空。循环体为:
取队首元素,判断是否为目标状态,如果是,返回队首结点与初始状态的距离(即结点深度)。否则,按照上、下、左、右,依次循环扩展该结点,并计算新结点的估价值f。如果移动合法,产生新节点入队。四个方向搜索结束,队首结点出队,根据剩余结点的估价值f,对队列中所有结点排序,最后进入下一循环。
二、逻辑实现
一个结点st_state,包括两个数据项:估价值f、盘面state。估价值f为int类型,而盘面state的保存,用python字符串实现。最后用二元组,来存储这两个数据项。
所有的结点,用列表st来保存。当前结点与初始状态的距离,用列表dist存储。当前结点的父节点索引,用列表fu保存。最后从逻辑上看,应该是这样:
单个数据元素的结构:
数据元素间的关系(队列):
入队出队操作:
上下左右移动,通过交换字符实现
从字符串的角度看,移动前后,其实就是置换两个字符的位置。其中一个字符是0,另一个字符,是某个相邻滑块。
如果找到两个字符的索引,交换位置是非常高效的。字符0的索引,通过for循环遍历得到。而相邻滑块的索引,可以通过字符0的索引,计算得到,方法如下:
先将0的索引,转换为二维坐标。如果state[z] = '0',那么‘0’的二维坐标就是state[z//3][z%3]。
再根据上下左右移动,对坐标的影响,计算出空格的二维新坐标,例如state[X][Y]往i方向移动:
,
此时将state[newX][newY]转换成一维坐标:
,
这样,就能够得知,与0交换位置的,相邻滑块的索引。从逻辑上看,应该是这样的:
先找到0的索引:
转换为二维坐标:
往i方向移动,以i=1(下移)为例,计算移动后的二维新坐标:
转换为一维坐标,就能够知道,索引为5、8指向的字符,交换位置,就是下移后的状态数组:
三、代码实现
import sys
init_lookup_table = [] #定义查找表为全局变量,确保每个函数都能访问到
#打印初始状态、目标状态,在转换为二维数组后,每个元素的x、y坐标
def daBiao(state):
#创建X、Y数组,用于存放坐标信息
state_X = list(range(9))
state_Y = list(range(9))
#将0的x、y置为-1,不会计算0元素的曼哈顿距离
state_X[0],state_Y[0] = -1,-1
#计算状态中每个元素的坐标
for i in range(9):
#计算下表为i的元素的x、y
x = i // 3
y = i % 3
#判断当前元素是1-8中的谁
value_ = int(state[i])
#修改对应元素的二维坐标
state_X[value_] = x
state_Y[value_] = y
#循环结束,返回X,Y
return state_X,state_Y
# 计算某个状态state,与goal的曼哈顿距离
def man_ha_dun(state,goal):
# 对初始状态\目标状态打表,为后续计算曼哈顿距离做准备
goal_x,goal_y = daBiao(goal)
# 计算曼哈顿距离
list = 0 # 初始化
for i in range(9):
if state[i] == '0': #表示不计算空格的曼哈顿距离
break
# 获取第i个元素的值,计算该元素的曼哈顿距离
value_ = int(state[i])
# 获取该元素的二维坐标
X = i // 3
Y = i % 3
# 根据initial_x、initial_y,计算出该元素的曼哈顿距离
list_i = abs(goal_x[value_] - X) + abs(goal_y[value_] - Y)
list += list_i
if state[4] != '0': #如果中间有将牌,那么list+1
list += 1
return list
#计算逆序数
def ni_xu_shu(data):
answer = 0
data_list = []
for i in data: #遍历字符串data
if int(i) != 0:
data_list.append(int(i)) #把不为0的放前面
data_list.append(0) #队尾加0
#计算data_list的逆序数
for i in range(8): #计算前7个数的逆序数,最后一个数的逆序数为0
for j in range(i+1,9): #第i个元素,依次与后面i+1个元素比较
if data_list[i] > data_list[j]: #如果满足条件,逆序数+1
answer += 1
return answer
# 判断某个元素是否被访问过,如果没有被访问过,则返回True,并加入查找表
def try_to_insert(st_state):
global init_lookup_table
if init_lookup_table.count(st_state) == 0:
init_lookup_table.append(st_state)
return True
else:
return False
#重排序函数,根据新入队节点的曼哈顿距离,返回一个新的节点顺序,调整其在队列中的位置(调整访问顺序)
def soreted_st_state(new_st_state_list):
return sorted(new_st_state_list,key=lambda x:x)
#A*算法,搜索到目标状态后,返回与初始状态的距离、访问路径,否则返回-1,表示不可到达
def A_star(initial,goal):
#0、先判断有无解
#求initial、goal的逆序数
initial_nixushu = ni_xu_shu(initial)
goal_nixushu = ni_xu_shu(goal)
#判断有无解,如果无解,返回-1
if (initial_nixushu % 2 == 0)and(goal_nixushu % 2 != 0) or (initial_nixushu % 2 != 0)and(goal_nixushu % 2 == 0):
# 如果奇偶性不同,返回-1,表示无解
return -1,None
#1、定义好基本的变量,做准备
#定义队列state的最大入队元素数量(最大搜索节点数,避免不可到达而死循环)
Max_st = 100000
#定义队列st、距离数组distance、存储父亲节点索引的fu
st = []
distance = list(range(Max_st))
fu = list(range(Max_st))
#注意:st的元素都是二元组,需要单独定义,开一个这样的列表
for i in range(Max_st):
st.append((i,"012345678"))
#定义队首指针front、队尾指针rear
front,rear = 1,2
#定义好上下左右四个操作,对x\y改变的两个数组
dx = [-1,1,0,0]
dy = [0,0,-1,1]
#求出initial到goal的曼哈顿距离,初始化distance,fu、st、init_lookup_table
initial_f = 0 + 3*man_ha_dun(initial,goal)
distance[1] = 0 #表示初始状态到初始状态的距离为0
fu[1] = -1 #表示初始状态没有父结点
#将节点表示为元组的形式,保存在查找表、st中(元组的1号位表示代价,2号位表示字符序列)
initial_st = (initial_f,initial)
st[front] = initial_st
global init_lookup_table
init_lookup_table.append(initial_st)
count_iter = 0 #记录循环次数
#3、开始搜索
while front != rear:
#判断当前队首节点是否为goal_st,如果是,则返回与initale的距离、访问路径
if st[front][1] == goal:
da_ying = [st[front][1]] #用于反向打印
fu_index = front #定义一个变量,记录当前结点的父节点索引
while fu[fu_index] != -1: #初始状态没有父节点
#把当前节点的父节点添加进打印队列中
da_ying.append(st[fu[fu_index]][1])
#准备把父节点的父节点加入队列
fu_index = fu[fu_index]
return distance[front],da_ying
#否则扩展队首节点,按照0元素上下左右
#先找到0元素的一维下标z
z = 0
for i in range(9):
if st[front][1][i] == '0':
z = i
break
#再算0的二维坐标
x = z // 3
y = z % 3
for i in range(4): #开始扩展节点
new_x = x + dx[i] #移动s后的X坐标
new_y = y + dy[i] #移动后的Y坐标
new_z = new_x * 3 + new_y #移动后的一维坐标
if (new_x>=0) and (new_x<3) and (new_y>=0) and (new_y<3): #判断移动是否合法
#如果移动合法,产生新节点(交换两个字符的位置),添加至队尾
if z < new_z:
state_rear = st[front][1][:z] + st[front][1][new_z] + st[front][1][z+1:new_z] + st[front][1][z] + st[front][1][new_z+1:]
else:
state_rear = st[front][1][:new_z] + st[front][1][z] + st[front][1][new_z + 1:z] + st[front][1][new_z] + st[front][1][z+1:]
#把该节点的f值,算出来
state_rear_f = (distance[front]+1) + 3*man_ha_dun(state_rear,goal)
#然后创建该节点,加入列表st(修改st[rear]的值)
st[rear] = (state_rear_f,state_rear)
#更新dist、fu
distance[rear] = distance[front] + 1 #表示新增节点与父节点的距离
fu[rear] = front
#最后判断这个新节点st[rear],是否出现过
if try_to_insert(st[rear]):
rear += 1 #队尾指针+1
#队首指针+1,出队
front += 1
#在扩展完队头节点以后,利用f值,对所有队列中的剩余节点排序,决定访问次序
st[front:rear] = soreted_st_state(st[front:rear])
#定期打印,方便用户查看
count_iter += 1 #表示循环次数加一
if count_iter % 800 ==0:
print("当前循环次数为:%d"%count_iter)
print("当前的队首节点是:",st[front])
if __name__ == '__main__':
# 1、输入初始状态、目标状态
initial = input("请输入初始状态:")
goal = input("请输入目标状态:")
# 2、用A*算法搜索目标状态,如果可以找到,返回初始状态与目标状态的距离,否则返回-1,表示不能找到目标状态
try:
answer,lu_jing = A_star(initial,goal)
except:
print("Error:输入的状态不是为0-8的9个数字(可能含有别的字符,或者输入超过限制)")
else:
#如果无法找到目标状态
if answer == -1:
print("无法从初始状态%s到达目标状态%s,请重新输入参数"%(initial,goal))
else:
print("从当前状态%s到达目标状态%s,需要%d步"%(initial,goal,answer))
# 3、打印路径
print("搜索路径为:")
for i in range(len(lu_jing)-1,-1,-1): #反向打印,从初始状态开始开始
print(lu_jing[i],end="\t")
if i % 10 == 0:
print("\n")
#这个表,有时候很长,妨碍看结果,就不打印了
#4、打印查找表,返回已经扩展的结点
# print("队列中已经扩展的结点为:")
# for i in range(len(init_lookup_table)):
# print(init_lookup_table[i][1],end='\t')
# if i % 10 == 0:
# print('\n')
#全民制作人:聂韬、孙文、赵广荣——————2024.5.13
四、写在最后的话
下面相关的视频链接,精心挑选的,可以看一下:
要学的还有很多,代码实战很关键啊。
标签:
相关文章
最新发布
- 光流法结合深度学习神经网络的原理及应用(完整代码都有Python opencv)
- Python 图像处理进阶:特征提取与图像分类
- 大数据可视化分析-基于python的电影数据分析及可视化系统_9532dr50
- 【Python】入门(运算、输出、数据类型)
- 【Python】第一弹---解锁编程新世界:深入理解计算机基础与Python入门指南
- 华为OD机试E卷 --第k个排列 --24年OD统一考试(Java & JS & Python & C & C++)
- Python已安装包在import时报错未找到的解决方法
- 【Python】自动化神器PyAutoGUI —告别手动操作,一键模拟鼠标键盘,玩转微信及各种软件自动化
- Pycharm连接SQL Sever(详细教程)
- Python编程练习题及解析(49题)
点击排行
- 版本匹配指南:Numpy版本和Python版本的对应关系
- 版本匹配指南:PyTorch版本、torchvision 版本和Python版本的对应关系
- Python 可视化 web 神器:streamlit、Gradio、dash、nicegui;低代码 Python Web 框架:PyWebIO
- 相关性分析——Pearson相关系数+热力图(附data和Python完整代码)
- Anaconda版本和Python版本对应关系(持续更新...)
- Python与PyTorch的版本对应
- Windows上安装 Python 环境并配置环境变量 (超详细教程)
- Python pyinstaller打包exe最完整教程