Question

Consider a situation when the goal in a Prolog program is a conjunction of several subgoals.

(a) Explain the difference between depth-first and breadth-first approaches for satisfying the entire goal.

(b) Explain, which approach Prolog uses and why.

Answer 1

A)

S.NO	BFS	DFS
1.	BFS stands for Breadth First Search.	DFS stands for Depth First Search.
	It uses Queue data structure for finding the shortest path.	It uses Stack data structure.
3.	BFS can be used to find single source shortest path in an unweighted graph.	In DFS, we may have to traverse through more edges to reach a destination vertex(goal) from a source.
3.	BFS is more suitable for searching vertices which are closer to source mode.	DFS is more suitable gor solutions away from source node.
4.	BFS considers all neighbors and therefore not suitable for decision making .	DFS explore all paths through decision. And if this decision leads to win situation, we stop.
5.	The Time complexity of BFS is O(V + E) where V stands for vertices and E stands for edges.	The Time complexity of DFS is also O(V + E) where V stands for vertices and E stands for edges.

B)

Prolog uses DFS as it is not purely declarative: because of constructs like the cut operator(The cut, in Prolog, is a goal, written as !, which always succeeds, but cannot be backtracked. It is best used to prevent unwanted backtracking, including the finding of extra solutions by Prolog and to avoid unnecessary computations. ) a procedural reading of a Prolog program is needed to understand it.

The order of clauses in a Prolog program is significant, as the execution strategy of the language depends on it.

Other logic programming languages, such as Datalog, are truly declarative but restrict the language. As a result, many practical Prolog programs are written to conform to Prolog's depth-first search order, rather than as purely declarative logic programs.