如何在Prolog迷宫求解中仅保留最短路径？

你的solve_maze/1返回多条路径，是因为它大概率用了深度优先搜索（DFS）——DFS会探索所有可能的路径，包括绕路的，所以会返回长路径，且不会优先返回最短的。要获取最短路径，最直接高效的方法是改用广度优先搜索（BFS），因为BFS按路径长度递增的顺序遍历，第一次到达终点的路径就是最短的。

方法一：用BFS实现最短路径搜索 #

BFS的核心是维护一个路径队列，每次处理队首的路径，扩展相邻的合法位置，把新路径加到队尾。这样先处理短路径，找到的第一条终点路径就是最短的。

示例代码 #

假设你已经定义了迷宫的基础谓词（start/1起点、end/1终点、wall/1墙的位置），以下是BFS实现：

% 入口谓词：获取最短路径
solve_shortest_maze(ShortestPath) :-
    start(Start),
    bfs([[Start]], ShortestPath).

% BFS终止条件：队首路径的最后一个位置是终点，返回该路径
bfs([Path|_], Path) :-
    last(Path, End),
    end(End).

% BFS递归处理：扩展当前路径的相邻节点
bfs([CurrentPath|RestQueue], ShortestPath) :-
    last(CurrentPath, CurrentPos),
    % 生成所有合法的新路径（相邻、非墙、未访问过）
    findall(
        NewPath,
        (
            adjacent(CurrentPos, NewPos),
            \+ wall(NewPos),
            \+ member(NewPos, CurrentPath),
            append(CurrentPath, [NewPos], NewPath)
        ),
        NewPaths
    ),
    % 新路径加到队列尾部，保持BFS顺序
    append(RestQueue, NewPaths, NewQueue),
    bfs(NewQueue, ShortestPath).

% 定义相邻位置：上下左右四个方向
adjacent(X/Y, X1/Y) :- X1 is X + 1.  % 右
adjacent(X/Y, X1/Y) :- X1 is X - 1.  % 左
adjacent(X/Y, X/Y1) :- Y1 is Y + 1.  % 下
adjacent(X/Y, X/Y1) :- Y1 is Y - 1.  % 上

代码说明 #

1. 初始化队列：从起点开始，队列初始值是[[Start]]（仅包含起点的路径）。
2. 终止判断：每次检查队首路径的最后一个位置是否是终点，是则直接返回这条路径（BFS保证这是最短的）。
3. 扩展路径：找到当前位置的所有相邻合法位置（非墙、未在当前路径中），生成新路径并加到队列尾部。
4. 避免循环：用member(NewPos, CurrentPath)确保不会重复访问同一位置，防止死循环。

这个实现会直接返回你示例中的第3条最短路径，且不会返回更长的路径。

方法二：收集所有路径后筛选最短（适合小迷宫） #

如果你的迷宫很小，也可以先收集所有路径，再按长度排序取最短的。但这种方法效率低，不适合大迷宫：

solve_shortest_maze(ShortestPath) :-
    findall(Path, solve_maze(Path), AllPaths),
    predsort(compare_path_length, AllPaths, [ShortestPath|_]).

% 比较两条路径的长度，短的在前
compare_path_length(Order, PathA, PathB) :-
    length(PathA, LenA),
    length(PathB, LenB),
    compare(Order, LenA, LenB).

注意事项 #

• 如果你原来的wall/2是wall(X,Y)形式，只需把代码中的wall(NewPos)改成wall(X,Y)（其中NewPos = X/Y）。
• BFS方法无需遍历所有路径，性能远优于收集所有路径再筛选的方式，优先推荐。

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