3 - Informed Search

Question 1

Informed Search Techniques …

Answer 1

… have additional information about more promising paths and are therefore more efficient than uninformed search algorithms.

Question 2

The choice of the next node is based on ________.

Answer 2

The choice of the next node is based on THE EVALUATION FUNCTION f(n).

Question 3

A heuristic h(n) is admissible iff …

Answer 3

UNDERESTIMATE: h(A) <= c(A; goal)

Question 4

A heuristic h(n) is consistent iff …

Answer 4

TRIANGLE INEQUALITY: h(A) <= c(A;B) + h(B)

Question 5

The performance of the heuristic depends on the ________.

Answer 5

… on the QUALITY OF THE HEURISTIC.

Question 6

What are good possibilities to obtain decent heuristics?

Answer 6

Relaxed problems and pattern databases

Question 7

Greedy Best-First Search (GBFS)

Answer 7

Evaluation function is heuristic: f(n) = h(n)

Question 8

GBFS explores ________ which is ________.

Answer 8

GBFS explores THE NODE WITH THE LOWEST HEURISTIC FUNCTION which is NOT ALWAYS OPTIMAL.

Question 9

GBFS: Completeness

Answer 9

GBFS is complete if graph search is used

Question 10

GBFS: Optimality

Answer 10

GBFS is NOT optimal

Question 11

GBFS: Time/Space Complexity

Answer 11

GBFS has EXPONENTIAL time complexity O(b^m) and EXPONENTIAL space complexity O(b^m)

Question 12

A* Search (A*)

Answer 12

Evaluation function is sum of heuristic and path cost: f(n) = h(n) + c

Question 13

A*: Completeness

Answer 13

A* is complete if costs > 0

Question 14

A*: Optimality

Answer 14

A* is optimal iff costs > 0 && heuristic admissible

Question 15

A*: Time/Space Complexity

Answer 15

A* has EXPONENTIAL time complexity O(b^(eps*d)) and EXPONENTIAL space complexity O(b^(eps*d))

Question 16

The epsilon parameter for A* determines ________.

Answer 16

Epsilon determines the PERFORMANCE OF THE HEURISTIC (0 -> good / 1 -> bad).

Question 17

Main disadvantage of A* and solution

Answer 17

Possibly huge space consumption –> Use Iterative Deepening A*

Question 18

Informed search methods require a ________ that estimates ________.

Answer 18

Informed search methods require a HEURISTIC FUNCTION that estimates THE COST h(n) FROM A NODE TO THE GOAL.