06-02-2024

Artificial Intelligence
(BITE308L)

Informed
Search Algorithms

Dr. S. Hemalatha
School of Computer Science Engineering & Information Systems
VIT, Vellore

INFORMED SEARCH ALGORITHMS

• Uninformed search algorithms:
– Looking through search space for all possible solutions of the problem
– Do not have any additional knowledge about search space
• Informed search algorithms:
– Contain an array of knowledge
• How far we are from the goal
• Path cost
• How to reach to goal node, etc.
– The knowledge help agents to
• Explore less to the search space and
• Find more efficiently the goal node

Dr. Hemalatha S, SCORE, VIT

1
 06-02-2024

INFORMED SEARCH ALGORITHMS

• Informed search algorithm uses the idea of heuristic
– Also, called heuristic search
– More useful for large search space

• The heuristic method,

– However, might not always give the best solution
– But, guaranteed to find a good solution in reasonable time

Dr. Hemalatha S, SCORE, VIT

INFORMED SEARCH ALGORITHMS

BEST-FIRST SEARCH
• General approach considered
• An instance of the general TREE-SEARCH /GRAPH-SEARCH algorithm
– a node is selected for expansion based on an evaluation function, 𝒇(𝒏)
EVALUATION FUNCTION
• Interpreted as a cost estimate
– So, the node with the lowest evaluation is expanded first
• The choice of 𝑓 determines the search strategy
• The implementation of best-first graph search is identical to that for uniform-
cost search
– Except for the use of 𝑓 instead of 𝑔 to order the priority queue

Dr. Hemalatha S, SCORE, VIT

2
 06-02-2024

Heuristic function
• Used in informed search
– Additional knowledge of the problem imparted to search algorithm
• Takes the current state of the agent as its input
– Produces the estimation of how close agent is from the goal
– Estimates how close a state is to the goal
• Represented by 𝒉(𝒏)
– Calculates the cost of an optimal path between a pair of states
• Admissibility of the heuristic function:
– ℎ(𝑛) ≤ ℎ∗ (𝑛) [ℎ 𝑛 - heuristic cost & ℎ∗ 𝑛 - estimated cost]
• ℎ(𝑛): arbitrary, nonnegative, problem-specific functions, with one constraint:
– If 𝑛 is a goal node, then ℎ(𝑛) = 0

Dr. Hemalatha S, SCORE, VIT

Pure Heuristic search

• Pure heuristic search: the simplest form of heuristic search algorithms
– Nodes expanded based on their heuristic value ℎ(𝑛)
– Two lists maintained: OPEN and CLOSED list
– CLOSED list: The search places those nodes which have been already expanded &
– OPEN list: The search places nodes which have yet not been expanded
• On each iteration,
– each node 𝑛 with the lowest heuristic value is expanded and
– generates all its successors and
– 𝑛 is placed to the closed list
• The algorithm continues unit a goal state is found

Dr. Hemalatha S, SCORE, VIT

3
 06-02-2024

informed Search Algorithms

• Greedy best-first Search

• A* Search

Dr. Hemalatha S, SCORE, VIT

Greedy best-first Search

GREEDY BEST-FIRST SEARCH ALGORITHM
• always selects the path which appears best at that moment
• It is the combination of depth-first search and breadth-first search algorithms
– Best-first search allows us to take the advantages of both algorithms
– At each step, the most promising node can be chosen
• It uses the heuristic function and search
• In the best first search algorithm,
– we expand the node which is closest to the goal node
– the closest cost is estimated by heuristic function,
𝒇 𝒏 = 𝒉(𝒏)
ℎ(𝑛)= estimated cost from node n to the goal

Dr. Hemalatha S, SCORE, VIT

4
 06-02-2024

Greedy best-first Search algorithm

• Step 1: Place the starting node into the OPEN list
• Step 2: If the OPEN list is empty, Stop and return failure
• Step 3: Remove the node 𝑛, from the OPEN list which has the lowest value of
ℎ(𝑛), and place it in the CLOSED list
• Step 4: Expand the node 𝑛, and generate the successors of node 𝑛
• Step 5: Check each successor of node n, and find whether any node is a goal node
or not
– If any successor node is goal node, then return success and terminate the search, else
proceed to Step 6
• Step 6: For each successor node
– Check for evaluation function 𝑓 𝑛
– Check if the node has been in either OPEN or CLOSED list
– If the node has not been in both list, then add it to the OPEN list
• Step 7: Return to Step 2

Dr. Hemalatha S, SCORE, VIT

Greedy best-first Search

example

Dr. Hemalatha S, SCORE, VIT

5
 06-02-2024

Greedy best-first Search

advantages & disadvantages
ADVANTAGES:
• Best first search can switch between BFS and DFS by gaining the
advantages of both the algorithms.
• This algorithm is more efficient than BFS and DFS algorithms.

DISADVANTAGES:
• It can behave as an unguided depth-first search in the worst case
scenario.
• It can get stuck in a loop as DFS.
• This algorithm is not optimal.
Dr. Hemalatha S, SCORE, VIT

Greedy best-first Search

key-points
Time Complexity:
• The worst case time complexity of Greedy best first search is 𝑂 𝑏
Space Complexity:
• The worst case space complexity of Greedy best first search is 𝑂 𝑏

𝑚 is the maximum depth of the search space

Complete:
• Greedy best-first search is also incomplete, even if the given state space
is finite
Optimal:
• Greedy best first search algorithm is NOT optimal
Dr. Hemalatha S, SCORE, VIT

6
 06-02-2024

A* search algorithm
• Most commonly known form of best-first search
• Uses
– Heuristic function ℎ(𝑛), and
– Cost
• To reach the node 𝑛 from the start state 𝑔(𝑛)
• Combined features of UCS and greedy best-first search,
– By which it solve the problem efficiently
• Finds the shortest path through the search space using the heuristic function
• Expands less search tree and provides optimal result faster
• Similar to UCS except that it uses 𝑔 𝑛 + ℎ 𝑛 instead of 𝑔 𝑛

Dr. Hemalatha S, SCORE, VIT

A* Search Algorithm

• search heuristic as well as cost to reach the node used

– Both costs combined as follows:

• The sum is called as fitness number

Dr. Hemalatha S, SCORE, VIT

7
 06-02-2024

A* Search Algorithm
• Step1: Place the starting node in the OPEN list
• Step 2: Check if the OPEN list is empty or not, if the list is empty then return failure
and stops.
• Step 3: Select the node from the OPEN list which has the smallest value of evaluation
function 𝑔 + ℎ
– If node 𝑛 is goal node then return success
– Stop, otherwise
• Step 4: Expand node 𝑛 and generate all of its successors, and put 𝑛 into the closed list
– For each successor 𝑛 , check whether 𝑛 is already in the OPEN or CLOSED list
– If NOT, then compute evaluation function for 𝑛 and place into Open list
• Step 5: Else if node 𝑛 is already in OPEN and CLOSED, then it should be attached to
the back pointer which reflects the lowest 𝑔 𝑛 value
• Step 6: Return to Step 2
Dr. Hemalatha S, SCORE, VIT

A* Search Algorithm
example

Dr. Hemalatha S, SCORE, VIT

8
 06-02-2024

A* Search Algorithm
example

Dr. Hemalatha S, SCORE, VIT

A* Search Algorithm
advantages & disadvantages
Advantages:
• The best algorithm among other search algorithms
• Optimal and complete
• Can solve very complex problems

Disadvantages:
• It does not always produce the shortest path
– as it is mostly based on heuristics and approximation
• A* search algorithm has some complexity issues
• The main drawback of A* is memory requirement as it keeps all generated nodes in the
memory, so it is not practical for various large-scale problems

Dr. Hemalatha S, SCORE, VIT

9
 06-02-2024

A* Search Algorithm
key-points
Points to remember:
• A* algorithm returns the path which occurred first, and it does not search for all remaining paths
• The efficiency of A* algorithm depends on the quality of heuristic
• A* algorithm expands all nodes which satisfy the condition f(n)

Complete: A* algorithm is complete as long as:

• Branching factor is finite.
• Cost at every action is fixed.

Dr. Hemalatha S, SCORE, VIT

A* Search Algorithm
key-points
• Optimal:
– If it follows two conditions:
1. Admissible: the first condition requires for optimality is that h(n) should be an
admissible heuristic for A* tree search. An admissible heuristic is optimistic in nature
2. Consistency: Second required condition is consistency for only A* graph-search.
• If the heuristic function is admissible, then A* tree search will always find the least cost
path.
• Time Complexity: The time complexity of A* search algorithm depends on heuristic
function, and the number of nodes expanded is exponential to the depth of solution d. So
the time complexity is O(b^d), where b is the branching factor.
• Space Complexity: The space complexity of A* search algorithm is 𝑶 𝒃𝒅

Dr. Hemalatha S, SCORE, VIT

10