(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.
Comentários