It finds the optimal path between a starting state S and a goal state G by exploring nodes with the least cumulative cost from S, until reaching G and there are no paths from S that are shorter than the current path to G, this is when it knows it successfully found the shortest path between S and G, and terminates.
This will always find the optimal path from S to G, but if there are alot of paths with similar costs, it’ll have a broad movement while exploring states (similar to BFS) and will explore alot of unnecessary states before reaching the goal state.
How could this be solved? find another way to differentiate paths with similar costs.
A* solves this by adding a heuristic value to the total cost of a state path…
- (!) UCS is identical to BFS if path costs are all identical.
Example
…
Related Notes
| Thumbnail | Note | Type |
|---|