使用机器学习/人工智能的最短根

Question

假设我有一组散落在XY平面上的点，我有两个点，即开始点和终点，在XY平面上的任何位置。我想找出起点和终点之间的最短路径，而不触及零散点。路径必须保持一定的偏移量(即假设路径有一定的宽度)。如何在编程中解决这类问题，机器学习中是否有算法？

Answer 1

所以你需要一个贪婪的最短路径算法？试试Dijsktra的算法。http://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/

最低价格的最短解决方案。

Answer 2

您还可以考虑A*算法。

这可以找到与Dijkstra算法相同的解决方案，但通常以较低的计算成本(这在您的情况下可能很重要，因为在空间离散化之后，您可能会得到一个大的网格)。

这是因为A*使用一个启发式来偏倚搜索，因此它首先寻找更有希望的方向(例如，向目标移动原则上是一个好主意，所以首先尝试)。

您可以看到A*正在运行这里和(与Dijkstra的算法并排-谢谢@Thrawn提供链接)、这里的一些可视化。

Answer 3

这不是一个机器学习问题，而是一个优化问题。

所以你需要一个贪婪的最短路径算法

确实可以这样解决，但挑战是将网格表示为一个图形.例如，将网格分解为n×n矩阵。在最短路径算法中，节点是矩阵的一个元素(因此不包括包含散乱点的矩阵元素)，而弧的权重是距离。

然而，n必须是小的，因为最短路径协商是np难问题.

对于这个特定的问题，也许还有其他的算法，但我不知道。