python简单编程八数码问题

实现结果：给定八数码的起始状态和目标状态，程序可以自动计算出所需要的步数，并能打印出每一步的变化。

使用深度搜索

import time as tm
g_dict_layouts = {}
#每个位置可交换的位置集合
g_dict_shifts = {0:[1, 3], 1:[0, 2, 4], 2:[1, 5],3:[0,4,6], 4:[1,3,5,7], 5:[2,4,8],6:[3,7],  7:[4,6,8], 8:[5,7]}def swap_chr(a, i, j):if i > j:i, j = j, i#得到ij交换后的数组b = a[:i] + a[j] + a[i+1:j] + a[i] + a[j+1:]return bdef solvePuzzle_depth(srcLayout, destLayout):#先进行判断srcLayout和destLayout逆序值是否同是奇数或偶数#这是判断起始状态是否能够到达目标状态，同奇同偶时才是可达src=0;dest=0for i in range(1,9):fist=0for j in range(0,i):if srcLayout[j]>srcLayout[i] and srcLayout[i]!='0':#0是false,'0'才是数字fist=fist+1src=src+fistfor i in range(1,9):fist=0for j in range(0,i):if destLayout[j]>destLayout[i] and destLayout[i]!='0':fist=fist+1dest=dest+fistif (src%2)!=(dest%2):#一个奇数一个偶数，不可达return -1, None#初始化字典g_dict_layouts[srcLayout] = -1stack_layouts = []stack_layouts.append(srcLayout)#当前状态存入列表bFound = Falsewhile len(stack_layouts) > 0:curLayout = stack_layouts.pop()#出栈if curLayout == destLayout:#判断当前状态是否为目标状态break# 寻找0 的位置。ind_slide = curLayout.index("0")lst_shifts = g_dict_shifts[ind_slide]#当前可进行交换的位置集合for nShift in lst_shifts:newLayout = swap_chr(curLayout, nShift, ind_slide)if g_dict_layouts.get(newLayout) == None:#判断交换后的状态是否已经查询过g_dict_layouts[newLayout] = curLayoutstack_layouts.append(newLayout)#存入集合lst_steps = []lst_steps.append(curLayout)while g_dict_layouts[curLayout] != -1:#存入路径curLayout = g_dict_layouts[curLayout]lst_steps.append(curLayout)lst_steps.reverse()return 0, lst_stepsif __name__ == "__main__":#测试数据输入格式srcLayout  = "541203786"destLayout = "123804765"retCode, lst_steps = solvePuzzle_depth(srcLayout, destLayout)if retCode != 0:print("目标布局不可达")else:for nIndex in range(len(lst_steps)):print("step #" + str(nIndex + 1))print(lst_steps[nIndex][:3])print(lst_steps[nIndex][3:6])print(lst_steps[nIndex][6:])

深度搜索：以栈为容器。由于每次将可能的新状态入栈，并标记为已经搜索到，当一直深入时便会遇到下一步可能搜索到的所有状态都已经标记为搜索过了，即没有可入栈的，这条深度搜索路线结束，下次出栈为栈顶状态，即另一条深度搜索路线。因为进行搜索之前判断了是否可达，所以进入搜索必有解，那么会按上述进行，直到找到目标状态。

广度搜索

最简单的方法是在上述深度搜索代码上进行改动，即可进行广度搜索。

curLayout = stack_layouts.pop(0) #把栈改成队列

深度是将集合中的元素从末尾取出，即和栈的特点相同，那么将先进后出变为先进先出，即将栈改成了队列。
广度将集合中的元素从头部取出，集合变量名.pop(0)，指定头部取出。

A*算法实现

A*算法是一种预测算法，主要用于寻路等，根据当前状态和目标状态之间的差异，预测到达目标需要多少开销，根据这个开销来判断下一次选择以那个状态开始。这个开销在八数码问题中可以以路程为标准。
A*算法公式：

F(N)=G(N)+H(N)

F(N)表示当前状态到达目标状态所用开销
G(N)表示从起点状态到当前状态所用开销
H(N)在本问题中可以将当前状态9个数字展开成一列，位置从1到9，将当前状态数字所在位置和目标状态该数字所在位置进行相减取绝对值，依次获得8个数（0表示空位，不进行计算）的差值，相加所得即为H(N)的值。原理是每个数当前位置和其应在位置的距离是接下来到达目标大概开销。

H(N)计算示例：
当前状态012345678
目标状态123456780
其中1分别在2号位和1号位，差取绝对值为1，同理其他的数计算结果为：1、1、1、1、1、1、1。
H(N)=1+1+1+1+1+1+1+1=8

import time as tm
g_dict_layouts = {}
g_dict_layouts_deep = {}
g_dict_layouts_fn = {}
#每个位置可交换的位置集合
g_dict_shifts = {0:[1, 3], 1:[0, 2, 4], 2:[1, 5],3:[0,4,6], 4:[1,3,5,7], 5:[2,4,8],6:[3,7],  7:[4,6,8], 8:[5,7]}
def swap_chr(a, i, j, deep, destLayout):if i > j:i, j = j, i#得到ij交换后的数组b = a[:i] + a[j] + a[i+1:j] + a[i] + a[j+1:]#存储fn,A*算法fn = cal_dislocation_sum(b, destLayout)+deepreturn b, fn
#返回错码和正确码距离之和
def cal_dislocation_sum(srcLayout,destLayout):sum=0a= srcLayout.index("0")for i in range(0,9):if i!=a:sum=sum+abs(i-destLayout.index(srcLayout[i]))return sum
def solvePuzzle_A(srcLayout, destLayout):#先进行判断srcLayout和destLayout逆序值是否同是奇数或偶数src=0;dest=0for i in range(1,9):fist=0for j in range(0,i):if srcLayout[j]>srcLayout[i] and srcLayout[i]!='0':#0是false,'0'才是数字fist=fist+1src=src+fistfor i in range(1,9):fist=0for j in range(0,i):if destLayout[j]>destLayout[i] and destLayout[i]!='0':fist=fist+1dest=dest+fistif (src%2)!=(dest%2):#一个奇数一个偶数，不可达return -1, Noneg_dict_layouts[srcLayout] = -1g_dict_layouts_deep[srcLayout]= 1g_dict_layouts_fn[srcLayout] = 1 + cal_dislocation_sum(srcLayout, destLayout)stack_layouts = []gn=0#深度值stack_layouts.append(srcLayout)#当前状态存入列表while len(stack_layouts) > 0:curLayout = min(g_dict_layouts_fn, key=g_dict_layouts_fn.get)del g_dict_layouts_fn[curLayout]stack_layouts.remove(curLayout)#找到最小fn，并移除# curLayout = stack_layouts.pop()if curLayout == destLayout:#判断当前状态是否为目标状态break# 寻找0 的位置。ind_slide = curLayout.index("0")lst_shifts = g_dict_shifts[ind_slide]#当前可进行交换的位置集合for nShift in lst_shifts:newLayout, fn = swap_chr(curLayout, nShift, ind_slide, g_dict_layouts_deep[curLayout] + 1, destLayout)if g_dict_layouts.get(newLayout) == None:#判断交换后的状态是否已经查询过g_dict_layouts_deep[newLayout] = g_dict_layouts_deep[curLayout] + 1#存入深度g_dict_layouts_fn[newLayout] = fn#存入fng_dict_layouts[newLayout] = curLayout#定义前驱结点stack_layouts.append(newLayout)#存入集合lst_steps = []lst_steps.append(curLayout)while g_dict_layouts[curLayout] != -1:#存入路径curLayout = g_dict_layouts[curLayout]lst_steps.append(curLayout)lst_steps.reverse()return 0, lst_steps
if __name__ == "__main__":#测试数据srcLayout  = "013425786"destLayout = "647850321"retCode, lst_steps = solvePuzzle_A(srcLayout, destLayout)if retCode != 0:print("目标布局不可达")else:for nIndex in range(len(lst_steps)):print("step #" + str(nIndex + 1))print(lst_steps[nIndex][:3])print(lst_steps[nIndex][3:6])print(lst_steps[nIndex][6:])

三种算法差异

广度搜索和深度搜索是按不同方法来进行搜索，如果找寻步数最少解，广度可以得到最优值，如果搜索时间，那么广度和深度要以问题情况进行选择。A*算法是一种预测算法，时间开销相对较低，但是不能保证解为最优值，时间开销方面相对于前两种较小，但也视问题规模和情况具体分析。

以上为自己的理解和表述，若有不足请包涵。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！