Scribd
Upload
3 views12 pages

Search Part

The document discusses problem-solving agents and various search strategies in artificial intelligence, highlighting the differences between uninformed and informed search strategies. It explains the concept of best-first search and A* search, detailing the importance of heuristic functions for optimizing search efficiency. Additionally, it provides examples of heuristic functions used in problems like the 8-puzzle and the conditions for optimality in search algorithms.

Uploaded by

Sugandima Vidanagamachchi
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views12 pages

Search Part

The document discusses problem-solving agents and various search strategies in artificial intelligence, highlighting the differences between uninformed and informed search strategies. It explains the concept of best-first search and A* search, detailing the importance of heuristic functions for optimizing search efficiency. Additionally, it provides examples of heuristic functions used in problems like the 8-puzzle and the conditions for optimality in search algorithms.

Uploaded by

Sugandima Vidanagamachchi
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Artificial Intelligence

Solving Problems by Searching

Content:
• Problem-solving agents
• Example problems
• Searching for solutions
• Uninformed search strategies
Informed Search Strategies
• It uses problem-specific knowledge beyond the definition of
the problem itself.
• It can find solutions more efficiently than can an uninformed
strategy.

• Best-first search is an example for informed search strategy.


– In best-first search, a node is selected for expansion based on an
evaluation function, f(n).
– The evaluation function is constructed as a cost estimate.
– So the node with the lowest evaluation is expanded first.

• Exactly UCS with f(n) replacing g(n)


Informed Search Strategies
• The choice of f determines the search strategy.
• These algorithms are used Heuristic function, h(n) as an
evaluation function.

h(n) = estimated cost of the cheapest path from the state at node n to a
goal state

• Heuristic functions are the most common form in which


additional knowledge of the problem is imparted to the search
algorithm.
• If n is a goal node, then h(n) = 0
Route finding problem in Romania
Route finding problem in Romania
Properties of Greedy best-first search
A* search
• Conditions for optimality:
– Admissibility
– Consistency

• Admissible heuristic
– An admissible heuristic is one that never overestimates the
cost to reach the goal
– They think the cost of solving the problem is less than it
actually is.
– Theorem: If h(n) is admissible, A* using Tree Search is
optimal
A* search
• Consistency
– This is a form of the general triangle inequality
– Theorem: if h(n) is consistent, A* using Graph-Search is optimal
Heuristic Functions
• A good heuristic function can reduce the search
process.
• For 8-puzzle problem

– h1 = the number of misplaced tiles


– h2 = the sum of the distances of the tiles from their goal
positions. This is called the city block distance or
Manhattan distance
Heuristic Functions
• For 8-puzzle problem

– h1 = 8
– h2 = 3+1+2+2+2+3+3+2 = 18
Defining Heuristics: h(n)
• Cost of an exact solution to a relaxed problem
(fewer restrictions on operator)
• Constraints on Full Problem:
– A tile can move from square A to square B if A is
adjacent to B and B is blank.
– Constraints on relaxed problems:
• A tile can move from square A to square B if A is adjacent to B.
(h2)
• A tile can move from square A to square B if B is blank.
• A tile can move from square A to square B. (h1)

You might also like