A* search algorithm: Difference between revisions
Attempt at clarification and added an extra credit
(corrected heuristic) |
(Attempt at clarification and added an extra credit) |
||
Line 2:
<!-- A* is pronounced as: A star !-->
The A* search algorithm is an extension of [[Dijkstra's algorithm]] useful for
The algorithm should not assume that all edge costs are the same. It should be possible to start and finish on any node, including ones identified as a barrier in the task.
;Task
Line 18 ⟶ 19:
Note: using a heuristic score of zero is equivalent to Dijkstra's algorithm and that's kind of cheating/not really A*!
;''Extra Credit''
Use this algorithm to solve an 8 puzzle. Each node of the input graph will represent an arrangement of the tiles. The nodes will be connected by 4 edges representing swapping the blank tile up, down, left, or right. The cost of each edge is 1. The heuristic will be the sum of the manhatten distance of each numbered tile from its goal position. An 8 puzzle graph will have 9!/2 (181,440) nodes. The 15 puzzle has over 10 trillion nodes. This algorithm may solve simple 15 puzzles (but there are not many of those).
<br><br>
;See also:
* Wikipedia webpage: [https://en.wikipedia.org/wiki/A*_search_algorithm A* search algorithm].
* [https://www.redblobgames.com/pathfinding/a-star/introduction.html An introduction to: Breadth First Search |> Dijkstra’s Algorithm |> ''A*'']
<br>
;Related
* [[
<br><br>
| |||