Review of search

(19th-April-2020)

Here is the review of search.

• Many problems can be abstracted as the problem of finding paths in graphs.

• Breadth-first and depth-first searches can find paths in graphs without any extra knowledge beyond the graph.

• A* search can use a heuristic function that estimates the cost from a node to a goal. If this estimate underestimates the actual cost, A* is guaranteed to find a least-cost path first.

• Iterative deepening and depth-first branch-and-bound searches can be used to find least-cost paths with less memory than methods such as A*, which store multiple paths.

• When graphs are small, dynamic programming can be used to record the actual cost of a least-cost path from each node to the goal, which can be used to find the next arc in an optimal path.

Here is some training for your study. Let’s enjoy.

• Design the search algorithm for automatic driving car.

• In general, a search problem is formalized as :

• state space

• special start and goal state(s)

• operators that perform allowable transitions between states

• cost of transitions

• All these can be either deterministic or probabilistic.