m X n行または列で値の繰り返しがないサイズの行列が与えられた場合、サイクルを検出する効率的な方法はありますか?
たとえば、次のサンプル マトリックスがあります。
3 5 2 9 7 4
4 3 6 1 8 7
1 4 7 5 2 9
9 8 3 2 6 1
2 6 8 7 3 5
サイズ3の置換サイクルが少なくとも1つある：
3 5 2 9 7 4
4 8 3 1 6 7
1 4 7 5 2 9
9 6 8 2 3 1
2 3 6 7 8 5
行 2、4、および 5 の値 3、6、および 8 は、サイクルを形成します。
問題はカクロパズルに関するものです。それらを解決することとは関係ありませんが、特定のグリッドのレイアウトが不適切になるかどうかを検出しようとしています。行と列の合計は両方のレイアウトで同じであるため、並べ替えのサイクルはその特定のレイアウトを無効にします。
nxnグリッドの場合、O（n ^ 3）時間でこれを実行できると思います。
考え
グリッドの例を考えて、左上の 3 と 5 が最終的にラテン サブスクエアになるかどうかを仮定します。
(3) (5) 2 9 7 4
4 8 3 1 6 7
1 4 7 5 2 9
9 6 8 2 3 1
2 3 6 7 8 5
ラテン正方形が必要なため、(5) 列にその 3 (すべての値が各列に表示される必要があります) と、近くの 2 (正方形を形成する必要があります) を含める必要があります。
(3) (5) 2 9 7 4
4 8 3 1 6 7
1 4 7 5 2 9
9 6 8 2 3 1
(2) (3) 6 7 8 5
この含意をしばらく続けることはできますが、すぐに問題が発生します。左の行に 5 が含まれていません。左上の 3 と左上の 5 を含めると、矛盾が生じます。
一般に、同じ行または同じ列に 2 つの値を含めると、そのペアによって最大 4 つの他の値が強制的に含められたり、矛盾が暗示されたりします。この含意構造を使って、悪い解決策をすばやく排除し、良い解決策だけを残したいと考えています。
グラフを作成する
この有用な含意構造があるので、それを調査する必要があります。値の水平および垂直ペアごとにノードを作成し、ペアが別のペアを含める必要があることを意味する場合は常に、これらのノード間に有向エッジを挿入します。「矛盾」のノードもあります。たとえば、例{(0, 0), (0, 1)}の左上に対応するペアには、 、、および(3) (5)への出力エッジがあります。{(0, 0), (4, 0)}{(0, 1), (4, 1)}contradiction
その結果、多数のノードが矛盾を指し、場合によってはいくつかのノードが循環して互いに指し示すグラフが作成されます。矛盾ノードとそれを直接的または間接的に指すものをすべて取り除きます。残っているのはサイクルだけで、どのサイクルもラテン方陣に対応する必要があります。
正しさ
これが正しいかどうかは正直わかりません。追加された各ペアが必要なすべての作業を発生させるという意味で、ラテン方陣がすぐに徹底的に正確性をチェックされていないことは明らかです...しかし、見落とされるすべての悪いケースは、値が重複していて、これは、入力で発生しないことが保証されていました。
さらに作業が必要です。
複雑
行または列に O(n^2) ペア、および O(n) 行 + 列があるため、グラフには O(n^3) ノードがあります。各ノードには最大で 4 つのアウト エッジがあるため、O(n^3) エッジもあります。
エッジ リストを使用していると仮定すると、指しているオブジェクトを削除するcontradictionには、ノードの数に比例して時間がかかります。上流のインエッジに続いて、後方フラッド フィルを実行するだけです。
サイクルの検出には、ノードとエッジの数に比例する時間がかかります。アウトノードの数 (最大 4) に基づいてノードをバケットに入れ、ゼロアウト バケット内のノードを削除し、影響を受けるノードを再バケット化するまで続けます。終わり。残っているものがあれば、それはサイクルです。
すべての操作にはノードとエッジの数に比例する時間がかかり、O(n^3) 個のノードとエッジがあるため、アルゴリズム全体では O(n^3) 時間かかります。