8数码问题Best First Search Python实现异常：路径与A*一致+启发式值异常

首先，你的代码里有几个核心问题导致了当前的异常现象：启发式函数被硬编码固定为1、目标tile位置的存储方式错误，还有路径代价gn的计算逻辑错误。下面一步步拆解并给出修复方案：

1. 为什么启发式值始终输出1？ #

看你search函数里的这段代码：

def fn(node):
    return 1

你把Best First Search的核心评估函数f(n)直接固定返回1了！不管当前节点是什么状态，调用这个函数都会得到1，这就是所有状态下输出都是1的根本原因——你完全没用到自己定义的曼哈顿距离启发式hn。

2. 为什么路径和A*一致？ #

当前你的“Best First Search”本质上是广度优先搜索（BFS）：所有节点的优先级都是1，heapq会按照第二个参数entrance（入队顺序）来排序，先入队的节点先被弹出，这和BFS的队列行为完全一致。如果你的A算法也存在类似的错误（比如没正确实现g(n)+h(n)），或者测试用例中BFS的路径刚好和正确A的路径重合，就会出现两者路径相同的情况。

3. 为什么你的曼哈顿距离启发式没生效？ #

你用heapq来存储目标状态中每个tile的位置，这是完全错误的！heapq是用来实现优先队列的排序结构，不是键值对查找工具。比如目标状态中的tile值8，你想用tiles_places[8]获取它的目标位置，但tiles_places是堆结构，索引8对应的是另一个tile的位置，导致hn计算出的曼哈顿距离完全错误——哪怕你后续启用了hn，也得不到正确的启发式值。

4. 路径代价gn的计算错误 #

你的Node类里的gn方法会累加自身和所有父节点的cost，但每个节点的cost已经是parent.cost + 1（在expand方法里设置的），所以node.cost本身就是从初始状态到当前状态的累计路径代价，不需要再重复累加父节点的cost。当前的gn方法会把路径代价计算成实际的2倍以上，比如从初始到当前走了4步，gn会算出0+1+2+3+4=10，这完全错误。

修正后的完整代码 #

下面是修复了所有问题的代码，包含真正的Best First Search（使用曼哈顿距离h(n)作为评估函数）和可选的A*算法（使用g(n)+h(n)），同时正确输出每个状态的启发式值：

from copy import deepcopy
import heapq

class Node:
    def __init__(self, state=None, parent=None, cost=0, depth=0):
        self.state = state
        self.parent = parent
        self.cost = cost  # cost已经是从初始到当前的累计代价
        self.depth = depth
        self.children = []

    def is_goal(self, goal_state):
        return is_goal_state(self.state, goal_state)

    def expand(self):
        new_states = operator(self.state)
        self.children = []
        for state in new_states:
            # 子节点的cost是父节点cost+1，正确累计路径代价
            self.children.append(Node(state, self, self.cost + 1, self.depth + 1))

    def parents(self):
        current_node = self
        while current_node.parent:
            yield current_node.parent
            current_node = current_node.parent

    def gn(self):
        # 直接返回累计的cost即可，不需要重复累加父节点
        return self.cost

def is_goal_state(state, goal_state):
    return state == goal_state  # 简化写法，二维列表可以直接比较

def operator(state):
    states = []
    zero_i, zero_j = None, None
    # 找到0的位置
    for i in range(len(state)):
        for j in range(len(state[i])):
            if state[i][j] == 0:
                zero_i, zero_j = i, j
                break
        if zero_i is not None:
            break

    def add_swap(i, j):
        new_state = deepcopy(state)
        new_state[i][j], new_state[zero_i][zero_j] = new_state[zero_i][zero_j], new_state[i][j]
        states.append(new_state)

    # 上下左右移动
    if zero_i != 0:
        add_swap(zero_i - 1, zero_j)
    if zero_j != 0:
        add_swap(zero_i, zero_j - 1)
    if zero_i != len(state) - 1:
        add_swap(zero_i + 1, zero_j)
    if zero_j != len(state[0]) - 1:
        add_swap(zero_i, zero_j + 1)
    return states

# 用户输入部分
def get_matrix(input_prompt):
    print(input_prompt)
    R = int(input("Enter the number of rows: "))
    C = int(input("Enter the number of columns: "))
    print("Enter the entries rowwise (space-separated per row):")
    matrix = []
    for _ in range(R):
        row = list(map(int, input().split()))
        matrix.append(row)
    # 打印输入的矩阵
    print("Your matrix:")
    for row in matrix:
        print(" ".join(map(str, row)))
    return matrix

initial_state = get_matrix("=== Enter initial state ===")
goal_state = get_matrix("=== Enter goal state ===")

def search(state, goal_state, use_best_first=True):
    # 用字典存储每个tile对应的目标位置，正确实现查找
    tile_goal_pos = {}
    for i in range(len(goal_state)):
        for j in range(len(goal_state[i])):
            tile_value = goal_state[i][j]
            tile_goal_pos[tile_value] = (i, j)

    # 曼哈顿距离启发式函数h(n)
    def hn(node):
        cost = 0
        for i in range(len(node.state)):
            for j in range(len(node.state[i])):
                tile_val = node.state[i][j]
                if tile_val == 0:
                    continue  # 0不需要计算距离
                goal_i, goal_j = tile_goal_pos[tile_val]
                cost += abs(goal_i - i) + abs(goal_j - j)
        return cost

    # 定义评估函数f(n)
    if use_best_first:
        # Best First Search: f(n) = h(n)
        def fn(node):
            return hn(node)
    else:
        # A*算法: f(n) = g(n) + h(n)
        def fn(node):
            return node.gn() + hn(node)

    # 优先队列搜索实现
    def priority_search(start_state, goal_state, fn):
        queue = []
        entrance = 0  # 解决优先级相同的节点排序问题
        start_node = Node(start_state)
        heapq.heappush(queue, (fn(start_node), entrance, start_node))
        entrance += 1

        while queue:
            current_priority, _, current_node = heapq.heappop(queue)
            if current_node.is_goal(goal_state):
                # 回溯路径
                path = []
                while current_node:
                    path.append(current_node.state)
                    current_node = current_node.parent
                path.reverse()
                return path, hn, fn

            current_node.expand()
            for child in current_node.children:
                heapq.heappush(queue, (fn(child), entrance, child))
                entrance += 1

        return None, hn, fn  # 无解的情况

    return priority_search(state, goal_state, fn)

# 选择算法：True=Best First Search，False=A*
path, hn_func, fn_func = search(initial_state, goal_state, use_best_first=True)

# 输出路径和对应的启发式值
print("\n=== Search Path ===")
for idx, state in enumerate(path):
    print(f"Step {idx+1}:")
    for row in state:
        print(" ".join(map(str, row)))
    current_node = Node(state)
    print(f"Heuristic h(n): {hn_func(current_node)}")
    print(f"Evaluation f(n): {fn_func(current_node)}")
    print("-"*20)

修正后的关键变化 #

1. 用字典存储目标tile位置：tile_goal_pos字典可以直接通过tile值获取其在目标状态中的坐标，确保曼哈顿距离计算正确。
2. 修复gn的计算：直接返回self.cost，因为cost已经是从初始到当前的累计路径代价。
3. 正确定义评估函数：
   • Best First Search使用f(n) = h(n)（仅启发式）
   • A*使用f(n) = g(n) + h(n)（路径代价+启发式）
4. 优化输入逻辑：允许一行输入多个数字，更方便用户操作。
5. 输出更清晰：同时显示启发式值h(n)和评估函数值f(n)，让你清楚看到算法的决策依据。

现在运行代码，你会看到每个状态的启发式值是正确的曼哈顿距离，而且Best First Search会优先选择启发式值最小的节点扩展，路径也会和BFS/A*产生明显区别（如果测试用例足够复杂的话）。

内容的提问来源于stack exchange，提问作者minsuga