Scribd
Upload
57 views

Algorithms For AI - Merged

The document discusses algorithms for artificial intelligence and different search techniques. It describes uninformed search which has no additional information about distances to the goal state. Informed search uses a heuristic function to estimate distances and is more efficient. Key differences are that informed search uses knowledge, has higher efficiency and performance, and lower costs compared to uninformed search. Examples provided are the 8 queens problem and 8-puzzle problem formulated with and without heuristic functions.

Uploaded by

Venneti Sri sai vedanth
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
57 views

Algorithms For AI - Merged

The document discusses algorithms for artificial intelligence and different search techniques. It describes uninformed search which has no additional information about distances to the goal state. Informed search uses a heuristic function to estimate distances and is more efficient. Key differences are that informed search uses knowledge, has higher efficiency and performance, and lower costs compared to uninformed search. Examples provided are the 8 queens problem and 8-puzzle problem formulated with and without heuristic functions.

Uploaded by

Venneti Sri sai vedanth
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
You are on page 1/ 21

Algorithms for AI

 Artificial Intelligence is the science of getting machines to think and make


decisions like human beings do.
 An AI algorithm is an extended subset of machine learning that tells the
computer how to learn to operate on its own.
 In turn, the device continues to gain knowledge to improve processes and
run tasks more efficiently.

Uninformed Search (Blind Search):


 An uninformed search is a searching technique that has no additional
information about the distance from the current state to the goal.
 The plans to reach the goal state from the start state differ only by the
order and length of actions.

Informed Search (Heuristic Search):


 Informed Search is another technique that has additional information
about the estimate distance from the current state to the goal.
 Informed Search algorithms have information on the goal state which
helps in more efficient searching.
 This information is obtained by a function that estimates how close a
state is to the goal state.
Difference between informed and uninformed search:

Basis of Informed search Uninformed search


comparison

Basic Uses knowledge to find No use of knowledge


knowledge the steps to the solution.

Efficiency Highly efficient as Efficiency is mediatory


consumes less time and
cost.

Cost Low Comparatively high

Performance Finds the solution more Speed is slower than the


quickly. informed search.

Algorithms Heuristic depth-first and Depth-first search, breadth-


breadth-first search, and first search, and lowest cost
A* search first search
8 Queens Problem formulation using Heuristic function
Tiling problem (8-puzzle)
Heuristic Functions:

That is, Heuristic value of start state = 8


That is, Heuristic value of start state = 18

Heuristic Function Constraint:


8- Puzzle Problem formulation using Heuristic function
8-puzzle problem without heuristics: Uninformed Search Technique

In the above tree structure, we have shown the traversing of the tree using BFS
algorithm from the root node S (start state) to goal node K (goal state). BFS search
algorithm traverse in levels, 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

In BFS, we explore each and every state until we get goal state.
Solution:
Time complexity = O(bd) = 320 = exponential time
Depth = 20 in worst case and here we obtained goal state in depth = 3.
8-puzzle problem with heuristics: Informed Search Technique

Heuristic function – number of misplaced tiles


Heuristic value of start state S = 3
That is, h = 3
Compute heuristic value of each explored states.

State with minimum heuristic value is considered to be the best state to explore
further (Best first heuristic search). So, we explore state with h = 2.
Now, we stop exploring as we reached the goal state.

We do not explore each node like in uninformed search. We explore node based
on heuristic value. Heuristics helps to get quick solution.

In heuristic best first search,


Path Cost f(n) based on Depth g(n) is
f(n) = g(n) = 3

Scroll down for another example

You might also like