Programming Game AI by Example

原文摘录   · · · · · · 

• Dijkstra’s algorithm builds a shortest path tree one edge at a time by first adding the source node to the SPT and then by adding the edge that gives the shortest path from the source to a node not already on the SPT. This process results in an SPT containing the shortest path from every node in the graph to the source node. (查看原文)

  马马马马马 2014-04-09 22:29:40

• Dijkstra’s algorithm searches by minimizing the cost of the path so far. It can be improved significantly by taking into account, when putting nodes on the frontier, anestimateof the cost to the target from each node under consideration. This estimate is usually referred to as aheuristic, and the name given to the algorithm that uses this method of heuristically directed search is A* (pronounced ay-star). A* proceeds in an almost identical fashion to Dijkstra’s search algo-rithm. The only difference is in the calculation of the costs of the nodes on the search frontier. The adjusted cost,F, to the node when positioned on the priority queue (the search frontier), is calculated as: F = G+H (5.3) where G is the cumulative cost to reach a node andHis the heuristic e... (查看原文)

  马马马马马 2014-04-09 22:39:18