7

次のグリッドがあるとしましょう。文字のペアを接続する必要があります。同じ文字をつなげるだけでなく、つなぐパスが交差しないようにする必要があります。パスと最短パスを交差させずにすべてのペアを接続できるかどうかを教えてくれるアルゴリズムは何ですか?

これはグラフの問題であり、最短経路の部分は BFS を使用して解決できることがわかりました。私がよくわからないのは、交差点です。

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

1 に答える 1

3

これは「Disjoint Connecting Paths」と呼ばれる NP 完全問題です。いくつかの超多項式アルゴリズム (非常に遅い) 以外に、いくつかの近似アルゴリズムがあります (間違いを犯したり、最適ではない可能性があります)。

于 2012-06-25T07:15:30.787 に答える