Chapter 4: Heuristic Search

Question 1

Describe the Best-First Search algorithm

Answer 1

Similar to Breadth-First Search and Depth-First Search with lists of open and closed-state nodes. However, it uses a priority queue to retrieve higher-priority nodes first based on a heuristic function that estimates the cost of
a path to the goal state.

Question 2

Heuristics

Answer 2

Rules for choosing those branches in a state space that are most likely to lead to an acceptable problem solution

Question 3

Evaluation function

Answer 3

A function used to estimate the value of a particular state.

Question 4

Admissibility

Answer 4

Heuristics that find the shortest path to a goal whenever it exists.

Question 5

Monotonicity

Answer 5

When the same state is not found later in the search at a cheaper cost (and with a shorter path from the start state).
i.e. Algorithm A = Algorithm A*
i.e. estimated = actual

Question 6

Informedness

Answer 6

A heuristic’s estimation is more informative if it is closer to the actual cost than another heuristic.

Question 7

Algorithm A

Answer 7

Uses an evaluation function to estimate the cost of reaching the goal and prioritizes nodes based on their estimated cost, expanding the node with the lowest cost.

Question 8

Algorithm A*

Answer 8

When algorithm A is used with an evaluation function where the estimated cost to the goal is less than or equal to the cost of the minimal path to the goal.

Question 9

Compare Depth-First Search, Breadth-First Search, and Best-First Search

Answer 9

Algorithms that are used to search data structures to find a “goal state”. DFS uses a stack to explore as far down each path before backtracking, BFS uses a queue to explore all
nodes at the current depth before moving on to the next depth, and best-first search uses a priority queue and heuristic function to estimate the cost of paths and then
moves towards the most cost-effective path.

Question 10

What is the Best-First Search Algorithm?

Answer 10

1. Initialize:
   
   • Create a priority queue “OPEN”
   • Add start node to “OPEN”
   • Create a set “CLOSED”
2. Loop:
   
   • If “OPEN” is empty, fail
   • Remove lowest-priority node from “OPEN” as “current”
   • If “current” is the goal, return path
   • Add “current” to “CLOSED”
   • For each neighbour of “current”:
     
     • If not in “CLOSED”:
       
       • Calculate tentative cost
       • Add neighbour to “OPEN” with updated priority

Question 11

Algorithm A vs. Algorithm A*

Answer 11

A = estimation
A* = actual