如何在Prolog的8数码问题A*搜索中实现启发式与路径代价计算

核心思路梳理 #

A*算法的核心是基于f(n) = g(n) + h(n)的优先级搜索：

• g(n)：从初始状态到当前状态的路径代价（这里每步移动代价为1，等价于路径长度）
• h(n)：你已实现的启发式函数（统计非空格数码不在目标位置的数量）
• 每次从待扩展节点中选择f(n)最小的节点进行搜索，同时维护开放列表（待扩展）和关闭列表（已扩展）避免重复状态

完整代码实现 #

1. 目标状态定义 #

goal_state([[1,2,3],[8,0,4],[7,6,5]]).

2. 启发式函数（复用你的逻辑） #

% 计算不在目标位置的非空格数码数量
heuristic(State, H) :-
    goal_state(Goal),
    flatten(State, SFlat),
    flatten(Goal, GFlat),
    count_mismatches(SFlat, GFlat, H).

count_mismatches([], [], 0).
count_mismatches([S|Ss], [G|Gs], H) :-
    S = G, !,
    count_mismatches(Ss, Gs, H).
count_mismatches([S|Ss], [G|Gs], H) :-
    S \= G, S \= 0, % 空格不计入启发值
    count_mismatches(Ss, Gs, H1),
    H is H1 + 1.
count_mismatches([0|Ss], [G|Gs], H) :-
    count_mismatches(Ss, Gs, H).

3. 移动规则实现（补全基础逻辑） #

% 定位空格位置
find_zero(State, Row, Col) :-
    nth0(Row, State, RowList),
    nth0(Col, RowList, 0).

% 交换两个位置的元素
swap(State, R1, C1, R2, C2, NewState) :-
    nth0(R1, State, Row1),
    nth0(R2, State, Row2),
    swap_col(Row1, C1, Row2, C2, NewRow1, NewRow2),
    replace(State, R1, NewRow1, TempState),
    replace(TempState, R2, NewRow2, NewState).

swap_col(Row1, C1, Row2, C2, NewRow1, NewRow2) :-
    nth0(C1, Row1, Val1),
    nth0(C2, Row2, Val2),
    replace(Row1, C1, Val2, NewRow1),
    replace(Row2, C2, Val1, NewRow2).

replace(List, Index, NewElem, NewList) :-
    nth0(Index, List, _, Rest),
    nth0(Index, NewList, NewElem, Rest).

% 上下左右移动空格的合法规则
move(State, NextState) :-
    find_zero(State, R, C), R > 0, R1 is R-1, swap(State, R, C, R1, C, NextState).
move(State, NextState) :-
    find_zero(State, R, C), R < 2, R1 is R+1, swap(State, R, C, R1, C, NextState).
move(State, NextState) :-
    find_zero(State, R, C), C > 0, C1 is C-1, swap(State, R, C, R, C1, NextState).
move(State, NextState) :-
    find_zero(State, R, C), C < 2, C1 is C+1, swap(State, R, C, R, C1, NextState).

4. A*搜索核心实现 #

% A*入口：初始状态 -> 解路径
astar(InitialState, Path) :-
    heuristic(InitialState, H),
    F is 0 + H, % 初始f值：g=0 + h
    astar_search([(F, 0, InitialState, [])], [], Path).

% 开放列表为空，无解
astar_search([], _, _) :- !, fail.

% 找到目标状态，反转路径得到正序结果
astar_search([(_, _, State, Path)|_], _, FinalPath) :-
    goal_state(State),
    reverse([State|Path], FinalPath).

% 扩展当前节点，更新开放列表
astar_search([(F, G, State, Path)|OpenRest], Closed, FinalPath) :-
    findall(NextState, move(State, NextState), NextStates),
    process_children(NextStates, G, Path, OpenRest, Closed, NewOpen),
    sort(1, @=<, NewOpen, SortedOpen), % 按f值升序排序开放列表
    astar_search(SortedOpen, [State|Closed], FinalPath).

% 处理子节点：计算代价、去重、更新开放列表
process_children([], _, _, Open, Closed, Open).
process_children([NextState|Rest], G, Path, Open, Closed, NewOpen) :-
    (member(NextState, Closed) ->
        process_children(Rest, G, Path, Open, Closed, NewOpen)
    ;
        G1 is G + 1, % 子节点路径代价=父节点+1
        heuristic(NextState, H1),
        F1 is G1 + H1,
        (member((OldF, OldG, NextState, _), Open) ->
            (G1 < OldG ->
                delete(Open, (OldF, OldG, NextState, _), TempOpen),
                append(TempOpen, [(F1, G1, NextState, [State|Path])], TempNewOpen)
            ;
                TempNewOpen = Open
            )
        ;
            append(Open, [(F1, G1, NextState, [State|Path])], TempNewOpen)
        ),
        process_children(Rest, G, Path, TempNewOpen, Closed, NewOpen)
    ).

关键细节说明 #

1. 路径代价计算：g(n)直接用路径步数表示，初始状态g=0，每扩展一步g+1，无需额外复杂计算。
2. 开放列表排序：使用Prolog内置的sort/3函数，按节点的第一个元素（f值）升序排列，替代findall排序的低效方式。
3. 状态去重：关闭列表存储已扩展的状态，开放列表中若存在相同状态，仅保留路径代价更小的节点，避免重复搜索。
4. 路径存储：节点中的Path是从当前状态回溯到初始状态的列表，最终通过reverse/2转换为从初始到目标的正序路径。

测试示例 #

% 测试你给出的初始状态
?- astar([[2,8,3],[1,6,4],[7,0,5]], Path).

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