Given a list of facts, edge(a,b) like that, how to write a simple path search algorithm…
- User
Given a list of facts,
edge(a,b)like that, how to write a simple path search algorithm in prolog? Assistant
A classic Prolog question!
Given a list of facts like
edge(a, b), you want to write a simple path search algorithm in Prolog. I'll guide you through it.The Problem
You have a graph represented by a set of
edge/2facts, whereedge(A, B)means there's a direct connection (edge) from nodeAto nodeB. Your goal is to find a path from a starting node (Start) to a target node (End).The Solution
Here's the simple, yet powerful, Prolog code for a path search algorithm:
% path(Start, End, Path) path(Start, End, [Start, End]) :- edge(Start, End). path(Start, End, [Start | Rest]) :- edge(Start, Intermediate), path(Intermediate, End, Rest).Let's break it down:
Clause 1: Direct Edge
path(Start, End, [Start, End]) :- edge(Start, End).If there's a direct edge from
StarttoEnd, we've found a path of length 2:[Start, End]. Easy!Clause 2: Recursive Step
path(Start, End, [Start | Rest]) :- edge(Start, Intermediate), path(Intermediate, End, Rest).If there's no direct edge, we:
- Find an
Intermediatenode connected toStartviaedge(Start, Intermediate). - Recursively search for a path from
IntermediatetoEnd, yieldingRestof the path. - If we find such a path, prepend
StarttoRest, forming the complete path:[Start | Rest].
How it works
- Prolog tries Clause 1: if
edge(Start, End)is true, it returns a path of length 2. - If not, Prolog tries Clause 2:
edge(Start, Intermediate)bindsIntermediateto a node connected toStart.- The recursive call
path(Intermediate, End, Rest)searches for a path fromIntermediatetoEnd. - If a path is found (
Rest), Prolog prependsStartto it, forming the final path.
Example Usage
Suppose you have these facts:
edge(a, b). edge(b, c). edge(c, d). edge(a, e). edge(e, d).Query:
?- path(a, d, Path).Prolog will respond with:
Path = [a, b, c, d] ; Path = [a, e, d].Two paths from
atodare found!Tips & Variations
- To avoid cycles, add a
\+ member(Intermediate, Rest)check in Clause 2, ensuring we don't revisit nodes:
path(Start, End, [Start | Rest]) :- edge(Start, Intermediate), \+ member(Intermediate, Rest), path(Intermediate, End, Rest).- For undirected graphs, add
edge(B, A)for eachedge(A, B)fact, or modify the predicate toedge(A, B) :- edge(A, B) ; edge(B, A). - To find all paths, use
findall/3:findall(Path, path(a, d, Path), AllPaths). - For shortest path, you'll need more advanced techniques, like Dijkstra's algorithm or breadth-first search (BFS).
Now, go ahead and experiment with this simple yet elegant Prolog path search algorithm!
Happy Prologging!
- Find an
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.