在一个多边形中找到最少代价的路径

Question

在一个多边形中找到最少代价的路径

algorithmmathgraphpolygongraph-algorithm

5

我试图找到一个考虑成本的多边形内路径。在我的具体情况中，我有一个角色，它只能相对直线行动，也就是说，它不应该与向北、向东、向南或向西移动相差超过几度。理想情况下，我会分配一个随着偏差增加而增加的成本。我认为这是与图论相关的问题，但我不知道如何在多边形中实现这一点...在插图中，红色虚线路径是常规算法产生的路径；绿色路径是我想要的路径。编辑：我有点搞砸了图片；为了澄清：红色路径意味着是多边形内最短的可能路径，我确实希望绿色路径是在角度约束下可能的最短路径。 (为了澄清，如果我的多边形看起来像(1)，我希望路径像(2)一样，而不仅仅是两点之间的直线)。

(1)   ,-------------------+      (2)   ,-------------------+
     /               (B)  |           /               (B)  |
    /                     |          /                /    |
+--+                      |  ->  +--+                /     |
|                       +-+      |                  /    +-+
| (A)                   |        | (A)-------------+     |
+-----------------------+        +-----------------------+

- user1449556

A* 可能可以适应您的角度限制。 - sp2danny

你的空间是离散的还是连续的？ - Vikram Bhat

@VikramBhat 这是连续的，可以作为一组点/顶点或三角化的形式出现。 - user1449556

@sp2danny A*/Dijkstra算法看起来很有前途，但我不确定如何将它们适应于多边形，特别是因为没有离散节点 - 我想我可以使用多边形的顶点作为节点，但由于理想路径不一定遵循边缘，所以我认为那样做行不通... - user1449556

3个回答

1

运行一个快速探索随机树算法，但将探索方向限制在几度平行于轴的方向上，并选择较大的增量距离以保持转向次数较低。基本上可以按照您的意愿添加任何启发式方法。快速探索随机树：一种新的路径规划工具是关于快速探索随机树的开创性论文。

- user3784553

1

我在这里添加另一个答案，因为它与我的其他答案大不相同。从常规路径查找算法的结果开始，运行随机优化以最大化适应度函数，该函数描述了通过添加顶点、移动顶点和删除路径中的顶点来使路径“相对直线”（如果您希望还可以包括短和其他指标）的程度，同时仍保持路径有效。

常见的随机优化方法包括模拟退火。

- user3784553

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- 1k5 · Accepted Answer

这其实更像是一条评论，但是我不能发表评论因为需要50个声望... 另一方面，我认为这个问题没有令人满意的答案，因为它没有明确定义。但是对于一个有趣的问题+1 :-)

给出红色虚线的算法从路径的起点和终点之间的直线开始（它并不完全在多边形内）。然后你沿着多边形的边缘滑动，直到你碰到一个角落，并把它作为你的新起点。（请注意，你画的红色虚线并不是真正的最短路径。）现在你的绿线基本上是红线，你用更好的路径替换了不喜欢的部分（错误的角度），这些路径更长，但出于某种原因更好（好的角度）。这也是为什么你得到了你下面例子的“正确”答案。只需从(A)到(B)的直线开始，这是最短的路径，也在多边形内。现在用更有利的角度替换这条直线。（这可能会迫使你通常要转弯很多次...）

只是一些想法。