A*

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'))