苏州网站建设公司哪个好/代写文章质量高的平台

在C++和Python之间切换

有一段时间没有使用Python，要练练手。
关于八数码问题的A${}^{\ast }$算法，网上有很多，基本拜读了，受益匪浅。之前觉得用A${}^{\ast }$算法不能肯定能够获得最短途径。但仔细分析发现，其实很多的A${}^{\ast }$算法与Dijkstra算法基本一致，就此确定能够获得最短路径，至于原因，读者可自行百度Dijkstra算法。大致的思路如下。
1、判断是否有解，无解直接退出，有解进入步骤2。
2、建立Open和Close两个数组，Open初始化放入source（包括步长为0，评价值，source，父状态（为空））。
3、对Open中的第一个数据（序号0）进行扩展，得到几个次生状态：如果既不在Open也不在Close中，直接添加到Open中；如果已经在Close中，则放弃；如果在Open中，比较两者的评价值，把较小的那个留在Open中。然后将这个数据（序号0）从Open中删除，放到Close中去。如果次生状态与目标状态相同，进入步骤5，否则进入步骤4。
4、对Open数组以评价值为关键字进行排序，这样保证步骤3中的第一个数据是当前选出距目标最近的一个状态数据。重复步骤3，步骤4，直至找到目标状态。
5、通过当前状态的父状态回溯到source后输出完整状态变化信息，程序结束。
6、关于评价值问题。这是成败的关键。本文采用曼哈顿距离结合差异值进行评估，包含次生状态已经历的步长和次生状态到目标状态的估价值等基本数据，程序运行时间大大缩短。
程序完整清单如下：

# 统计从一个状态（father）变化到下一个状态（sun）的所有列表
def moving(state):_sun = []zero_ind = state.index(0)for b in base[zero_ind]:te = copy.deepcopy(state)te[b], te[zero_ind] = 0, te[b]_sun.append(te)return _sun# 判断是否有解
def solution(state):ct = 0for k in range(9):if state[k] != 0:for j in range(k):if state[j] > state[k]:ct += 1return ct# 计算曼哈顿距离
def manhattan(storey, state):global targetcount = storeyfor i in range(9):if target[i] != 0:for j in range(9):if state[j] == target[i]:count += abs(j % 3 - i % 3) + abs(j // 3 - i // 3)breakreturn count# 计算当前状态与目标状态的差异值，逐位比较，有差异就累加1
def diff(layer, state):_diff = layerfor _i in range(9):if state[_i] != target[_i]:_diff += 1return _diff# 回溯，显示移动路径
def trace():result.append(target)_father = Close[-1][3]while True:if _father == source:result.insert(0, source)breakfor c in Close:if c[2] == _father:result.insert(0, _father)_father = c[3]breakfor r in result:print(r)if __name__ == '__main__':import timeimport copysource = [1, 2, 3, 4, 0, 5, 6, 7, 8]  # 19步target = [7, 6, 4, 0, 2, 1, 8, 5, 3]source = [1, 2, 3, 4, 0, 5, 6, 7, 8]  # 28步target = [0, 8, 7, 6, 5, 4, 3, 2, 1]source = [1, 2, 3, 4, 0, 5, 6, 7, 8]  # 28步target = [5, 6, 7, 8, 0, 1, 2, 3, 4]source = [8, 3, 6, 5, 7, 4, 2, 1, 0]  # 29步target = [1, 0, 2, 3, 4, 5, 6, 7, 8]source = [1, 2, 3, 4, 0, 5, 6, 7, 8]  # 30步target = [8, 7, 6, 5, 0, 4, 3, 2, 1]# 记录空格（0）从一个状态（位置）变化到下一个状态（位置）信息base = [[1, 3], [0, 2, 4], [1, 5], [0, 4, 6], [1, 3, 5, 7], [2, 4, 8], [3, 7], [4, 6, 8], [5, 7]]Open, Close = [], []# layer = 0result = []print("source", source)print("target", target)if source == target:print("成功！共搜索 0 层。")exit(0)c1, c2 = solution(source), solution(target)if (c1 + c2) % 2 != 0:print("无解！")exit()t0 = time.time()dis = manhattan(0, source)Open.append([0, dis, source, []])while True:father = Open[0]Open.remove(father)Close.append(father)sun = moving(father[2])if target in sun:dis = manhattan(father[0] + 1, target)Close.append([father[0] + 1, dis, target, father[2]])trace()print("成功！共搜索", len(result) - 1, "层。")print("耗时{}s。".format(time.time() - t0))exit(0)for un in sun:mark = 0dis = manhattan(father[0] + 1, un) / diff(father[0] + 210, un)  # 评估值，关键数据for pen in Open:if pen[2] == un:if dis < pen[1]:Open.remove(pen)Open.append([father[0] + 1, dis, un, father[2]])mark = 1breakif mark == 1:continuefor lose in Close:if lose[2] == un:mark = 1breakif mark == 0:Open.append([father[0] + 1, dis, un, father[2]])Open = sorted(Open, key=lambda x: x[1])

运行结果如下，运算时间还是比较感人的：

D:\Python\Python38\python.exe D:/Python/study/20201210.py
source [1, 2, 3, 4, 0, 5, 6, 7, 8]
target [8, 7, 6, 5, 0, 4, 3, 2, 1]
[1, 2, 3, 4, 0, 5, 6, 7, 8]
[1, 0, 3, 4, 2, 5, 6, 7, 8]
[0, 1, 3, 4, 2, 5, 6, 7, 8]
[4, 1, 3, 0, 2, 5, 6, 7, 8]
[4, 1, 3, 6, 2, 5, 0, 7, 8]
[4, 1, 3, 6, 2, 5, 7, 0, 8]
[4, 1, 3, 6, 2, 5, 7, 8, 0]
[4, 1, 3, 6, 2, 0, 7, 8, 5]
[4, 1, 0, 6, 2, 3, 7, 8, 5]
[4, 0, 1, 6, 2, 3, 7, 8, 5]
[0, 4, 1, 6, 2, 3, 7, 8, 5]
[6, 4, 1, 0, 2, 3, 7, 8, 5]
[6, 4, 1, 7, 2, 3, 0, 8, 5]
[6, 4, 1, 7, 2, 3, 8, 0, 5]
[6, 4, 1, 7, 2, 3, 8, 5, 0]
[6, 4, 1, 7, 2, 0, 8, 5, 3]
[6, 4, 0, 7, 2, 1, 8, 5, 3]
[6, 0, 4, 7, 2, 1, 8, 5, 3]
[0, 6, 4, 7, 2, 1, 8, 5, 3]
[7, 6, 4, 0, 2, 1, 8, 5, 3]
[7, 6, 4, 8, 2, 1, 0, 5, 3]
[7, 6, 4, 8, 2, 1, 5, 0, 3]
[7, 6, 4, 8, 2, 1, 5, 3, 0]
[7, 6, 4, 8, 2, 0, 5, 3, 1]
[7, 6, 0, 8, 2, 4, 5, 3, 1]
[7, 0, 6, 8, 2, 4, 5, 3, 1]
[0, 7, 6, 8, 2, 4, 5, 3, 1]
[8, 7, 6, 0, 2, 4, 5, 3, 1]
[8, 7, 6, 5, 2, 4, 0, 3, 1]
[8, 7, 6, 5, 2, 4, 3, 0, 1]
[8, 7, 6, 5, 0, 4, 3, 2, 1]
成功！共搜索 30 层。
耗时1.1131258010864258s。Process finished with exit code 0