算法找到最短路径，与障碍 [英] Algorithm to find the shortest path, with obstacles

问题描述

我的积分从而重新presents一格，我在寻找一种算法，让我点A和B之间的最短距离的集合 美中不足的是任何时候（不包括A和B）可以有障碍物阻碍的道路，因而必须绕道。该路径不能移动对角线。

I have a collection of Points which represents a grid, I'm looking for an algorithm that gets me the shortest distance between point A and B. The catch being any point (excluding A and B) can have an obstacle obstructing the path, and thus must be detoured. The path may not move in diagonals.

有关其他人寻找解决这类问题，我发现这些引用是非常有用的：

For anyone else looking to solve this type of problem, I found these references to be very useful:

http://optlab-server.sce.carleton.ca/POAnimations2007/ DijkstrasAlgo.html

<一个href="http://en.literateprograms.org/Dijkstra%27s_algorithm_%28Java%29#chunk%20def:visit%20each%20vertex%20u,%20always%20visiting%20vertex%20with%20smallest%20minDistance%20first" rel="nofollow">http://en.literateprograms.org/Dijkstra%27s_algorithm_%28Java%29#chunk%20def:visit%20each%20vertex%20u,%20always%20visiting%20vertex%20with%20smallest%20minDistance%20first

推荐答案

这是一个很好的去处使用 A *搜索算法，启发式搜索算法，发现两点之间的最佳路径非常快，即使有障碍物present。这样做是为了在网格转换成图表其中在所述网格中的每个单元是一个节点，并且其中有未彼此妨碍任何两个相邻小区之间的边缘。一旦你有了这个图，你要找的答案是从起始节点到目的节点图中的最短路径。

This is an excellent spot to use the A* search algorithm, a heuristic search algorithm that finds optimal paths between points very quickly even when there are obstacles present. The idea is to convert the grid into a graph where each cell in the grid is a node and in which there is an edge between any two adjacent cells that aren't obstructed from one another. Once you have this graph, the answer you're looking for is the shortest path in the graph from the start node to the destination node.

为了使用A *，你需要一个启发函数的猜测，从发车到目的地方任何一点的距离。一个良好的启发式这是使用两点之间的曼哈顿距离。

In order to use A*, you'll need a heuristic function that "guesses" the distance from any point on the grid to the destination square. One good heuristic for this would be to use the Manhattan distance between the two points.

如果您正在寻找寻找最短路径更容易，但仍然非常有效的算法，考虑寻找到 Dijkstra算法< /一>，它可以被看作是A *简化版本。它比A *慢一点，但仍运行速度非常快，并保证最佳的答案。

If you're looking for an easier but still extremely efficient algorithm for finding the shortest path, consider looking into Dijkstra's algorithm, which can be thought of as a simpler version of A*. It's a bit slower than A*, but still runs extremely quickly and guarantees an optimal answer.

希望这有助于！

这篇关于算法找到最短路径，与障碍的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！