如何连接两个点而不穿过另一个路径？

Question

我们假装我有以下网格.我必须连接成对的字母.不仅必须连接相同的字母,而且还必须确保连接路径不会相互交叉.什么算法可以告诉我是否可以连接所有对而没有交叉路径和最短路径？

我意识到这是一个图形问题,可以使用BFS解决最短路径部分.我不确定的是过路.

  +---+---+---+---+---+---+---+---+
  | A |   |   | B |   |   |   |   |
  +-------------------------------+
  |   |   |   |   |   |   |   |   |
  +-------------------------------+
  |   |   | B |   |   |   | D |   |
  +-------------------------------+
  |   |   |   |   |   |   |   |   |
  +-------------------------------+
  |   | C |   |   | C |   |   |   |
  +-------------------------------+
  |   |   |   | A |   |   |   |   |
  +-------------------------------+
  |   |   |   |   |   |   | D |   |
  +-------------------------------+
  |   |   |   |   |   |   |   |   |
  +---+---+---+---+---+---+---+---+

Answer 1

这是一个 NP 完全问题，称为“不相交连接路径”。除了一些超多项式算法（非常慢）之外，还有一些近似算法（可能会出错，或者不是最优的）。

• 偶数度平面图中不相交路径问题的近似算法 - Jonas Kleinberg (pdf)