Brute Force & Branch and Bound
What is the main approach used in Brute Force search?
Tries every possible path to find the optimal one.
What is Dijkstra's Algorithm used for?
Finding the shortest path in graphs with non-negative weights.
What is an admissible heuristic in A*?
One that never overestimates the true cost to the goal.
What does IDA* stand for?
Iterative Deepening A*
What is Beam Stack Search?
A memory-efficient best-first search that limits expanded nodes per level.
How does Branch and Bound improve efficiency over Brute Force?
It uses cost bounds to prune suboptimal paths.
Why does Dijkstra's Algorithm not use a heuristic?
It selects nodes solely based on accumulated path cost.
What is the role of the function f(n) = g(n) + h(n) in A*?
It balances path cost so far (g) and estimated cost to goal (h).
How does RBFS differ from A*?
RBFS uses recursion with limited memory and avoids full open list storage.
Why is beam width important in Beam Stack Search?
It controls how many paths are explored at each level, affecting completeness.
When is Brute Force a valid strategy despite its inefficiency?
When the problem space is small or no heuristic exists.
Given nodes A-B (3), B-C (2), A-C (6), find the shortest path from A to C.
A → B → C with total cost = 5
If g(n) = 4 and h(n) = 3, what is f(n)?
f(n) = 4 + 3 = 7
Apply one iteration of IDA* where threshold = 6 and f(n) = 5. Expand or prune?
Expand, since f(n) is within the threshold.
With beam width = 2 and 5 candidate nodes, what happens?
Only the 2 best nodes based on evaluation are kept; rest are pruned.
Why does Branch and Bound use less memory than A*?
It prunes branches without storing all nodes.
Compare A* and Dijkstra: which is more efficient and why?
A* is often more efficient due to heuristics that guide the search.
How does heuristic quality affect A*’s performance?
A better heuristic leads to fewer node expansions and faster solutions.
Is A* always better than IDA*? Why
Not always; IDA* is more memory-efficient but may re-expand nodes.
Which is more efficient on large graphs: Beam Stack or RBFS? Why?
Depends on structure; Beam Stack is faster but may miss optimal paths.
Why is Branch and Bound more scalable than Brute Force in large search spaces? ?
Because it avoids evaluating all paths by eliminating unpromising ones early.
Modify Dijkstra’s to stop early when the goal is reached. What’s improved?
Time efficiency is improved by halting unnecessary computation.
What is the purpose of using heuristics in A*?
To estimate the cost to the goal and guide the search efficiently.
Combine RBFS and IDA* into a hybrid algorithm. What does it improve?
Combines depth-limited search with recursive memory reuse for efficiency.
Break down how Beam Stack Search uses divide-and-conquer.
It partitions search space and stores promising paths in a stack-like structure.