Search

Question 1

What is a path of search?

Answer 1

Goal > Problem > Means > Solution > Sequence

Question 2

What are all the states ?

Answer 2

Initial state, actions, transition model.

Goal test: path cost, solution

Question 3

What is a state?

Answer 3

A state is a (representation of) a physical configuration.

Question 4

What is a node?

Answer 4

A node is a data structure constituting part of a search tree that
includes state, parent node, ac on, path cost g(x), depth.

Question 5

BFS?

Answer 5

• Guaranteed to reach sol if one exists
• Shortest/cheapest sol (in terms of no. of operations)
• Can take time to reach sol.
• b^d memory req (space complexity)
• b+b^2+b^3+….+b^d nodes expanded (time complexity)

Question 6

DFS?

Answer 6

• Guaranteed to reach sol if one exists
• Sol not necessarily the best
• Time taken less than BFS
• Memory req. less than BFS: b*m (branching factor * max depth)
• May not terminate if wrong branch expanded

Question 7

DLS ?

Answer 7

• Good space complexity
• Need ‘depth limit’ on branches
• Will then always terminate
• Sol guaranteed if one exists within that depth bound

Question 8

IDS?

Answer 8

Same as DLS, but with iterative deepening by d=d+1, every time a solution is not found, until it is.

• Useful is the search space is large and the max depth d of solution isn’t known.
• Trade off time for memory
• Memory req: b*d (space complexity)
• Nodes expanded: converges to b^d (really its the ∑(d+1-i)*b^i, i=0) (time complexity)
• Longer than BFS but savings on memory are insane
• May repeat nodes!

Question 9

3 ways to avoid repeated states in IDS?

Answer 9

• Do not return to the state you have just come from
• Do not create paths with cycles in them
• Do not generate any state that was ever generated before

Question 10

Goal vs data driven?

Answer 10

• Data driven: initial state to the goal
• Goal driven: goal to the initial state

Usually more efficient, as few paths actually reach the goal. Often used in expert systems, and prolog.

Question 11

Bi-Directional Search ?

Answer 11

• If unsure of branching factor, then can search from both ends for best results

Pros:
- Efficient: 2b^(d/2) time complexity

Cons:

• Must be able to generate predecessors of states
• Must be efficient way to check if each node appears in other search
• Impractical for large d
• Space complexity: b^(d/2) memory req.