Question

有障碍物情况下的二维空间中两点间的最短路线

问题的来源：我经常在路上走路，发现人们都爱抄近路，于是就不禁思考起这个问题：给定一个任意的含障碍物的地图，如何找到两点间的最短路线？

规则：
1. 问题讨论的空间是二维的欧氏空间（不弯曲的）。
2. 障碍物的形状是任意的闭集（点集）。
3. 不可穿过障碍物的内部。

显然，如果没有障碍物，则根据欧几里得几何中的公理，两点之间，线段最短。
如果两点之间的线段没穿过障碍物，则最短路线还是线段。
开始我以为很简单，不断地一步步做切线，每次取最短的切线段就行了，后来发现了如图中的反例。
后来又觉得找出两两障碍物的公切线，然后计算各种组合间的公切线就行了。后来又发现我又错了。因为上一个点和公切线的一个端点之间的连续可能会穿过障碍物。。。
不知道这个问题到底有多深，会不会用到变分法？
To 钟学秀：
谢谢你的回复，不过貌似我已经把问题解决了：
1. 用多边形近似障碍物；
2. 用每一个障碍物的凸包替换它们自身；
3. 除了穿越障碍物内部的连线外，把所有障碍物的顶点、起点、终点之间两两连线。
于是问题转化为图的问题，然后用A*算法或 Dijkstra 算法解之。
To 鸿均的信徒：谢谢回复。不过你的方法即使连外绕的最短路线也得不到（而且从切点怎么走向下一个点你也没说清），呵呵。
To langzi2007：你的想法很有创造性，把障碍物看做镜面，从起点出发的无数光路中只有一条经过终点，问题就是，如何找到这条光路？你把一个数学问题转化为了物理问题，可是新问题并不比旧问题更容易解决。（不好意思，刚刚发现，有时候A到B的光路不止一条，例如可以直线或者多次反射后到达，有时候一条都没有，比如只在中间有一个障碍物）
另外纠正一下你的一个错误：“速度达到接近光速才能体现出物质波来”应为“尺度接近普朗克长度才能体现出物质波来”，巨大的光速c掩盖的是时空的本性，极小的普朗克长度h掩盖的才是物质的波动性。
关于你的问题，简单的说，定积分求的是一个数，变分法求的是一个函数。

Answer 1

这里只讨论一个障碍物的情况，多个障碍物时可以用计算机迭代找出来，这里相当介绍你一个算法。障碍物为一个闭集，由巴拿赫定理的几何形式知存在一个支撑泛函f1使得f1（A）=0;几何上解释为过点A有一条切线，同理存在f2使得f2(B)=0；找到了f1和f2之后，再在各自上找一点C和D使得CD得到的线性泛函也为支撑泛函（几何解释就是CD也为切线）得到的线路A-C-D-B为所求。相关理论的证明是已经没问题的，修读过泛函就没问题，因此你只需理解它的操作思想。

你说的没错！巴拿赫定理成立的条件是凸闭集，所以我用错了。不过还是值得像你那样考虑先求出凸闭包。迭代的思想我是这样认为的：
比如你有两个障碍物，你可以假设存在一点E在两个障碍物的凸闭包的公切线上，然后分别对AE，BE做前述操作。如果有n个时候我们先看看AB线段需要跨越哪些障碍物，然后排除掉其他干扰的，剩下的先做个从左到右排序吧，然后再在相邻两个之间像之前说的那样插入一个点（不过这里有两条公切线，所以到底是插在哪条上好，直接这样是判断不出来的，这要根据实际情况，要不就让计算机两条上都插再比较咯，但这样时间复杂度就大了些，暂时还没有想到好的判别标准）

Answer 2

光走的路线永远是最短路线 光反射 衍射 折射 当然折射需要穿越障碍物 所以我们只用反射和衍射 衍射的话是对于物质波来讲的 对于我们人类来说 除非速度达到奖金光速才能体现出物质波来 才能衍射 所以就免谈了
现在只剩下反射了 所以最短的路线就是反射 把你想象成光线 再看吧
不要把事情看得太严重咯 还变分法？ 变分法是什么啊 那个能用到这？你要无限分割？

Answer 3

我只能解决外绕的,内部穿来穿去解决不了.
连接AB,找出所有障碍离直线AB的最大距离,然后以这个障碍做切线且分别连接AB,如果中间穿过其他的障碍再用穿过的障碍和最大障碍以及A或B做切线

Answer 4

大佬，可以将两个切点之间的弧线连接吗？ 怎么联系您

Answer 5

高深啊，