如何连接两点而不经过另一条路径？

2018-06-03 03:28:06

假设我有以下网格。我必须连接字母对。不仅必须连接相同的字母，还必须确保连接路径不会相互交叉。有什么算法可以告诉我，如果可以连接所有的线对而不穿越路径和最短路径？

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

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

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

偶度平面图中不相交路径问题的一种近似算法 - Jonas Kleinberg（pdf）

链接地址: http://www.djcxy.com/p/10887.html

上一篇: How to connect two points without crossing another path?

下一篇: Replicate OpenSSL smime command on iPhone/Cocoa