Day 8

Question 1

For this particular problem, greedy best-first search using ℎ𝑆𝐿𝐷 finds a solution without ever expanding a node that is not on the solution path. The solution it found does not have optimal cost

Answer 1

This is why the algorithm is called “greedy”—on each iteration it tries to get as close to a goal as it can, but greediness can lead to worse results than being careful

Question 2

The most common informed search algorithm is A* search (pronounced “A-star search”), a best-first search that uses the evaluation function 𝑓 𝑛 = 𝑔 𝑛 + ℎ(𝑛)

Answer 2

where g(n) is the path cost from the initial state to node n, and h(n) is the estimated cost of the shortest path from n to a goal state

Question 3

Greedy best-first graph search is complete in finite state spaces, but not in infinite ones.

Question 4

The worst-case time and space complexity is O(|V |). With a good heuristic function, however, the complexity can be reduced substantially, on certain problems reaching O(bm)

Question 5

A key property is admissibility: an admissible heuristic is one that never overestimates the cost to reach a goal

Question 6

A* search is complete

Question 7

With an admissible heuristic, A* is cost-optimal

Answer 7

With an inadmissible heuristic, A* may or may not be cost-optimal.

Question 8

With an inadmissible heuristic, A* may or may not be cost-optimal.