Terminology

Search: Process of finding an acceptable solution in the set of all possible candidate solutions
Frontier: Set of discovered locations that are pending exploration
Explored: Set of already explored locations
Plan: Set of already explored locations
Path: A sequence of locations
Heuristic: An educated guess
- Typically represents a rule of thumb (quick way to assess a situation) but not always the exact/correct answer
Optimal: Guaranteed to find the best possible solution (cost optimality)
Search Efficiency: Algorithm which visits fewest number of locations is the most efficient
Best-First Search: Explore a graph by prioritizing the most promising (best) node before less promising nodes
- What constitutes ‘promising’ changes from algorithm to algorithm
- Not to be confused with ‘greedy best-first search’
Informed Search: Any search algorithm using information about the goal to guide its search efforts

<aside> 📌 SUMMARY: Terminologies

</aside>

Check through all possible candidates

Brute Force

Enumerate all possible candidates in an indiscriminate manner until a solution / the best solution that reaches the goal is found

If the set of possible actions is infinite, then we can choose to do an early return
However if it is a finite set, then we can return the best solution

Expand nodes from the current depth before going onto the next depth.

Optimal only if the actions cost the same

Search for the solution by checking all nodes at the current depth before moving onto next depth

Example of BFS starting at C1

We iteratively expand at each node until we find the goal (at 3 cost, assume all actions are equal)
After the goal is found, return the solution (C1 → B1 → B2 → B3)

Expand from A to reach B and C

<aside> 📌 **SUMMARY:

All three algorithms (Brute-Force, Breadth-First, Uniform-Cost) are optimal (Brute-Force only if actions have same cost and Brute-Force only if finite set)
Only Breadth-First and Uniform-Cost are Best-First Search**

</aside>