我有一张地图，上面有目的地（下面的红点）和一些兴趣点（黄色、绿色和蓝色的点）。
我试图找到通往目的地的路径，但起点未定义 - 我只是希望它通过尽可能多的兴趣点，而不是迂回路线。
例如，在这种情况下，以下（粉红色线）将是一条很好的路线：
黄色的点是离目的地最远的 POI（在这种情况下没有用），绿色的点是接下来最远的四个。
任何人都可以提出一个适合这个的算法吗？
这是变成图表的合适问题吗？“不太迂回”的要求似乎暗示了这一点，但我将如何与想要通过尽可能多的 POI 相协调呢？
编辑：澄清“不太迂回”的要求。我只是希望它是一条合理的路线，例如所有拐角的总和最多转动 90 度。POI 将始终在目的地附近，因此长度并不是真正的问题。
问题可以明确地简化为所有 POIG=(V,E)所在的图，在这种情况下是（所有顶点之间的边）。您还需要生成一个权重函数，使得VEV x Vw:E->Rw(u,v) = distance between u and v
这个问题实际上是旅行商问题的一个变体，所以它是NP-Hard（所以没有已知的多项式解决方案） - 但看看周围，这个问题有很多启发式方法。
此外 - 如果您不期望有很多 POI（比如 20-30） - 可以使用动态规划解决方案来找到所有点之间的最佳路径。
看起来你可以把它变成一个图，为每个兴趣点分配一个负权重（可能通过减少通向该点的任何边的值），然后将所述图插入 Bellman-Ford 算法] 1，这允许负长度边缘。如果两个 POI 非常靠近，则可能会出现唯一的问题，因此可能需要某种修剪方法。