algorithm - ポイントのセットが与えられた場合、グリッドによく知られたアルゴリズムの塗りつぶしがありますか?

Question

ここでこのゲームを見ましたFlow、かなり面白そうです。

お揃いの色をパイプでつなげて流れを作ります。すべての色を組み合わせてボード全体を覆い、各パズルを解いてください。ただし、パイプが交差したり重なったりすると、パイプが破損することに注意してください。

ペアのセットが与えられた場合(x, y)、パズルを解くためのアルゴリズムはありますか、つまり、私が知らないグリッド全体 (解決策があると仮定) を埋めますか?

Answer 1

これは、グローバルルーティングの問題の非常に特殊な例です。グローバルルーティングは、VLSI CAD（集積回路内で数百万のネットをルーティングする必要がある）でよく研究されている問題です。問題はNP完全であり、実行時と品質の間で必要なトレードオフに応じて、さまざまな方法で解決できます。次のウィキは良い出発点です：

http://en.wikipedia.org/wiki/Routing_(electronic_design_automation）

ここでの論文は、さまざまな手法の調査を提供します。

http://dropzone.tamu.edu/~jhu/publications/HuIntegration01.pdf

私が与えたポインタは、通常、あなたが述べた問題のはるかに複雑なバージョンを解決しようとしていることを覚えておいてください。それにもかかわらず、数学的概念は同じままです。