如何连接两个点而不交叉另一条路径？

Question

让我们假设我有下面的网格。我必须连接成对的字母。不仅相同的字母必须连接，而且我还必须确保连接的路径不相互交叉。有什么算法可以告诉我，如果不需要交叉路径和最短路径，就可以连接所有对？

我意识到这是一个图问题，最短路径部分可以用BFS来解决。我不确定的是交叉路。

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

Answer 1

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

• An Approximation Algorithm for the Disjoint Paths Problem in Even-Degree Planar Graphs - Jonas Kleinberg (pdf)