A*算法
A* 算法维护一个优先级队列，结点的优先级由$f(n)$的值决定，$f(n)$值越小，结点的优先级越高。$f(n) = g(n)+h(n)$，其中$g(n)$为结点从起始状态到当前状态所花费的代价，$h(n)$为当前状态到终止状态距离的估计代价，为启发式函数。当$h(n)$小于等于结点n到终止状态的实际代价，则A* 算法一定能找到最优路径。
以下为 A* 的伪代码：
初始化优先级队列OPEN，CLOSE(OPEN里为待展开的结点，CLOSE中表示已经展开的结点)
将初始状态加入OPEN
while OPEN:
n⬅OPEN中弹出优先级最高的结点
将n加入CLOSE
如果n为终止结点:
找n的parent，直到起始状态
return
遍历n的邻近结点m:
如果m在CLOSE中:
continue
如果m也不在OPEN中:
设置m的parent为n
将m加入OPEN中Q: 森林宝石的秘密通道
题目描述：
在一个神秘的森林里，有一块由9个小方格组成的魔法石板。石板上有8个宝石，每个宝石上刻有1-8中的一个数字(每个数字都不重复）。石板上还有一个空位，用0表示。通过移动空位周围的宝石，你可以改变宝石的位置。传说中，当宝石按照某个特定的顺序排列时(本题设为135702684)，魔法石板将会显露出通往一个宝藏的秘密通道。
现在，你站在这块魔法石板前，需要找到一种最少步骤的移动方法，将宝石排列成目标顺序。为了解开这个谜题，请使用A*算法来设计一个程序，帮助你从初始状态成功解锁秘密通道。
要求：要求只能用A*算法。
输入格式：一行介个数字，空格用0表示，除0之外，分别表示从左到右从上到下的对应宝石上的数字。
输入格式：只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)。
输入输出样例：
输入：150732684
输出：2
# 该函数返回启发式函数的值，current_node为当前结点矩阵，goal_node为目标结点矩阵
def heuristic_f(current_node, goal_node):
h = 0
rows = current_node.shape[0]
cols = current_node.shape[1]
for i in range(rows):
for j in range(cols):
if current_node[i][j] != goal_node[i][j] and current_node[i][j]!=0:
goal_x = np.argwhere(goal_node==current_node[i][j])[0][0]
goal_y = np.argwhere(goal_node==current_node[i][j])[0][1]
h += (abs(i-goal_x) + abs(j-goal_y))
return h将open_list定义为一个按照f升序排列的列表，其中为待展开的结点，close_list中存储已经展开的结点。当open_list不为空时，每次弹出第一个结点。
def main():
# 每个结点用一个字典表示
start = {}
input_order = list(input())
# 初始化3*3的输入矩阵
input_order = [int(x) for x in input_order]
start_node = np.array(input_order).reshape(3, 3)
start['node'] = start_node
start['parent'] = {}
start['steps'] = get_steps(start['node'])
start['g'] = 0
start['h'] = heuristic_f(start['node'], goal['node'])
start['f'] = start['g'] + start['h']
# openlist中存储待展开的结点，closelist中存储已经展开的节点
openlist = []
closelist = []
openlist.append(start)
while openlist:
current = openlist.pop(0)
closelist.append(current)
# 如果当前展开的结点与目标结点一致，则返回
if (current['node'] == goal['node']).all():
print(current['g'])
p_list = []
p = current
while p:
p_list.append(p.get('node'))
p = p['parent']
p_list.reverse()
# print(p_list)
return
children = get_children(current)
for child in children:
# 判断该结点是否出现和待展开的结点列表和已经展开的结点列表
exist_open = False
exist_close = False
for i in range(len(openlist)):
if (child['node'] == openlist[i]['node']).all():
exist_open = True
# 如果该孩子结点的f小于与它展开相等的在openlist结点的值，则用该孩子结点替代
if child['f'] < openlist[i]['f']:
del openlist[i]
openlist.append(child)
break
for j in range(len(closelist)):
if (child['node'] == closelist[j]['node']).all():
exist_close = True
break
if exist_open == False and exist_close == False:
openlist.append(child)
openlist = sorted(openlist, key=itemgetter('f'))
