Prolog path谓词优化：获取全路径及提升易用性技术问询

Hey there! Let’s tackle your Prolog path predicate questions one by one—these are super common hurdles when getting comfortable with logic programming, so you’re not alone here.

First, I’ll assume your current path predicate is probably optimized to find a single shortest (or "optimal") path. To return all paths—ordered by length (shortest first, so your optimal path comes first)—we can adjust it using either depth-first search (DFS) for all paths, or breadth-first search (BFS) to prioritize shorter paths first.

Example Setup (Edge Definitions) #

Let’s start with a sample graph to test with:

% Basic edge definitions for UK cities
edge(london, birmingham).
edge(birmingham, manchester).
edge(london, leeds).
edge(leeds, manchester).
edge(birmingham, leeds).

Option 1: DFS for All Paths (Unordered) #

This version returns every possible path (without cycles) in DFS order. We’ll use an accumulator to track visited nodes to avoid infinite loops:

% Public predicate: path_all(Start, End, Path) returns one path at a time
path_all(Start, End, Path) :-
    path_helper(Start, End, [Start], Path).

% Helper with accumulator to track visited nodes
path_helper(End, End, Visited, Path) :-
    reverse(Visited, Path). % Reverse to get start-to-end order
path_helper(Current, End, Visited, Path) :-
    edge(Current, Next),
    \+ member(Next, Visited), % Prevent revisiting nodes (no cycles)
    path_helper(Next, End, [Next|Visited], Path).

When you query path_all(london, manchester, P), Prolog will backtrack to return every valid path one by one.

Option 2: BFS for Paths Ordered by Length (Optimal First) #

If you want the shortest (optimal) path first, followed by longer paths, use BFS. This explores all nodes at the current depth before moving to the next:

% Public predicate: path_ordered(Start, End, Path) returns shortest paths first
path_ordered(Start, End, Path) :-
    bfs_queue([[Start]], End, Path).

% Initialize queue with the starting node as a single-node path
bfs_queue([Path|_], End, Path) :-
    last(Path, End). % Found a path when last node is the end
bfs_queue([CurrentPath|RestQueue], End, ResultPath) :-
    last(CurrentPath, CurrentNode),
    % Generate all new paths by extending current path to unvisited nodes
    findall([Next|CurrentPath], 
            (edge(CurrentNode, Next), \+ member(Next, CurrentPath)), 
            NewPaths),
    append(RestQueue, NewPaths, NewQueue), % Add new paths to end of queue
    bfs_queue(NewQueue, End, ResultPath).

Querying path_ordered(london, manchester, P) will first return the shortest path(s), then longer ones in order.

To make path(Start, End) work (no extra parameters), we can create a wrapper predicate that either prints all paths or returns them one by one via backtracking. Here are two approaches:

Approach 1: Print All Paths Automatically #

This version will print every valid path when you call path(Start, End), then notify you when there are no more:

% Simplified predicate: path(Start, End) prints all paths
path(Start, End) :-
    path_ordered(Start, End, Path), % Use our ordered path predicate
    write('Path: '), write(Path), nl,
    fail. % Force backtracking to find next path
path(Start, End) :-
    write('No more paths from '), write(Start), write(' to '), write(End), nl.

Now you can call path(london, manchester) directly, and it’ll output all paths starting with the shortest.

Approach 2: Return Paths via Backtracking (Interactive) #

If you want to interactively retrieve paths (e.g., in a Prolog REPL), you can skip the fail and just let backtracking do the work:

% Simplified predicate that returns paths one by one
path(Start, End) :-
    path_ordered(Start, End, Path),
    write('Found path: '), write(Path), nl.

Each time you press ; in the REPL, it’ll return the next path.

Bonus: Collect All Paths into a List #

If you want all paths in a single list, use bagof to gather them:

path(Start, End, AllPaths) :-
    bagof(Path, path_ordered(Start, End, Path), AllPaths).

% Shorthand to print the list
path(Start, End) :-
    path(Start, End, AllPaths),
    write('All paths: '), write(AllPaths), nl.

A quick note: Always include the \+ member(Next, Visited) check to avoid infinite loops if your graph has cycles (e.g., edge(a,b), edge(b,a)).

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