找到障碍的最短路径的算法
我有一个表示网格的Points集合，我正在寻找一种算法，该算法可使我在A点和B点之间的距离最短。任何点（不包括A点和B点）的捕获都可能会阻碍路径，并且因此必须绕道而行。路径可能不会沿对角线移动。
对于希望解决此类问题的其他人，我发现这些参考非常有用：
http://optlab-
server.sce.carleton.ca/POAnimations2007/DijkstrasAlgo.html
http://en.literateprograms.org/Dijkstra%27s_algorithm_%28Java%29#chunk%20def:visit%20each%20vertex%20u,%20always%20visiting%20vertex%20with%20smallest%20minDistance%20first
回答：
这是使用A
*搜索算法的极好地方，该算法是一种启发式搜索算法，即使存在障碍物也可以非常快速地找到点之间的最佳路径。想法是将网格转换为图形，其中网格中的每个单元都是一个节点，并且在任意两个相邻单元之间没有被彼此阻挡的边。拥有该图形后，您要寻找的答案是图形中从起始节点到目标节点的最短路径。
为了使用A
*，您需要一个启发式函数来“猜测”网格上任何点到目标正方形的距离。一种很好的启发方法是使用两点之间的曼哈顿距离。
如果您正在寻找一种更简单但仍然非常有效的算法来查找最短路径，请考虑研究Dijkstra的算法，可以将其视为A
的简单版本。它比A 慢一些，但仍然运行得非常快，并保证了最佳答案。
希望这可以帮助！
以上是 找到障碍的最短路径的算法 的全部内容， 来源链接： utcz.com/qa/408698.html
