7

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

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

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

1 回答 1

3

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

于 2012-06-25T07:15:30.787 回答