TCS 364

FUNDAMENTAL OF ARTIFICIAL INTELLIGENCE AND MACHINE LEARNING

1
Topics Covered
➢ Searching
➢ Search Algorithms

2
 Searching

➢Search algorithms are one of the most important areas of Artificial Intelligence.

➢Search is the fundamental technique of AI. Possible answers, decisions or courses of

action are structured into an abstract space, which we then search. Please check below
searching algorithms.

3
Searching

4
 Search Algorithm Terminologies
➢Search: Searching is a step by step procedure to solve a search-problem in a given search space. A search
problem can have three main factors:

➢Search Space: Search space represents a set of possible solutions, which a system may have.

➢Start State: It is a state from where agent begins the search.

➢Goal test: It is a function which observe the current state and returns whether the goal state is achieved or not.

➢Search tree: A tree representation of search problem is called Search tree. The root of the search tree is the
root node which is corresponding to the initial state.

5
 Search Algorithm Terminologies
➢Actions: It gives the description of all the available actions to the agent.

➢Transition model: A description of what each action do, can be represented as a transition model.

➢Path Cost: It is a function which assigns a numeric cost to each path.

➢Solution: It is an action sequence which leads from the start node to the goal node.

➢Optimal Solution: If a solution has the lowest cost among all solutions.

6
 Uniformed Search Algorithms
Uninformed search is a class of general-purpose search algorithms which operates in brute force-way. Uninformed
search algorithms do not have additional information about state or search space other than how to traverse the tree, so
it is also called blind search.

Following are the various types of uninformed search algorithms:

➢Breadth-first Search

➢Depth-first Search

➢Depth-limited Search

➢Iterative deepening depth-first search

7
 Breadth-first Search
➢Breadth-first search is the most common search strategy for traversing a tree or graph. This algorithm searches

breadthwise in a tree or graph, so it is called breadth-first search.

➢BFS algorithm starts searching from the root node of the tree and expands all successor node at the current level

before moving to nodes of next level.

➢The breadth-first search algorithm is an example of a general-graph search algorithm.

➢Breadth-first search implemented using FIFO queue data structure.

8
 Breadth-first Search
Advantages:

➢BFS will provide a solution if any solution exists.

➢If there are more than one solutions for a given problem, then BFS will provide the minimal solution which
requires the least number of steps.

Disadvantages:

➢It requires lots of memory since each level of the tree must be saved into memory to expand the next level.

➢BFS needs lots of time if the solution is far away from the root node.

9
 Breadth-first Search: Example
In the below tree structure, we have shown the traversing of the tree using BFS algorithm from the root node S
to goal node K.

10
 Breadth-first Search: Example
BFS search algorithm traverse in layers, so it will follow the path which is shown by the dotted arrow, and the
traversed path will be:

S---> A--->B---->C--->D---->G--->H--->E---->F---->I---->K

11
 Depth-first Search
➢Depth-first search is a recursive algorithm for traversing a tree or graph data structure.

➢It is called the depth-first search because it starts from the root node and follows each path to its greatest depth
node before moving to the next path.

➢DFS uses a stack data structure for its implementation.

➢The process of the DFS algorithm is similar to the BFS algorithm.

12
 Depth-first Search
Advantage:

➢DFS requires very less memory as it only needs to store a stack of the nodes on the path from root node to the current
node.

➢It takes less time to reach to the goal node than BFS algorithm (if it traverses in the right path).

Disadvantage:

➢There is the possibility that many states keep re-occurring, and there is no guarantee of finding the solution.

➢DFS algorithm goes for deep down searching and sometime it may go to the infinite loop.

13
 Depth-first Search: Example
➢In the below search tree, we have shown the flow of depth-first search, and it will follow the order as: Root node--->Left
node ----> right node.

➢It will start searching from root node S, and traverse A, then B, then D and E, after traversing E, it will backtrack the tree as
E has no other successor and still goal node is not found. After backtracking it will traverse node C and then G, and here it
will terminate as it found goal node.

14