Knowledge - Based Systems In Artificial Intelligence

Artificial Intelligence

Introduction

Defining Breadth First Search & Depth First Search

Breadth First Search
Tree example for Breadth-First Search
Graph Traversal
Advantages of Breadth-First Search
Disadvantages of Breadth-First Search
Real Life Examples on Breadth First Search

Depth First Search
Tree example for Depth-First Search
Advantages of Depth-First Search
Disadvantages of Depth-First Search
Real Life Examples on Depth First Search

Breadth First Search & Depth First Search In Artificial Intelligence

Breadth-First Search

Breadth-first search carefully examines every node at a particular depth before going to the next level, it is guaranteed to find the solution, with the shortest path from the first state. Breadth-first search starts at the root of the tree. It starts from the root node. and explores all nodes at the same level. Which means first it examines the neighboring nodes first before examining nodes at the next level. And then after that it moves towards the next level of neighboring nodes. It generates one tree at a time until the solution is found.

Tree example for Breadth-First Search

A, B, C, D, E, F, G, H, I, J, K, L

Graph

Visiting	Queue (Memory)
A	B,C
B	C,D,E,F,G
C	D,E,F,G/N
D	E,F,G,H,I,J,K,M,N
E	F,G,H,I,J,K,M,N
F	G,H,I,J,K,M,N
G	H,I,J,K,M,N
H	I,J,K,M,N
I	J,K,M,N
J	K,M,N
K	M,N
M	N

Advantages:

Breadth first search will never get trapped exploring the useless path forever. As an advantage It can be implemented using queue data structure and this method provides shortest path to the solution.
If there is more than one solution then BFS can find the minimal one that requires less number of steps which means it will take Smallest number of moves.
It is simple to implement(If there is a solution, BFS will definitely find it out)

Disadvantages:

A disadvantage of the breadth-First Search is that it can have a high memory requirement - as a record needs to be maintained of every expanded node which means, each level of the tree must be saved in order to generate the next level, and the amount of memory is relative to the number of nodes stored, as the space complexity of BFS.
Since each level of nodes is saved for creating next one, it consumes a lot of memory space. Space requirement to store nodes is rapid.
Its complexity depends on the number of nodes. It can check duplicate nodes.
If the solution is farther away from the root, breath first search will consume lot of time.

Real Life Examples for Breadth- First Search

Peer to Peer Networks. In Peer to Peer Networks like Bit Torrent, Breadth First Search is used to find all neighbor nodes.
Social Networking Websites: In social networks, we can find people within a given distance ‘k’ from a person using Breadth First Search till ‘k’ levels.
GPS Navigation systems: Breadth First Search is used to find all neighboring locations.
Broadcasting in Network: In networks, a broadcasted packet follows Breadth First Search to reach all nodes.
Path Finding We can either use Breadth First or Depth First Traversal to find if there is a path between two vertices.

Depth First Search

Depth-first search is not guaranteed to find the solution with the shortest path. As it is possible for depth-first search to proceed down an infinitely long branch, without ever returning to explore other branches, there is no guarantee that depth-first search will ever find a solution, even when one exists. The memory requirements of depth-first search are more modest than breadth-first search. Only a single path from the root node to the current node, plus any unexpanded nodes on the path, need to be stored. It creates the same set of nodes as Breadth-First method, only in the different order.

Depth-first search starts at the root node and continues down a particular path selecting a child node at the deepest level of the tree to expand next. Only when the search comes to an end or edge ,without having any child nodes, it does the search "backtrack" - continuing the search from the last node it came across whose child nodes have not been fully examined explored or visited. It is implemented in recursion with LIFO stack data structure. It creates the same set of nodes as Breadth-First method, only in the different order. As the nodes on the single path are stored in each process from root to leaf node, the space requirement to store nodes is linear.

Tree example for Depth-First Search

A, B, D, H, I, E, J, K, C, F, L,

Advantages:

Depth First Search consumes very less memory space. If depth-first search finds solution without exploring much in a path then the time and space it takes will be very less.
It will reach at the goal node in a less time period than Breadth First Search if it traverses in a right path. The time complexity of a depth-first Search to depth since it generates the same set of nodes as breadth-first search, but simply in a different order. practically depth-first search is time-limited rather than space-limited.
If depth-first search finds solution without exploring much in a path then the time and space it takes will be very less. It may find a solution without examining much of search because we may get the desired solution in the very first time.

Disadvantages :

Space Complexity.
Its complexity depends on the number of paths. It cannot check duplicate nodes.
Some nodes can be missed.
Sometimes the states may also enter into infinite loops and go on infinitely on one path. it may go down the left-most path forever. Even a finite graph can generate an infinite tree.
Depth-First Search is not guaranteed to find the solution. And there is no guarantee to find a minimal solution, if more than one solution exists.

Real Life Examples on Depth First Search

Detecting cycle in a graph

A graph has cycle if and only if we see a back edge during DFS. So we can run DFS for the graph and check for back edges.

Path Finding

· Solving puzzles with only one solution, such as mazes. (DFS can be adapted to find all solutions to a maze by only including nodes on the current path in the visited set.)

Topological Sorting

Topological Sorting is mainly used for scheduling jobs from the given dependencies among jobs. In computer science, applications of this type arise in instruction scheduling, ordering of formula cell evaluation when re computing formula values in spreadsheets, logic synthesis, determining the order of compilation tasks to perform in make files, data serialization, and resolving symbol dependencies in linkers.

To test if a graph is bipartite

We can augment either BFS or DFS when we first discover a new vertex, color it opposite its parents, and for each other edge, check it doesn’t link two vertices of the same color. The first vertex in any connected component can be red or black.