ARTIFICIAL INTELLIGENCE

A Course under Centre of Excellence as Initiative of Department of Science and

Technology, Government of Bihar

GOVERNMENT POLYTECHNIC SAHARSA

Presenter:
Prof. Shubham
HoD(Computer Science and Engineering)
Todays Class
➢Problem Solving
➢Key Terms in Problem Solving
➢Properties of Search Algorithm
➢Types of Search Algorithms
➢Uninformed Search Algorithm
➢Informed Search Algorithms
Problem Solving
• A search problem consists of:
• A State Space. Set of all possible states where you can be.
• A Start State. The state from where the search begins.
• A Goal Test. A function that looks at the current state returns whether or not
it is the goal state.
• The Solution to a search problem is a sequence of actions, called
the plan that transforms the start state to the goal state.
• This plan is achieved through search algorithms.
Key Terms:
• 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.
• 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.
Properties of Search Algorithms:

• Completeness: A search algorithm is said to be complete if it

guarantees to return a solution if at least any solution exists for any
random input.
• Optimality: If a solution found for an algorithm is guaranteed to be
the best solution (lowest path cost) among all other solutions, then
such a solution for is said to be an optimal solution.
• Time Complexity: Time complexity is a measure of time for an
algorithm to complete its task.
• Space Complexity: It is the maximum storage space required at any
point during the search, as the complexity of the problem.
Uninformed Search Algorithms:

• The search algorithms in this section have no additional information

on the goal node other than the one provided in the problem
definition.
• The plans to reach the goal state from the start state differ only by
the order and/or length of actions.
• Uninformed search is also called Blind search.
• These algorithms can only generate the successors and differentiate
between the goal state and non goal state.
Informed Search Algorithms:

• Here, the algorithms have information on the goal state, which helps in more
efficient searching. This information is obtained by something called a heuristic.
In this section, we will discuss the following search algorithms.
1.Greedy Search
2.A* Tree Search
3.A* Graph Search

• Search Heuristics: In an informed search, a heuristic is a function that estimates

how close a state is to the goal state.
• For example – Manhattan distance, Euclidean distance, etc. (Lesser the distance,
closer the goal.) Different heuristics are used in different informed algorithms
discussed below.
Uninformed Search Strategies
• A problem graph, containing the start node S and the goal node G.
• A strategy, describing the manner in which the graph will be traversed
to get to G.
• A fringe, which is a data structure used to store all the possible states
(nodes) that you can go from the current states.
• A tree, that results while traversing to the goal node.
• A solution plan, which the sequence of nodes from S to G.
Depth First Search
• The depth-first search or DFS algorithm traverses or explores data
structures, such as trees and graphs.
• The algorithm starts at the root node (in the case of a graph, you can
use any random node as the root node) and examines each branch
as far as possible before backtracking.
• DFS uses Stack data structure.
• Start from root
• For each node if it has untraversed children
• (go to children)
• Else
• (Backtrack to parent node)
Algorithm
To implement DFS traversal, you need to take the following stages.
• Step 1: Create a stack with the total number of vertices in the graph as the size.
• Step 2: Choose any vertex as the traversal's beginning point. Push a visit to that
vertex and add it to the stack.
• Step 3 - Push any non-visited adjacent vertices of a vertex at the top of the stack
to the top of the stack.
• Step 4 - Repeat steps 3 and 4 until there are no more vertices to visit from the
vertex at the top of the stack.
• Step 5 - If there are no new vertices to visit, go back and pop one from the stack
using backtracking.
• Step 6 - Continue using steps 3, 4, and 5 until the stack is empty.
• Step 7 - When the stack is entirely unoccupied, create the final spanning tree by
deleting the graph's unused edges.
Example
Application Of Depth-First Search Algorithm

The minor spanning tree is produced by the DFS traversal of an unweighted graph.
1.Detecting a graph's cycle: A graph has a cycle if and only if a back edge is visible
during DFS. As a result, you may run DFS on the graph to look for rear edges.
2.Topological Sorting: Topological Sorting is mainly used to schedule jobs based
on the dependencies between them. In computer science, sorting arises in
instruction scheduling, ordering formula cell evaluation when recomputing
formula values in spreadsheets, logic synthesis, determining the order of
compilation tasks to perform in makefiles, data serialization, and resolving
symbols dependencies linkers.
3.To determine if a graph is bipartite: You can use either BFS or DFS to color a new
vertex opposite its parents when you first discover it. And check that each other
edge does not connect two vertices of the same color. A connected component's
first vertex can be either red or black.
4.Finding Strongly Connected Components in a Graph: A directed graph is strongly
connected if each vertex in the graph has a path to every other vertex.
Breadth First Search
• Breadth-first search is a graph traversal algorithm that starts
traversing the graph from the root node and explores all the
neighboring nodes.
• Then, it selects the nearest node and explores all the unexplored
nodes. While using BFS for traversal, any node in the graph can be
considered as the root node.
• BFS uses Queue Data Structure.
Algorithm
• Step 1: SET STATUS = 1 (ready state) for each node in G
• Step 2: Enqueue the starting node A and set its STATUS = 2 (waiting state)
• Step 3: Repeat Steps 4 and 5 until QUEUE is empty
• Step 4: Dequeue a node N. Process it and set its STATUS = 3 (processed
state).
• Step 5: Enqueue all the neighbours of N that are in the ready state (whose
STATUS = 1) and set
• their STATUS = 2
• (waiting state)
• [END OF LOOP]
• Step 6: EXIT
Applications of BFS algorithm

• The applications of breadth-first-algorithm are given as follows -

• BFS can be used to find the neighboring locations from a given source
location.
• In a peer-to-peer network, BFS algorithm can be used as a traversal
method to find all the neighboring nodes. Most torrent clients, such as
BitTorrent, uTorrent, etc. employ this process to find "seeds" and "peers" in
the network.
• BFS can be used in web crawlers to create web page indexes. It is one of
the main algorithms that can be used to index web pages. It starts
traversing from the source page and follows the links associated with the
page. Here, every web page is considered as a node in the graph.
• BFS is used to determine the shortest path and minimum spanning tree.
Uniform-Cost Search (Dijkstra for large Graphs)

• Uniform-Cost Search is a variant of Dijikstra’s algorithm

• The uniform-cost search is then implemented using a Priority Queue.
• instead of inserting all vertices into a priority queue, we insert only
source, then one by one insert when needed.
• In every step, we check if the item is already in priority queue (using
visited array). If yes, we perform decrease key, else we insert it.
• This variant of Dijkstra is useful for infinite graphs and those graph
which are too large to represent in the memory. Uniform-Cost Search
is mainly used in Artificial Intelligence.
Algorithm for uniform cost search:

• Insert the root node into the priority queue

• Remove the element with the highest priority.
If the removed node is the destination, print total cost and stop the
algorithm
Else if, Check if the node is in the visited list
• Else Enqueue all the children of the current node to the priority
queue, with their cumulative cost from the root as priority and the
current not to the visited list.
• Advantages:
• Uniform cost search is optimal because at every state the path with
the least cost is chosen.
• Disadvantages:
• It does not care about the number of steps involve in searching and
only concerned about path cost. Due to which this algorithm may be
stuck in an infinite loop.