A Star Search

“A* Search in Artificial
Intelligence”
By:
Sohaib Saleem
To:
Resp. Inam-ul-Haq
By Sohaib Chaudhery,UE Okara Campus! 1

Uniform Cost Search
 Uniform Cost is a blind search algorithm that is optimal according to any specified path
length function.
 Do not have additional info about states beyond problem def.
 Total search space is looked for solution
 No info is used to determine preference of one child over other.
 Example: 1. Breadth First Search(BFS), Depth First Search(DFS), Depth Limited
Search (DLS).
A
B
C
E
D HF
G
State Space without any extra information associated with each state

Informed/Heuristic Search
 Some info about problem space(heuristic) is used to compute
preference among the children for exploration and expansion.
 Examples: 1. Best First Search, 2. Problem Decomposition, A*,
Mean end Analysis
 The assumption behind blind search is that we have no way of
telling whether a particular search direction is likely to lead us to
the goal or not
 The key idea behind informed or heuristic search algorithms is to
exploit a task specific measure of goodness to try to either reach
the goal more quickly or find a more desirable goal state.
 Heuristic: From the Greek for “find”, “discover”.By Sohaib Chaudhery,UE Okara Campus! 3

Informed/Heuristic Search(conti…)
 Heuristic function:
 It maps each state to a numerical value which depicts goodness of a node.
 H(n)=value
 Where ,
 H() is a heuristic function and ‘n’ is the current state.
 Ex: in travelling salesperson problem heuristic value associated with each
node(city) might reflect estimated distance of the current node from the goal
node.
 The heuristic we use here is called HSLD Straight line Distance heuristic.

A* Search
 A* search is a combination of lowest-cost-first and best-first searches that
considers both path cost and heuristic information in its selection of which path
to expand.
 For each path on the frontier, A* uses an estimate of the total path cost from a
start node to a goal node constrained to start along that path.
 It uses cost(p), the cost of the path found, as well as the heuristic function h(p),
the estimated path cost from the end of p to the goal.
 For any path p on the frontier, define f(p)=cost(p)+h(p). This is an estimate of
the total path cost to follow path p then go to a goal node.
 If n is the node at the end of path p, this can be depicted as follows:
actual estimate
start ------------> n --------------------> goal
cost(p) h(p)
-------------------------------------------->
f(p)

A * Search(conti…)
 It is best-known form of Best First search. It avoids expanding paths that are
already expensive, but expands most promising paths first.
 Idea: minimize the total estimated solution cost
 f(n) = g(n) + h(n),
where
 g(n) the cost (so far) to reach the node
 h(n) estimated cost to get from the node to the goal
 f(n) estimated total cost of path through n to goal. It is implemented using
priority queue by increasing f(n).
 Minimize the total path cost to reach the goal.
 A* is complete, optimal, and optimally efficient among all optimal search
algorithms.

At S we observe that the best node is A with a value of 4 so we
move to 4.

Now we move to D from S.

A* Search Example: Romania tour

Search Terminology
 Problem Space − It is the environment in which the search takes place. (A set of
states and set of operators to change those states)
 Problem Instance − It is Initial state + Goal state.
 Problem Space Graph − It represents problem state. States are shown by nodes and
operators are shown by edges.
 Depth of a problem − Length of a shortest path or shortest sequence of operators
from Initial State to goal state.
 Space Complexity − The maximum number of nodes that are stored in memory.
 Time Complexity − The maximum number of nodes that are created.
 Admissibility − A property of an algorithm to always find an optimal solution.
 Branching Factor − The average number of child nodes in the problem space graph.
 Depth − Length of the shortest path from initial state to goal state.

Admissible heuristics
 A heuristic h(n) is admissible if for every
node n, h(n) ≤ h*(n), where h*(n) is the
true cost to reach the goal state from n
 e.g., Straight-Line Distance
 an admissible heuristic never overestimates the
cost to reach the goal, i.e., it is optimistic
 THEOREM: If h(n) is admissible, A* using
Tree-Search is optimal

Optimality of A*
A* expands nodes in order of increasing f value

Evaluation: A* search
□ Complete
■ Yes
□ Optimal
■ Yes
□ Space
■ Keeps all nodes in memory
□ Time
■ Exponential

Thank-You

A Star Search

Recommended

Recommended

More Related Content

What's hot

What's hot (20)

Similar to A Star Search

Similar to A Star Search (20)

More from university of education,Lahore

More from university of education,Lahore (20)

Recently uploaded

Recently uploaded (20)

A Star Search