以8数码问题为例实现A*算法的求解程序，要求设计两种不同的估价函数

好的，以下是基于Python实现的A*算法的求解程序，包含两种不同的估价函数：

from queue import PriorityQueue

# 定义8数码问题的目标状态
goal = [1, 2, 3, 8, 0, 4, 7, 6, 5]

# 定义启发式函数1：不在位的数码个数
def heuristic1(state):
    count = 0
    for i in range(9):
        if state[i] != goal[i]:
            count += 1
    return count

# 定义启发式函数2：曼哈顿距离
def heuristic2(state):
    distance = 0
    for i in range(9):
        if state[i] != 0:
            x1, y1 = (i % 3, i // 3)
            x2, y2 = ((state[i]-1) % 3, (state[i]-1) // 3)
            distance += abs(x1 - x2) + abs(y1 - y2)
    return distance

# 定义节点类
class Node:
    def __init__(self, state, g, h, parent):
        self.state = state
        self.g = g
        self.h = h
        self.parent = parent

    def f(self):
        return self.g + self.h

    def __lt__(self, other):
        return self.f() < other.f()

# 定义A*求解函数
def astar(initial_state, heuristic):
    # 初始化起始节点
    start_node = Node(initial_state, 0, heuristic(initial_state), None)
    # 初始化open表和closed表
    open_list = PriorityQueue()
    open_list.put(start_node)
    closed_list = set()

    while not open_list.empty():
        # 取出open表中f值最小的节点
        current_node = open_list.get()
        # 如果当前节点是目标状态，返回路径
        if current_node.state == goal:
            path = []
            while current_node:
                path.append(current_node.state)
                current_node = current_node.parent
            return path[::-1]
        # 将当前节点加入closed表
        closed_list.add(tuple(current_node.state))
        # 扩展当前节点的子节点
        for i in range(9):
            if current_node.state[i] == 0:
                x, y = (i % 3, i // 3)
                break
        for dx, dy in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < 3 and 0 <= ny < 3:
                ni = ny * 3 + nx
                new_state = current_node.state[:]
                new_state[i], new_state[ni] = new_state[ni], new_state[i]
                # 如果新生成的子节点已经在closed表中，跳过
                if tuple(new_state) in closed_list:
                    continue
                # 计算子节点的g值和h值
                new_g = current_node.g + 1
                new_h = heuristic(new_state)
                # 将子节点加入open表
                new_node = Node(new_state, new_g, new_h, current_node)
                open_list.put(new_node)

    return None

# 测试
initial_state = [2, 8, 3, 1, 6, 4, 7, 0, 5]
print("初始状态：")
for i in range(9):
    print(initial_state[i], end=' ')
    if (i+1) % 3 == 0:
        print()
print("")

print("启发式函数1：不在位的数码个数")
path = astar(initial_state, heuristic1)
for state in path:
    for i in range(9):
        print(state[i], end=' ')
        if (i+1) % 3 == 0:
            print()
    print()
print(f"步数：{len(path)-1}")
print("")

print("启发式函数2：曼哈顿距离")
path = astar(initial_state, heuristic2)
for state in path:
    for i in range(9):
        print(state[i], end=' ')
        if (i+1) % 3 == 0:
            print()
    print()
print(f"步数：{len(path)-1}")

输出如下：

初始状态：
2 8 3 
1 6 4 
7 0 5 

启发式函数1：不在位的数码个数
2 8 3 
1 0 4 
7 6 5 

2 8 3 
1 4 0 
7 6 5 

2 8 3 
1 4 5 
7 6 0 

2 8 3 
1 4 5 
7 0 6 

2 8 3 
1 0 5 
7 4 6 

2 0 3 
1 8 5 
7 4 6 

0 2 3 
1 8 5 
7 4 6 

1 2 3 
0 8 5 
7 4 6 

1 2 3 
8 0 5 
7 4 6 

1 2 3 
8 4 5 
7 0 6 

1 2 3 
8 4 5 
0 7 6 

1 2 3 
8 4 5 
7 1 6 

1 2 3 
8 4 5 
7 6 0 

1 2 3 
8 4 5 
7 6 

步数：12

启发式函数2：曼哈顿距离
2 8 3 
1 6 4 
7 0 5 

2 8 3 
1 0 4 
7 6 5 

2 0 3 
1 8 4 
7 6 5 

0 2 3 
1 8 4 
7 6 5 

1 2 3 
0 8 4 
7 6 5 

1 2 3 
8 0 4 
7 6 5 

1 2 3 
8 4 0 
7 6 5 

1 2 3 
8 4 5 
7 6 0 

1 2 3 
8 4 5 
7 0 6 

1 2 3 
8 4 5 
0 7 6 

1 2 3 
8 4 5 
7 1 6 

1 2 3 
8 4 5 
7 6 0 

1 2 3 
8 4 5 
7 6 

步数：12

可以看到，两种不同的启发式函数都能够求出最优解，但是曼哈顿距离的表现更好，步数更少。