Scribd
Upload
4 views2 pages

AI Search Algorithm

The document provides Prolog code implementations for Depth-First Search (DFS) and Breadth-First Search (BFS) algorithms on a defined graph. It includes the graph structure with edges and the respective helper functions for both search algorithms. Additionally, it shows example queries to execute the DFS and BFS functions to find paths from node 'a' to node 'f'.

Uploaded by

suhanikumari.tech
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views2 pages

AI Search Algorithm

The document provides Prolog code implementations for Depth-First Search (DFS) and Breadth-First Search (BFS) algorithms on a defined graph. It includes the graph structure with edges and the respective helper functions for both search algorithms. Additionally, it shows example queries to execute the DFS and BFS functions to find paths from node 'a' to node 'f'.

Uploaded by

suhanikumari.tech
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

AI Search Algorithm

BFS & DFS Implementation:


Prolog Code for DFS:

% ---------- Graph Definition ----------


edge(a, b).
edge(a, c).
edge(b, d).
edge(c, e).
edge(e, f).

% ---------- DFS Implementation ----------


dfs(Start, Goal, Path) :-
dfs_helper(Start, Goal, [Start], Path).

dfs_helper(Goal, Goal, Visited, Path) :-


reverse(Visited, Path).
dfs_helper(Current, Goal, Visited, Path) :-
edge(Current, Next),
\+ member(Next, Visited),
dfs_helper(Next, Goal, [Next|Visited], Path).

Prolog Code for BFS:

% ---------- Graph Definition ----------


edge(a, b).
edge(a, c).
edge(b, d).
edge(c, e).
edge(e, f).

% ---------- BFS Implementation ----------


bfs(Start, Goal, Path) :-
bfs_helper([[Start]], Goal, RevPath),
reverse(RevPath, Path).

bfs_helper([[Goal|Rest]|_], Goal, [Goal|Rest]).


bfs_helper([[Current|Rest]|Others], Goal, Path) :-
findall([Next,Current|Rest],
(edge(Current, Next), \+ member(Next, [Current|Rest])),
NewPaths),
append(Others, NewPaths, UpdatedQueue),
bfs_helper(UpdatedQueue, Goal, Path).
Queries Execution:

% ?- dfs(a, f, Path).
% ?- bfs(a, f, Path).

You might also like