Intro
Searching is one of the most fundamental methods of solving problems in AI
Uninformed Search
Depth-First Search
Breadth-First Search
Uniform Cost Search (Dijkstra’s algorithm)
- Dijkstra’s Algorithm finds the shortest paths from one node to every other node
Informed Search
Greedy Best-First Search
- Greedy best-first search expands the node that is the closest to the goal, as determined by a heuristic function h(n).
- Search is therefore directed towards the goal, but obstacles may be in the way
- Want to find combination of greedy first search, which explores small number of nodes and UCS which is guaranteed to find a shortest path
A* Search
-
A* search considers not only h(n), the estimated cost from the current location to the goal, but also g(n), the cost that was accrued until the current location. By combining both these values, the algorithm has a more accurate way of determining the cost of the solution and optimizing its choices on the go. The algorithm keeps track of (cost of path until now + estimated cost to the goal), and once it exceeds the estimated cost of some previous option, the algorithm will ditch the current path and go back to the previous option, thus preventing itself from going down a long, inefficient path that h(n) erroneously marked as best.
