找出两点之间的最短距离，并有分段阻挡。

Question

我需要找到端点之间的最短欧氏距离。A, B 在平面上，受制于有一组N个段子 S=[S1,S2,...] 我的欧几里得路径不能相交。

我可以想象一个递归的方法，首先 "猜测 "出在 A,B，并检查是否有任何交叉点，与一段 s，改变路径绕行 s，然后在新的端点上递归调用同样的算法。这似乎有O(2^N)的运行时间，因为有2种方法可以绕过每一段。

这是我正在研究的旅行推销员问题的一个子问题。

编辑：如果两段共用一个端点，这个点是可以通过的。

Answer 1

构造一个图 G 其顶点是 A, B 和 2N 段的端点。 如果且仅当两点之间的直线不与任何其他边相交时，才用一条边连接两点。

现在使用 A*搜索 来寻找最短路径。