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

八数码问题（也称为滑动拼图游戏）是一个典型的启发式搜索问题，可以使用A*算法来解决。A*算法结合了最佳优先搜索（Best First Search）和启发式函数来找到从起始状态到目标状态的最短路径。以下是实现A*算法的基本步骤：

1. **初始化**：创建一个队列，将起始状态放入其中，并设置当前节点为起始状态。

2. **计算F值**：对于每个节点，计算两个值：G值（从初始状态到当前状态的实际代价），通常为1；H值（启发式估计，从当前状态到目标状态的最小代价）。F值等于G值加上H值。

3. **选择节点**：从队列中选择F值最小的节点作为下一个执行节点。

4. **扩展节点**：如果当前节点是目标状态，则搜索结束；否则，将其所有可行的相邻状态加入队列，更新它们的G、H和F值。

5. **递归过程**：重复步骤2-4，直到找到目标状态或队列为空。

对于不同的估价函数设计，我们可以有：

- **曼哈顿距离**：每个棋子移动一个位置相当于平移一格，总和各个棋子横纵坐标之差的绝对值。简单直观，但可能不是最优的。

- **欧几里得距离**：计算棋子到目标棋盘位置的直线距离平方的平方根。比曼哈顿距离更精细，但也更复杂一些。

在实现时，你需要为每个节点维护一个评估函数的实例，例如`HeuristicFunction`类，它有一个计算方法`calculate()`，返回从当前节点到目标节点的估算费用。然后在A*搜索过程中，每次节点选择和扩展时都会调用这个方法。

class ManhattanDistance(HeuristicFunction):
    # 实现计算曼哈顿距离的方法

class EuclideanDistance(HeuristicFunction):
    # 实现计算欧几里得距离的方法

def a_star(start_state, goal_state):
    open_list = PriorityQueue()
    start_state.g = 0
    start_state.h = manhattan_distance(start_state, goal_state) or euclidean_distance(start_state, goal_state)
    start_state.f = start_state.g + start_state.h
    open_list.enqueue(start_state)

    while not open_list.is_empty():
        current_state = open_list.dequeue()

        # 检查是否达到目标
        if current_state == goal_state:
            return reconstruct_path(current_state)

        # 扩展节点并更新开放列表
        for next_state in get_neighbors(current_state):
            tentative_g = current_state.g + cost_between(current_state, next_state)
            if next_state not in closed_list or tentative_g < next_state.g:
                next_state.g = tentative_g
                next_state.h = ...  # 根据选择的估价函数计算
                next_state.f = next_state.g + next_state.h
                open_list.enqueue(next_state)