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

8数码问题（8-puzzle）是一个经典的搜索问题，目标是将一个3x3的矩阵中的数字1~8按照特定的顺序排列，初始状态是乱序的。每一次可以将数字与空格交换位置，目标是通过交换操作尽快到达目标状态。

A*算法是一种启发式搜索算法，可以用于解决8数码问题。它通过估计从当前状态到目标状态的代价来指导搜索方向，其中估价函数是关键。

以下是一个基于Python实现的A*算法求解8数码问题的程序，包括两种不同的估价函数。

import heapq

# 估价函数1：曼哈顿距离
def h1(state):
    dist = 0
    for i in range(3):
        for j in range(3):
            if state[i][j] == 0:
                continue
            x, y = (state[i][j] - 1) // 3, (state[i][j] - 1) % 3
            dist += abs(x - i) + abs(y - j)
    return dist

# 估价函数2：错位数
def h2(state):
    count = 0
    for i in range(3):
        for j in range(3):
            if state[i][j] == 0:
                continue
            if state[i][j] != 3 * i + j + 1:
                count += 1
    return count

# A*算法
def A_star(start, goal, h):
    open_list = [(h(start), start)]
    closed_set = set()
    g_score = {tuple(map(tuple, start)): 0}
    came_from = {}
    
    while open_list:
        _, current = heapq.heappop(open_list)
        if current == goal:
            path = []
            while current in came_from:
                path.append(current)
                current = came_from[current]
            path.append(start)
            return path[::-1]
        
        closed_set.add(tuple(map(tuple, current)))
        for i, j in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            new_x, new_y = i + current.index([0]), j + current[current.index([0])].index(0)
            if 0 <= new_x < 3 and 0 <= new_y < 3:
                neighbor = [list(row) for row in current]
                neighbor[current.index([0])][current[current.index([0])].index(0)], neighbor[new_x][new_y] = neighbor[new_x][new_y], neighbor[current.index([0])][current[current.index([0])].index(0)]
                tentative_g_score = g_score[tuple(map(tuple, current))] + 1
                if tuple(map(tuple, neighbor)) in closed_set:
                    continue
                if (tentative_g_score + h(neighbor), neighbor) not in open_list:
                    heapq.heappush(open_list, (tentative_g_score + h(neighbor), neighbor))
                elif tentative_g_score >= g_score.get(tuple(map(tuple, neighbor)), float('inf')):
                    continue
                came_from[tuple(map(tuple, neighbor))] = tuple(map(tuple, current))
                g_score[tuple(map(tuple, neighbor))] = tentative_g_score
    
    return None

# 测试
start = [[2, 8, 3], [1, 6, 4], [7, 0, 5]]
goal = [[1, 2, 3], [8, 0, 4], [7, 6, 5]]

print(A_star(start, goal, h1))
print(A_star(start, goal, h2))

该程序中，`h1`和`h2`分别是两种不同的估价函数。`A_star`函数使用了一个优先队列`open_list`，以及一个集合`closed_set`来存储已经扩展过的状态。`g_score`字典存储了起点到每个状态的最短距离，`came_from`字典则存储了每个状态的前驱状态。在搜索过程中，每次取出`open_list`中代价最小的状态进行扩展，直到找到目标状态或者`open_list`为空。

在测试部分，我们将初始状态和目标状态分别设置为`start`和`goal`，并分别使用`h1`和`h2`求解。程序输出的是求解出的最短路径，即一系列状态的列表。

需要注意的是，在实现中，我们将每个状态都转换成了一个元组，以便于存储在字典中。在比较状态是否相等时，也需要将其转换为元组进行比较。