03.3 Best-First Search/Depth-First Search Flashcards
Best-First Search
It uses a … for the frontier, which is ordered by some parametrized evaluation function f (n): always the …
→ different functions f result in …
→ … is Best-First Search with f (n) = g(n)
priority queue; node with the minimum value of f (n) is expanded first.
different algorithms
Uniform-Cost Search
Best-First Search: Changes to Breadth-First Search
Goal test is applied to a node when … rather than when it is first generated. WHY?
A test is added in case a …
Realization: subsequent operations on the …
it is selected for expansion
Reason: the first generated goal node might be on a suboptimal path.
better path to an already reached state is found.
lookup table reached.
Operations on the lookup table reached
s in reached: returns true if …
reached[s]: returns the node for state s in reached; …
reached[s] ← n: sets …
reached contains the state s.
due to the internal structure of lookup tables, this can be done in constant time^a
the value of state s to the node n.
Modify the pseudo-code below to a Best-First Search Algorithm
function Best-First-Search (problem, f ) returns a solution or failure
node ← Node(State=problem.Initial-State,Path-Cost=0)
frontier ← a priority queue ordered by f , with node as the only element
…
loop do
if Is-Empty(frontier) then return failure
node ← Pop(frontier) // chooses the node n with minimum f (n) in frontier if problem.Is-Goal(node.State) then return Solution(node)
for each child in Expand(problem,node) do
s ← child.State
if …
frontier ← Insert(child,frontier)
reached ← a lookup table, with one entry (node.State → node)
s is not in reached or child.Path-Cost < reached[s].Path-Cost then
reached[s] ← child
When executing the algorithm:
goal: xxx
node: xxx
frontier: xxx
reached: xxx
the cost C∗ of the optimal solution,
the minimum step-cost ǫ
Assess the performance metrics of Best-First search
Completeness: Yes, if costs are greater than 0 (otherwise infinite optimal paths of zero cost exist).
Optimality: Yes (if cost ≥ ǫ for positive ǫ).
Time complexity: The worst case is that the goal branches of a node with huge costs and all other step costs are ǫ. The number of explored nodes (for e.g. d = 1) sums up to
(b−1)+(b−1)b+(b−1)b2+···+(b−1)b⌊C∗/ǫ⌋ =O(b1+⌊C∗/ǫ⌋),
where ⌊a⌋ returns the next lower integer of a.
Space complexity: Equals time complexity since all nodes are stored.
Can Depth-First Search be implemented using Best-First Search? Solution: …
But: …, please see Depth-Limited Search on slide 86 with limit=∞).
Best-First Search with f (n) = −n.Depth.
usually implemented as a tree-like search (for pseudo-code
Depth-First Search: Performance
Reminder: Branching factor b, depth d, maximum length m of any path.
Completeness: …
Optimality: …
Time complexity:
Reminder: Breadth-first has O(b^d ) and d ≤ m.
Space complexity: The advantage of depth-first search is a good space complexity: explain.
No. But: for finite state spaces, completeness can be achieved by checking for cycles.
No
The worst case is that the goal path is tested last, resulting in O(b^m).
One only needs to store a single path from the root to the leaf plus unexplored sibling nodes. There are at most m nodes to a leaf and b nodes branching off from each node, resulting in O(b^m) nodes.
Depth-Limited Search: Idea
Shortcoming in depth-first search:
Depth-first search does not terminate in infinite state spaces. Why?
Solution:…
New issue:…
Realization:
LIFO queue (last-in-first-out, also known as stack) for the frontier:…
Introduce depth limit l.
How to choose the depth-limit?
it first pops the most recently added node.
Depth-Limited Search: Performance
Reminder: Branching factor b, depth d, maximum length m of any path, and depth limit l.
Completeness:…
Optimality: …
Time complexity:
Space complexity:
No, if l < d. Why?
No, if l > d. Why?
Same as for depth-first search, but with l instead of m: O(bl).
Same as for depth-first search, but with l instead of m: O(bl).
Iterative Deepening Search: Idea and Algorithm
Shortcoming:
Solution:
function Iterative-Deepening-Search (problem) returns a solution or failure
for depth= 0 to ∞ do
result ← Depth-Limited-Search(problem, depth) if result ̸= cutoff then return result
Shortcoming in depth-limited search:
One typically does not know the depth d of the goal state.
Solution:
Use depth-limited search and iteratively increase the depth limit l.
Iterative Deepening Search: Performance
Reminder: Branching factor b, depth d, maximum length m of any path, and depth limit l.
Completeness: …
Optimality: …
Time complexity: …
Space complexity: …
Yes, if depth d of the goal state is finite.
Yes (if cost = 1 per step); not optimal in general.
The nodes at the bottom level are generated once, those on the next-to-bottom level are generated twice, and so on, up to the children of the root, which are generated d times:
(d)b+(d−1)b2+…+(1)bd =O(bd) which equals the one of breadth-first search.
Same as for depth-first search, but with d instead of m: O(bd). Why?
Comparison of Computational Effort
Bidirectional Search, Idea/Comments
Comparing Uninformed Search Strategies
Summary
check slides 124-129
