在障碍物周围找到一条边数最少的最短路径
本文关键字：最短路径 障碍物 周围找 一条 | 更新日期: 2023-09-27 18:03:52
我需要一种算法，可以为我提供两点之间最短路径的信息。路径应该有尽可能少的边，因为每个路点，每个转弯都要花费时间，而时间——在我的情况下——是昂贵的。
路径应该经过计算以绕过特定形状的障碍物(主要是圆形或矩形)。
存储路径的信息应该是路径路径点的笛卡尔坐标或极坐标(即我的单位执行的命令，如转向角度alpha，移动距离b)。然而，我更喜欢每个路径点的笛卡尔坐标。
没有导航网之类的东西，只有坐标系统和关于障碍物和其他禁区在哪里的信息，有些是固定的，有些可能(很可能)会移动。
啊，所有这些都应该在。net中可用。
感谢//edit:为了让事情更清楚一些，下面是我打算做的事情的图片:https://dl.dropbox.com/u/8802336/path.png
你的问题可以有两种解释。
1。我想找到最短路径，通过选择边数最少的一条来打破僵局
你可以通过在图的每条边的权值上添加一个非常小的数字ε来做到这一点。个数必须满足ε < 1/numberOfEdges。这将增加每条路径的长度*ε边，这意味着更短的路径将被首选。这甚至适用于负权边。注意浮点数的不准确性。
2。我想找到圈数最少的路径，通过选择具有最短路径
的路径来打破平局你可以通过给图上每条边的权值加上一个大数字E来做到这一点。个数必须满足E > sumOfAllEdgeWeights。这将确保只考虑具有最少边数的路径。这使得不能处理负权边。注意整数溢出
如果目标是:
1)最小化边数。
2)最小化距离。
按照这个顺序，你可以这样做:
1)从起点到终点画一条线。
2)计算你的直线与之碰撞的所有物体
3)对于每个对象，计算垂直于对象的两个点，使您可以将路径分成两个路径段。对于矩形，你可以把直线分成两段，对于线段A，看它可以通过四个角中的哪个，对于线段B，看它可以通过四个角中的哪个，然后尝试所有的组合，直到找到位移最小的两个。对于圆，我忘记怎么做了，但在两条路径段与圆齐平的两边只有一个解，所以你可以用三角函数或其他方法来解决(我会试着弄清楚:))
对于两个新路径，以递归分支方式调用4)。
4)对于生成的两个线段，重复计算，直到没有碰撞。与A*类似，你应该首先计算看起来最好的路径(剩余的碰撞最少，或者如果太难的话，先计算最浅的路径)。
5)根据你喜欢的指标选择最佳路径。以A*的方式，你应该保持你的列表排序，这样通过你的指标最好的路径在顶部，这样你就可以选择第一个路径来完成。
我不能在脑子里证明这总是有效，但我以前见过类似的东西。
编辑要计算两个线段在一个方向上绕圆的最近路径，请对每个线段执行
-边A:从起点(或终点)xs,ys到圆心xc,yc，长度= A
-边B:从中心xc,yc到圆周上的某处，所以长度= r
-边C:从边B的端点到x,ys(斜边)
A和B组成的角是一个直角，我们知道A和B的长度，所以我们可以计算出C的长度为根号(A^2+B^2)
最后，我们知道C的长度= A的长度/sin(角(B到C)) = B的长度/sin(角(A到C))，这意味着我们可以通过三角学来求出A到C的角和B到C的角
这让我们可以完整地构造路径段的一侧。对另一侧重复此操作，我们将路径分成两段，两段都与圆齐平->最小化添加的距离