Editing Talk:342: 1337: Part 2
|
Please sign your posts with ~~~~ |
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
| Latest revision | Your text | ||
| Line 7: | Line 7: | ||
::Why can not be A* implemented exactly as Dijkstra's is with additional penalty (the optimistic distance) calculated at every update? That way it would be as memory efficient as Dijkstra's. | ::Why can not be A* implemented exactly as Dijkstra's is with additional penalty (the optimistic distance) calculated at every update? That way it would be as memory efficient as Dijkstra's. | ||
[[Special:Contributions/162.158.202.118|162.158.202.118]] 23:48, 5 September 2017 (UTC) | [[Special:Contributions/162.158.202.118|162.158.202.118]] 23:48, 5 September 2017 (UTC) | ||
| β | :A* needs a priority queue to store nodes to be searched and their heuristic estimates (starting from the initial node), and a chart to store searched nodes and their shortest-path values. In the worst case, every node in the graph is searched and put on the chart and the queue is empty (equivalent to Dijkstra's). In the best case, the chart contains only nodes on the shortest path, and the queue might be empty or contain unexpanded nodes, and there will likely be an implicit set of nodes never examined. It is hard to see how Dijkstra's can be more memory efficient than A*, except | + | :A* needs a priority queue to store nodes to be searched and their heuristic estimates (starting from the initial node), and a chart to store searched nodes and their shortest-path values. In the worst case, every node in the graph is searched and put on the chart and the queue is empty (equivalent to Dijkstra's). In the best case, the chart contains only nodes on the shortest path, and the queue might be empty or contain unexpanded nodes, and there will likely be an implicit set of nodes never examined. It is hard to see how Dijkstra's can be more memory efficient than A*, except at or near the worst case. |
The mountain hideaway is a staple of Kung Fu movies. Kill Bill was effectively spoofing the genre, and so is this cartoon (rather than specifically spoofing Kill Bill). [[User:Danshoham|Mountain Hikes]] ([[User talk:Danshoham|talk]]) 04:17, 9 October 2015 (UTC) | The mountain hideaway is a staple of Kung Fu movies. Kill Bill was effectively spoofing the genre, and so is this cartoon (rather than specifically spoofing Kill Bill). [[User:Danshoham|Mountain Hikes]] ([[User talk:Danshoham|talk]]) 04:17, 9 October 2015 (UTC) | ||
