Depth Limited Search

• Depth-limited search avoids the pitfalls of depth-first search which is

infinite path by imposing a cutoff on the maximum depth of a path.
• Depth-first search with depth limit l. Algorithm treats the node at
the depth limit l as it has no successor nodes further.
• In this algorithm, Depth-limited search can be terminated with two
Conditions of failure:
– Standard failure value: It indicates that problem does not have any
solution.
– Cutoff failure value: It defines no solution for the problem within a given
depth limit.
Advantages:
• Depth-limited search is Memory efficient.
Disadvantages:
• Depth-limited search also has a disadvantage of incompleteness.
• It may not be optimal if the problem has more than one solution.
DEPTH LIMITED SEARCH
 PROPERTIES OF DLS

• Complete?

• Yes (unless the goal node is within the depth l )

• Time?

• O(bl ) Exponential
• Space?

• O(bl) Keeps all nodes in memory

• Optimal?

• No (depending upon search algo and heuristic property)

 ITERATIVE DEEPENING SEARCH
• The hard part about depth-limited search is picking a good limit, which
is known as diameter of the state space. for most problems, we will not
know a good depth limit until we have solved the problem.
• Iterative deepening search is a strategy that sidesteps the issue of
choosing the best depth limit by trying all possible depth limits: first
depth 0, then depth 1, then depth 2, and so on.
• The iterative deepening algorithm is a combination of DFS and BFS
algorithms. This search algorithm finds out the best depth limit and
does it by iteratively increasing the depth limit until a goal is found.
• This algorithm performs depth-first search up to a certain "depth limit",
and it keeps increasing the depth limit after each iteration until the
goal node is found.
• To avoid the infinite depth problem of DFS, we can decide to only
search until depth L, i.e. we don’t expand beyond depth L.
 Iterative deepening search Algorithm

• Explore the nodes in DFS order.

• Set a LIMIT variable with a limit value.
• Loop each node up to the limit value and
further increase the limit value accordingly.
• Terminate the search when the goal state is
found.
ITERATIVE DEEPENING SEARCH
ITERATIVE DEEPENING SEARCH
ITERATIVE DEEPENING SEARCH

1'st Iteration-----> A
2'nd Iteration----> A, B, C
3'rd Iteration------>A, B, D, E, C,
F, G
In the third iteration, the
algorithm will find the goal node.
 Properties of Iterative deepening
Search
• Complete?? Yes
• Time?? (d + 1) b 0 + db 1 + ( d − 1) b 2 + . . . + b d = O(b d )
• Space?? O(bd)
• Optimal?? Yes, if step cost = 1 it can be modified to explore a
uniform-cost tree. Otherwise, not optimal but guarantees
finding solution of shortest length (like BFS).
• Disadvantages of Iterative deepening search
• The drawback of iterative deepening search is that it seems
wasteful because it generates states multiple times.
• Note: Generally, iterative deepening search is required when
the search space is large, and the depth of the solution is
unknown.
 Uniform cost search
• The primary goal of the uniform-cost search is to find a path to the goal node which
has the lowest cumulative cost ie sort by the cost-so-far.
• A uniform-cost search algorithm is implemented by the priority queue. It gives
maximum priority to the lowest cumulative cost and Enqueue nodes by path cost.
• Uniform cost search modifies the breadth-first strategy by always expanding the
lowest-cost node on the fringe. Uniform cost search is equivalent to BFS algorithm if
the path cost of all edges is the same.
• Algorithm outline: Let g(n) = cost of the path from the start node to the current
node n. Sort nodes by increasing value of g
– Always select from the OPEN the node with the least g(.) value for expansion, and
put all newly generated nodes into OPEN
– Nodes in OPEN are sorted by their g(.) values (in ascending order)
– Terminate if a node selected for expansion is a goal
• Called “Dijkstra's Algorithm” in the algorithm's literature and similar to “Branch and
Bound Algorithm” in operations research literature
UNIFORM COST SEARCH
UNIFORM COST SEARCH
 UNIFORM COST SEARCH

Expanded node Nodes list/open list

{ S0 }
1 S0 { B1 A3 C8 }
2 B1 { A3 C8 G21 }
3 A3 { D6 C8 E10 G18 G21 }
4 D6 { C8 E10 G18 G21 }
5 C8 { E10 G13 G18 G21 }
6 E10 { G13 G18 G21 }
7 G13 { G18 G21 }

• Solution path found is S C G, cost 13

• Number of nodes expanded (including goal node) =
7
 UNIFORM COST SEARCH

The good:
UCS is complete and optimal!​
The bad:
Explores options in every “direction”​. No information about goal
location​
 Bidirectional search
• Bidirectional search algorithm runs two simultaneous searches, one
form initial state called as forward-search and other from goal node
called as backward-search, to find the goal [Link] search stops
when these two graphs intersect each other.
• Bidirectional search can use search techniques such as BFS, DFS, DLS,
etc.
• Bidirectional search replaces one single search graph with two small
subgraphs in which one starts the search from an initial vertex and
other starts from goal vertex.
• Idea
– simultaneously search forward from S and backwards from G
– stop when both “meet in the middle”
– need to keep track of the intersection of 2 open sets of nodes. need a way
to specify the predecessors of G this can be difficult
When to use bidirectional approach?
• Both initial and goal states are unique and completely defined.
• The branching factor is same in both directions.
BIDIRECTIONAL SEARCH
 Properties of bidirectional search
• Complete: Yes. Bidirectional search is complete.
• Optimal: Yes. It gives an optimal solution.
• Time and space complexity: Bidirectional search
has O(bd/2)
• Disadvantage of Bidirectional Search
• It requires a lot of memory space.
 COMPARISON
Iterative Uniform
Limited Bidirectio
Criterion BFS DFS deepenin Cost
Depth nal
g Search

Time Bd Bm Bl Bd Bd/2 Bc*/

Space Bd B*m B*l Bd Bd/2 Bc*/

Optimality? Yes No No Yes Yes Yes

Completenes
Yes No Yes if ld Yes Yes if e Yes if 
s
• B – branching factor, d – solution depth,
• m – maximum depth of the tree, l –depth
limit of search (AdMax
• -smallest step cost
 INFORME
D SEARCH
S T R AT E G I
ES
 INFORMED SEARCH
• BFS, DFS, ID-DFS
– No idea where the goal is
– Explores many unnecessary nodes
• Informed search algorithms use domain knowledge to
decide which node looks most promising.
• In an informed search, problem information is available
which can guide the search. Informed search knows
where to look first
• Informed search strategies can find a solution more
efficiently than an uninformed search strategy.
 INFORMED SEARCH
• Informed search strategies can find a solution more efficiently than
an uninformed search strategy. Informed search is also called a
Heuristic search.
• A heuristic is a way which might not always be guaranteed for best
solutions but guaranteed to find a good solution in reasonable
time.
• Informed search can solve much complex problem which could not
be solved in another way.
• It contains the problem description as well as extra information like
how far is the goal node.

Example: traveling salesman problem, Greedy Search, A* Search

 INFORMED SEARCH
• Informed search uses an evaluation function
to rank nodes
• An evaluation function assigns a numerical
value to each node to estimate how good it is
for reaching the goal.
• General form:
𝑓(𝑛)=value used to decide which node to
expand next
Lower value of f(n) → higher priority
 INFORMED SEARCH
• Suppose: You are in Vidyavihar
• Goal: Colaba
• Nodes closer to Colaba are better choices.
• Evaluation function might say:
– Node A → Estimated distance 15 km away
– Node B → Estimated distance 20 km away
Expand Node A first
 General
Approach:
Best first
search
 Best First Search
• A search strategy is defined by picking the order of node expansion
• Use an evaluation function f(n) is used to assign score for each
node. f(n) provides an estimate for the total cost also known as
estimate of "desirability“. Expand the node n with smallest f(n) ie most
desirable unexpanded node.
Implementation:
– Order the nodes in fringe increasing order of cost.
– The algorithm maintains two lists, one containing a list of candidates yet to
explore (OPEN), and one containing a list of already visited nodes (CLOSED).
States in OPEN are ordered according to some heuristic estimate of their
“closeness” to a goal. This ordered OPEN list is referred to as priority
queue.
– The algorithm always chooses the best of all unvisited nodes that have
been graphed
• Choice of f determines the search strategy. The advantage of this
strategy is that if the algorithm reaches a dead-end node, it will
continue to try other nodes.`
 Best First Search
Let fringe be a priority queue containing the initial state
LOOP
if fringe is empty return failure
Node<- remove-first(fringe)
if Node is a goal
then return path from initial state to goal
node
else generate all the successors of the Node, and
put the newly generated nodes into fringe
according to their f values
END LOOP
BEST FIRST SEARCH EXAMPLE
BEst FIRST SEARCH SOLUTION
Does best first algorithm always
guarantee to find shortest path?
 HEURISTIC FUNCTIONS
• Most of Best First Strategies use eval. func. f(n) as heuristic function h(n)
• A heuristic function, h(n), is the estimated cost of the cheapest path from the state
at node n, to a goal state. A node is selected for expansion in informed search
algorithm based on an evaluation function that estimates cost to goal.
• A heuristic is:
– A function that estimates how close a state is to a goal
– Designed for a particular search problem
– The value of the heuristic function is always positive. If h(n)=0, n is goal node
• Examples: Manhattan distance, Euclidean distance for pathing
• Heuristic is a function which is used in Informed Search finds the most promising
path.
• Heuristic functions are very much dependent on the domain used. h(n) might be the
estimated number of moves needed to complete a puzzle, or the estimated straight-
line distance to some town in a route finder.
• Choosing an appropriate function greatly affects the effectiveness of the state-space
search, since it tells us which parts of the state-space to search next.
• A heuristic evaluation function which accurately represents the actual cost of getting
to a goal state, tells us very clearly which nodes in the state-space to expand next,
and leads us quickly to the goal state.
 EXAMPLe
heuristics
E.g., for the 8-puzzle:
• h1(n) = number of misplaced
tiles
• h2(n) = total Manhattan
distance(i.e., no. of squares
from desired location of each
tile)(cityblock, D4 distance)
• h1(S) = ?
• h2(S) = ?
 EXAMPle
heuristics
• E.g., for the 8-puzzle:
• h1(n) = number of misplaced
tiles
• h2(n) = total Manhattan
distance(i.e., no. of squares
from desired location of each
tile)
• h1(S) = 8
• h2(S) = 3+1+2+2+2+3+3+2 =
18
 EXAMPLE HEURISTICS
• For Graph Search problem
• Straight-line distance : The distance between
two locations on a map can be known without
knowing how they are linked by roads (i.e. the
absolute path to the goal).
 Properties of best first seaRch
• It may get stuck in an infinite branch that
doesn’t contain the goal .
• It does not guarantee to find the shortest path
solution .
Memory requirement :
• In best case : as depth first search.
• In average case : between depth and breadth.
• In worst case : as breadth first search
 Greedy Best First Search

• f(n)= h(n)
• Only considers:
– Estimated distance to goal
– Ignores path cost so far

– h(A) = 2
– h(B) = 1
• Greedy BFS:
Chooses B first (looks closer)
May miss optimal path
• Limitations
Not optimal
Not complete
Fast
Simple
• Greedy search is fast but
careless.
Greedy Best First Search
Greedy Best First Search
Greedy Best First Search
Greedy Best First Search
 A * Algorithm
Properties of a Good Heuristic Function
1. Admissible Heuristic (Admissibility)
– Never overestimates the true cost
– ℎ 𝑛 ≤ ℎ∗ 𝑛 (ℎ∗ 𝑛 is actual distance of node
n to goal node)
– Why important?
• Guarantees optimal solution (in A*)
 A * Algorithm
Properties of a Good Heuristic Function
2. Consistent (Monotonic)
• ℎ 𝑛 ≤ 𝑐 𝑛 𝑛′ + ℎ 𝑛′
• Meaning:
– Heuristic values decrease smoothly
– No sudden jumps
 A * Algorithm
• f(n)=g(n)+h(n)
– Where:
– g(n) = cost from start to node n
– h(n) = estimated cost to goal
• “What I’ve paid + what I expect to pay”
Complete
Optimal (if h is admissible)
Efficient
Widely used
 A * Algorithm

Expanded Node Open

-- S7
 A * Algorithm

Step 1: Start node S, Successors A & B

S-A => f(A) = 1+10=11
S-B => f(B)= 1+9=10

Expanded Node Open

-- S7
S7 B10 A11
 A * Algorithm
Step 2: S-B , Successors of B are A, C, G
S-B-A => f(A) = (1+9)+10=20....Discard
S-B-C => f(C)= (6+1)+5=12
S-B-G => f(G)= (1+12)+0=13
S-A path from step 1 chosen as min f(n)

Expanded Node Open

-- S7
S7 B10 A11
B10 A11 C12 G13
 A * Algorithm

Step 3: S-A , Successors is B

S-A-B => f(B) = (1+9)+9= 19 ....Discard

Expanded Node Open

-- S7
S7 B10 A11
B10 A11 C12 G13
A11 C12 G13
 A * Algorithm
Step 4: S-B-C , Successors is G
S-B-C-G => f(G) = (1+6+5)+0= 12 ......Discard G13(SBG)
SBCG optimal path from S to G
Expanded Node Open

-- S7
S7 B10 A11
B10 A11 C12 G13
A11 C12 G13
C12 G12

Expanded Node Open

-- S7
S7 B10 A11
B10 A11 C12 G13
A11 C12 G13
C12 G12
G12 (Goal) EMPTY