沿着兴趣点找到路径

Question

我有一张地图，上面标有目的地（下面的红点）和一些兴趣点（黄、绿和蓝点）。我想找到一条路径到达目的地，但起点未定义。我希望尽可能经过更多的兴趣点，而不是走太远的路线。例如，在这种情况下以下路径（粉色线）将是一个好的选择：黄点是距离目的地最远的兴趣点（在这种情况下没有用），绿色的是距离目的地次远的四个兴趣点。请问是否有合适的算法可以解决这个问题？这是一个适合转化为图形的问题吗？“不要走太远的路线”似乎暗示了这一点，但我如何与希望路径中尽可能经过更多的兴趣点协调呢？编辑：为了澄清“不要走太远的路线”的要求。我只是希望它是一个合理的路径，例如所有拐角的总和最多只有90度。兴趣点总是靠近目的地，因此长度并不是一个问题。

- user1671701

---

寻找最优路径是NP难问题，它基本上是旅行商问题的一个变体，你熟悉吗？ - amit

如@amit上面所述，那将是TSP问题。除非您设置条件来排除点，例如旅程的最大长度等，“尽可能多的POI”始终是全部。 - Orbling

如果图是无向的，则使用目标作为起点，因为起点未定义。 - UmNyobe

“尽可能多的POI”。您有类似于已经行驶距离的限制吗？ - UmNyobe

感谢您的快速反馈！@Orbling 假设我需要传递至少15个POI - “旅程的最大长度”听起来像是我的限制，可能可以有最大90度的航向变化或其他什么。 - user1671701

Answer 1

问题可以转化为一个图G=(V,E)，其中V是您所有的POI，而E在这种情况下是V x V（所有顶点之间的边）。您还需要生成一个权重函数w:E->R，使得w(u,v) = u和v之间的距离。

该问题实际上是旅行商问题的变体，因此它是NP-Hard（因此没有已知的多项式解决方案）-但是请四处看看，有许多启发式算法可用于解决此类问题。

此外-如果您不期望有很多POI（比如20-30个），则可以使用动态规划解决方案找到所有点之间的最优路径。

- amit

Answer 2

看起来你可以将它转化为一个图形，给每个感兴趣的点分配一个负权重（可能通过减少任何指向该点的边的值来实现），然后将该图形插入到Bellman-Ford算法1中，该算法允许负长度边。唯一的问题可能出现在两个POI非常接近的情况下，因此可能需要某种修剪方法。

- Sconibulus