Informed Search Flashcards

1
Q

What is cost cost-sensitive search?

A

Similar to BFS, but sorts the queue using the path cost. Unfortunately, this search explores in every “direction.”

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is a heuristic?

A

A function that estimates how close a state is to a goal.
Designed for a particular search problem
A rule of thumb that helps decide which is the most promising path to take during search.
In search, heuristic should be an underestimate of actual cost to get from current node to any goal.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is an informed search strategy?

A

One that uses problem-specific knowledge beyond the definition of the problem itself
One can find solutions more efficiently than an uninformed strategy.
Often implemented using a priority queue to store frontier nodes.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is greedy (best-first) search?

A

This search selects the node for expansion using the heuristic function for its evaluation function. Greedy search minimises the estimated cost to the goal, it expands whichever node n is estimated to be closest to the goal.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What are the properties of greedy best-first search?

A

Completeness - guaranteed, if b is finite and with repeated state-checking
Admissibility - not guaranteed
Space - O(b^m)
Time - O(b^m)
Optimal - no

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is A* search?

A

Uses both the cost of path generated and estimated to goal to order nodes on the frontier.
f(n) = g(n) + h(n)
g(n) - cost from initial node to node n
f(n) - estimated total cost of cheapest solution through node n
f(n) is the estimated cost of the cheapest solution extending this path

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What are the properties of A* search?

A

Completeness - guaranteed
Admissibility - guaranteed is heuristic is admissible/consistent
Space- O(b^d)
Time - O(b^d)
Optimal - yes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is admissiblility?

A

An admissible heuristic is one that never overestimates the cost to reach the goal. Admissible heuristics are by nature optimistic because they think the cost of solving the problem is less than it actually is.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is consistency?

A

A heuristic is consistent if for every node n, if the summed path cost is less than the straight cost to get to the same node.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is Euclidean distance?

A

sqrt((x2-x1)^2 + (y2-y1)^2)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is Manhattan distance?

A

|x1 - x2| + |y1 - y2|

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is iterative deepening A* search?

A

A low memory variant of A* which performs a series of depth-first searches bu cuts off each search when the sum f(n) exceeds some predefined threshold.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is dominance?

A

If one heuristic is better than another, it is a dominant hueristic

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What are the properties of A* search?

A

Completeness - guaranteed
Admissibility - guaranteed if heuristic is admissible/consistent
Space - O(bd)
Time - O(b^d)
Optimal - yes (assuming h(n) is admissible)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is the difference between A* search and iterative deepening A*?

A

Memory wise, IDA* is better for memory, worse for time
A* uses a priority queue, IDA* uses a stack
A* uses open and closed lists, but IDA* doesn’t use either.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly