Page 26 - DCAP506_ARTIFICIAL_INTELLIGENCE

Artificial Intelligence

Notes comprehensively looks for the whole graph or sequence without considering the goal until it
locates it. It does not make use of a heuristic algorithm.
From the position of the algorithm, all child nodes attained by increasing a node are added to a
FIFO (i.e., First In, First Out) queue. In usual implementations, nodes that have not yet been
scrutinized for their neighbors are positioned in some container (like a queue or linked list)
known as “open” and then once inspected are positioned in the container “closed”.

Example: An Example Map of Germany with some Associations among Cities.

Algorithm (Informal)

1. Enqueue the root node.
2. Dequeue a node and examine it.

(i) If the element wanted is found in this node, suspend the search and return a result.
(ii) or else enqueue any successors (the direct child nodes) that have not yet been exposed.
3. If the queue is empty, every node on the graph has been scrutinized – quit the search and
return “not found”.
4. Repeat from Step 2.

!

Caution Using a stack rather than a queue would turn this algorithm into a depth-first
search.

2.3.2 Features

Space Complexity
As all of the nodes of a level must be accumulated until their child nodes in the next level have
been produced, the space complexity is comparative to the number of nodes at the deepest level.

20 LOVELY PROFESSIONAL UNIVERSITY