Artificial Intelligence Search and Optimization Syllabus

Search and Optimization syllabus — full chapter and topic list

Expand any chapter to see its topics and sub-topics. This is the whole examinable outline for Search and Optimization in Artificial Intelligence, not a summary of it.

1. 1

   Uninformed Search Strategies

   5 topics

   • Breadth-First Search
   • Uniform-Cost Search
   • Depth-First and Depth-Limited Search
   • Iterative Deepening Search
   • Bidirectional Search
2. 2

   Informed (Heuristic) Search

   4 topics

   • Greedy Best-First Search
   • A* Search
   • Memory-Bounded Heuristic Search
   • Designing Heuristics
3. 3

   Local Search and Optimization

   5 topics

   • Hill-Climbing Search
   • Simulated Annealing
   • Local Beam Search
   • Genetic Algorithms
   • Continuous Space Optimization
4. 4

   Search in Complex Environments

   3 topics

   • Searching with Nondeterministic Actions
   • Searching with Partial Observations
   • Online Search Agents
5. 5

   Adversarial Search and Games

   5 topics

   • Minimax Algorithm
   • Alpha-Beta Pruning
   • Imperfect Real-Time Decisions
   • Stochastic and Partially Observable Games
   • Monte Carlo Tree Search
6. 6

   Constraint Satisfaction Problems

   5 topics

   • Defining CSPs
   • Constraint Propagation
   • Backtracking Search
   • Local Search for CSPs
   • Structure of Problems

Search and Optimization flashcards for Artificial Intelligence

21 of 50 cards from the Search and Optimization deck — real questions with worked answers.

1. What is the completeness, optimality, time complexity, and space complexity of Breadth-First Search (BFS)?

   BFS is complete (if branching factor $b$ is finite) and optimal (when all step costs are equal). Time and space complexity are both $O(b^{d})$, where $b$ is the branching factor and $d$ is the depth of the shallowest goal. Its large memory requirement is usually the bigger problem than its time.

2. In Breadth-First Search, why is a node tested for the goal when it is generated rather than when it is selected for expansion?

   BFS applies the goal test to each node when it is generated (not when expanded), because all nodes at a given depth are expanded before any deeper node. Testing at generation lets BFS stop as soon as the shallowest goal is first produced, saving a full extra layer of expansion.

3. What does Uniform-Cost Search expand, and what is the ordering criterion of its frontier?

   Uniform-Cost Search (UCS) expands the node with the lowest path cost $g(n)$ (cumulative cost from the start), using a priority queue ordered by $g(n)$. Unlike BFS, it optimizes for total path cost rather than number of steps.

4. State the completeness and optimality conditions for Uniform-Cost Search, and give its complexity.

   UCS is complete and optimal provided every step cost is $\geq \epsilon > 0$. Its time and space complexity are $O\!\left(b^{1+\lfloor C^{*}/\epsilon \rfloor}\right)$, where $C^{*}$ is the cost of the optimal solution and $\epsilon$ is the minimum step cost. This can be much worse than $O(b^{d})$ because UCS may explore large trees of small steps.

5. Why does Uniform-Cost Search apply the goal test when a node is selected for expansion rather than when generated?

   UCS delays the goal test until a node is chosen for expansion because a goal found early (on generation) may lie on a suboptimal path; a cheaper path to it may still be discovered. It also re-checks whether a better path to a frontier node has been found. This guarantees optimality.

6. What are the completeness, optimality, time, and space complexities of Depth-First Search (DFS) in tree-search form?

   Tree-search DFS is not complete (can loop on infinite paths or repeated states) and not optimal. Time complexity is $O(b^{m})$ and space complexity is $O(bm)$, where $m$ is the maximum depth of the search tree. Its key advantage is linear memory use.

7. What is Depth-Limited Search, and what problem does the depth limit introduce?

   Depth-Limited Search is DFS with a predetermined depth limit $\ell$: nodes at depth $\ell$ are treated as having no successors. It solves DFS's infinite-path problem but becomes incomplete if $\ell < d$ (goal deeper than the limit) and nonoptimal if $\ell > d$. Its complexities are $O(b^{\ell})$ time and $O(b\ell)$ space.

8. How does Iterative Deepening Search (IDS) work, and why is its repeated regeneration of nodes acceptable?

   IDS runs Depth-Limited Search repeatedly with limits $\ell = 0, 1, 2, \dots$ until a goal is found. Repeated work is acceptable because in a tree with branching factor $b$, most nodes are in the bottom level, so regenerating the upper levels adds only a constant-factor overhead.

9. State the completeness, optimality, and complexity of Iterative Deepening Search.

   IDS is complete (finite $b$) and optimal when step costs are all equal. Time complexity is $O(b^{d})$ and space complexity is $O(bd)$. It combines DFS's linear memory with BFS's completeness and shallow-goal optimality, making it the preferred uninformed method when the search space is large and depth unknown.

10. What is Bidirectional Search and what is its main computational advantage?

    Bidirectional Search runs two simultaneous searches — one forward from the initial state and one backward from the goal — stopping when the frontiers meet. Its advantage is complexity roughly $O(b^{d/2})$ in time and space instead of $O(b^{d})$, since $b^{d/2} + b^{d/2}$ is far smaller than $b^{d}$.

11. What are the main requirements and difficulties of implementing Bidirectional Search?

    It requires the ability to compute predecessors (to search backward) and an efficient way to test whether the two frontiers intersect (e.g., a hash table). Difficulties: defining the backward search when there are many goal states, and handling abstract or implicitly defined goals for which predecessors are hard to generate.

12. What evaluation function does Greedy Best-First Search use, and is it optimal?

    Greedy Best-First Search expands the node that appears closest to the goal, using the evaluation function $f(n) = h(n)$, where $h(n)$ is the heuristic estimate of cost from $n$ to the goal. It is not optimal and, in tree-search form, not complete (can get stuck in loops); it ignores the cost already incurred, $g(n)$.

13. Write the evaluation function used by A* Search and explain each term.

    A* uses $$f(n) = g(n) + h(n),$$ where $g(n)$ is the cost of the path from the start node to $n$, and $h(n)$ is the heuristic estimate of the cheapest cost from $n$ to a goal. Thus $f(n)$ estimates the cost of the cheapest solution through $n$.

14. Define an admissible heuristic and state its role in A* optimality.

    A heuristic $h(n)$ is admissible if it never overestimates the true cost to reach the goal: $0 \leq h(n) \leq h^{*}(n)$, where $h^{*}(n)$ is the true optimal cost from $n$. Admissibility guarantees that A* using tree search is optimal, because $f(n)$ never overestimates the true cost of a solution through $n$.

15. Define a consistent (monotonic) heuristic and give its defining inequality.

    A heuristic $h$ is consistent if for every node $n$ and every successor $n'$ generated by an action of cost $c(n, a, n')$: $$h(n) \leq c(n, a, n') + h(n').$$ This is a form of the triangle inequality. Consistency implies admissibility and guarantees A* with graph search is optimal, since $f$ is nondecreasing along any path.

16. What does it mean that A* is optimally efficient, and what is the relationship between consistency and admissibility?

    A* is optimally efficient: no other optimal algorithm using the same heuristic $h$ is guaranteed to expand fewer nodes than A* (up to tie-breaking). Every consistent heuristic is admissible, but not every admissible heuristic is consistent; consistency is the stronger property needed for optimal graph search.

17. In A*, what can you say about the $f$-costs of nodes expanded, and what is the C*-contour concept?

    With a consistent heuristic, A* expands nodes in nondecreasing order of $f$. A* expands all nodes with $f(n) < C^{*}$, some nodes with $f(n) = C^{*}$, and no nodes with $f(n) > C^{*}$, where $C^{*}$ is the optimal cost. These form 'contours' in the state space, analogous to UCS's uniform bands when $h = 0$.

18. Name two memory-bounded heuristic search algorithms and describe how IDA* limits memory.

    Two memory-bounded variants are IDA* (Iterative-Deepening A*) and RBFS (Recursive Best-First Search); also SMA* (Simplified Memory-Bounded A*). IDA* uses linear memory by doing iterative deepening on the $f$-cost: the cutoff at each iteration is the smallest $f$-value that exceeded the previous cutoff, rather than a depth limit.

19. How does Recursive Best-First Search (RBFS) achieve linear memory, and what is its main inefficiency?

    RBFS mimics best-first search using only linear space by recursively exploring the best path while keeping an $f\_limit$ equal to the best alternative $f$-value from an ancestor. When the current path exceeds $f\_limit$, it backs up and stores the best $f$-value of the forgotten subtree in its parent (backed-up value). Its inefficiency is excessive node regeneration when it repeatedly switches between promising paths.

20. How does SMA* handle running out of memory during search?

    SMA* (Simplified Memory-Bounded A*) proceeds like A* until memory is full, then drops the worst leaf node (highest $f$-value), backing up its $f$-value to its parent so the forgotten subtree can be regenerated later if needed. It is complete and optimal if the optimal solution fits within available memory; otherwise it returns the best reachable solution.

21. When combining two admissible heuristics, which should you use, and why is the answer 'the maximum'?

    Given admissible heuristics $h_{1}$ and $h_{2}$, use $h(n) = \max\{h_{1}(n), h_{2}(n)\}$. The maximum is still admissible (never exceeds the true cost) and dominates each individual heuristic, so it expands no more nodes than either alone — a more accurate estimate that stays a valid lower bound.

See more Search and Optimization flashcards →

Planning Search and Optimization for Artificial Intelligence

Search and Optimization (Artificial Intelligence) FAQ