4 - Uninformed Search

Question 1

Define Uninformed Search

Answer 1

No Knowledge of the cost from current state to goal

Only knows when goal found

Question 2

Define Heuristic

Answer 2

Informed search

Access to extra info
Typically a cost estimate from a heuristic function

Question 3

What are the main steps of General search

Answer 3

1. If goal state return solution
2. Apply all applic. operators to current, gen new set of states - node/state expansion
3. Decide next state and repeat. No more states = fail

Question 4

What is a fringe/frontier?

Answer 4

The collection of nodes waiting to be expanded

Question 5

What is node expansion?

Answer 5

Generating all successor nodes considering the available actions

Question 6

Define search strategy

Answer 6

Which node is next

Question 7

What is BFS?

Answer 7

Expands shallowest on fringe first

Expand all at depth d before d+1

Use a queue structure

Question 8

What is DFS?

Answer 8

Expand deepest first

Follow branch fully

Use a stack

Question 9

What is depth limited search?

Answer 9

If a solution is known to be no deeper than a certain level then apply cut off depth

Question 10

What is IDS?

Answer 10

Iterative deepening search

1. Run DLS lim d = 1
2. if not found, run with d+1 until solution

same nodes generated multiple times

Question 11

Criteria for search method evaluation

Answer 11

Time
Space
COmpleteness
Optimality

Question 12

What is the branching factor?

Answer 12

Max num of successors of any node

Question 13

What are the complexities of BFS?

Answer 13

Time = O(b^d) where b is num of successors
Space = same as time
Completeness = Yes
Optimality = Yes, if step costs identical

Question 14

DFS complexities

Answer 14

Time = O((b^m) where m is max depth
Space = O(bm)

Completeness = No, may cause looping
Optimality = No

Question 15

DLS complexities

Answer 15

Time Complexity: every state has b successors, and depth limit l. O(bl).
• Space Complexity: Has space complexity O(bl).
• Completeness: Like DFS, DLS is not complete if the chosen depth is less than solution depth.
• Optimality: Like DFS, DLS is not optimal.

Question 16

IDS complexities

Answer 16

Time = O(b^d) as nodes must be examined more than once (depth d and successors b)

Space = O(bd)
Complete = Yes
Optimality = Yes

Question 17

What is UCS?

Answer 17

Uniform Cost Search

An extension of BFS which expands node with lowest path cost

Question 18

What is path cost?

Answer 18

The cost of getting from start node to this node

g(n)

Question 19

UCS COmplexities

Answer 19

Time = b times (c/e) where c is the cost of opimal solution and every action costs at least e

Space = same as time
Complete = yes if every cost step > 0
Optimality = yes

Question 20

What is Bidirectional Search?

Answer 20

Two simultaneous searches forward and backward.

Reduced time complexity but needs to compute successors and also predecessors