Search

Question 1

What defines a search problem?

Answer 1

1. initial state (e.g. London)
2. sccuessor function (e.g. London->{Berlin, Rome})
3. goal test (e.g. ex: are we in Paris? or impl: are we near a big tower?)
4. path cost (e.g. km traveled)

Question 2

What is a solution to a search problem?

Answer 2

A sequance of actions that leads us from the initial state to a goal state.

Question 3

How do “Tree search algorithms” work?

Answer 3

• generating successors of already-explored states (expanding states)
• maintaining a list of states available for expansion (no closed list)

Question 4

Implementation: sates vs. nodes what’s the difference?

Answer 4

• A state is a representation of a phisical configuration
• A node is a data structure constituting part of a search tree
  it includes parent, children, depth, path cost

States do not have parents, children, depth, or path cost!

Question 5

How do “Graph search algorithms” work?

Answer 5

• generating successors of already-explored states (expanding states)
• maintaining a list of states available for expansion and a list of already explored states (frontiet + closed list)

Question 6

Search strategies…

Answer 6

• define the order of node expansion

Question 7

Types of search strategies are…

Answer 7

• uninformed search: basic algorithms
• informed search: further information about solution costs (heuristics)
• local search: “historyless”, one-step change

Question 8

Search strategies are evaluated by…

Answer 8

• completeness: does it always find a solution if one exists?
• time complexity: number of nodes generated/expanded
• space complexity maximum number of nodes in memory
• optimality: does it always find a least-cost solution?

Question 9

BFS

Answer 9

Breadth-first search

• expand shallowest unexpanded node
• frontier is a FIFO queue
• goal test at generation

complete? Yes (if b is finite)
time? O(b^d)
space? O(b^d) every node is kept in memory
optimality? Yes (if cost = 1 per step); not optimal in general

Question 10

UCS

Answer 10

Uniform-cost search

• expand least-cost unexpanded node
• frontier = queue ordered by cost, lowest first
• goal test at expansion => otherwise might miss better solution

complete? Yes, if step cost has a lower bound
time? O(b^(1+x))
space? O(b^(1+x))
optimal? Yes, goal test at expansion time ensures optimality

Question 11

DFS

Answer 11

Depth-first search

• expand deepest unexpanded node
• frontier is a LIFO queue

complete? No, fails in infinte-depth spaces, spaces with loops
time? O(b^m) m … max depth
space? O(b*m), linear space!
optimality? No

Question 12

DLS

Answer 12

Depth-limited search

• Depth-first search (DFS) with depth limitation, when reaching it report a cutoff

Question 13

IDS

Answer 13

Iterative deepening search

• Depth-limited search + systematically increase depth limit => gain completeness

complete? Yes
time? O(b^d)
space? O(b*m), linear space!
optimality? Yes, if step cost = 1, modifiable to explore uniform-cost tree

Question 14

Why IDS?

Answer 14

Iterative deepening search uses only linear space and not much more time than other uninformed algorithms.

Time: b/(b-1) * BFS