2


3

私は、 "ON"と "OFF"の2つの状態を持つ正方形のグリッドを使って作業しています。私はすべての "ON"コンポーネントを見つけるかなり単純な Connected Component Labelingアルゴリズムを持っています。 常にではありませんが、通常は1つの「ON」コンポーネントがあります。

on / offセルの行列、コンポーネントラベリング(おそらくセルのハッシュセットのリストとしてフォーマットされている)、およびラベリングが形成されてから変更されたセルのリストを入力として取り込むアルゴリズムを構築して出力します新しいラベル 明らかな解決策は、最初から再計算することですが、これは効率的ではありません。 一般に、変更されたセルのリストは少なくなります。

チェンジリストがオンになっているセルのみである場合、これは簡単です。

グループG;各セルはセルCを変更しました。グループU =空のグループ。 add(C); Gの各グループSを予測します。(SにCに隣接するセルが含まれている場合)G.削除(S); U.UnionWith(S); G.add(C); G.

しかし、変更に無効になったセルが含まれていると、どうすればよいかわかりません。 すべてのONセルは厳密に1つのグループのメンバーでなければならないことに留意してください。 したがって、1つの解決策は、新たにオフになったセルに隣接している各セルを取り出してそれらが互いに接続されているかどうかを確認することである(例えば、特許文献1参照)。 * pathfindingを使用します。 これにより、1〜4個の連続したグループが生成されます(セルがそのグループ内で唯一のセルであり、したがってチェックする隣接セルが0個でない場合、その場合は0個のグループが生成されます)。 ただし、通常(常にではありません)これらの隣接する正方形をつなぐのは、隣接するグループを見つけるのと同じくらい難しいので(これを行うための賢明な方法を提案しているのでない限り)。 また、変更されたセルがたくさんある場合は、やることが少し怖いです。

私がこれをしている理由を知ることを主張する人たちのための文脈: Nurikabeパズルの1つの規則はあなたが1つの連続した壁のグループを持つことができるということです。 私がスピードを上げるために(そしてパスファインディングで遊ぶために)解決しようとしている問題の単純化は上にあります。 基本的に、私は以前のそのようなテストから得られた情報を無駄にせずに連続した壁をチェックしたいです。 O(f(Δ))がO(f(Δ))の場合、O(f(N))アルゴリズムを使用するのはちょっと面倒なので、速度を向上させるためにソルバーの前の情報を利用できる場所を確認しますアルゴリズムで十分です(Nはパズルのサイズ、Δはアルゴリズムが最後に実行されてからの変更です)。

プロファイリング_does_は、このアルゴリズムを改善すると実行時間が変わることを示していますが、これは利益よりもむしろ楽しみのためのプロジェクトです。

注意:現在のアルゴリズムの説明は省略しましたが、基本的には、最初に見つかったON正方形に対してスタックベースの Flood Fillアルゴリズムを実行して確認します。それ以上のON四角形がある場合(これは複数のグループがあることを意味しますが、調べてもかまいません)。

改良:Yairchu氏とJohn Kugelman氏の提案は、この問題を解決するものではありませんが、コードのこの部分やその他のコードを高速に実行するためのものです。

電流ループ

foreach(四角形のm.Neighbors [tmp.X] [tmp.Y]){if(0!=((byte)(s.RoomType))

改善のアイデア:

foreach(平方平方m.NeighborsXX [tmp.X] [tmp.Y]){if(Retval.Add(s))curStack.Push(s); }

これはいくつかのm.NeighborsXXインスタンスを維持することを必要とし(強化される必要があるそれぞれのタイプのマッチに対して1つ)、そして正方形が変わるたびにそれらすべてを更新します。 実際に役立ったかどうかを確認するには、これをベンチマークする必要がありますが、ある程度の速度でメモリを交換する標準的なケースのように見えます。

3 回答


1


完全な解決策ではありませんが、ここに行きます:

  • 接続された各コンポーネントに対して、スパニングツリーをメモリに保存します** TreeプロパティA:私たちのスパニングツリーは、どのノードがどのノードの「上」にあるかという概念を持っています(検索ツリーのように)。 どちらを選択するかは任意です

  • エッジの削除と追加について説明しましょう

  • エッジを追加する場合: 2つのノードが同じコンポーネント内にあるかどうか、それらのツリーのルートが同じかどうかをチェックします。 同じグループに属している場合は何もしません異なるグループに属している場合は、新しいエッジでツリーを結合します。 **これは私達の新しい端がそれの上にあることができるように木の一つの "形"(だれが誰より上にあるかの定義)を変換することを必要とするでしょう

  • エッジを削除するとき:このエッジがグループのスパニングツリーに参加していない場合は何もしません。 接続している場合は、グループがまだ接続されているかどうかを確認する必要があります。あるグループから別のグループにアクセスしようとします。 2つのうち小さい方から実行します。ツリー内の各ノードについて、そのサブツリーのサイズを維持します。**プロパティCを使用すると、両方のグループのサイズを判断できます。*プロパティBのため、通常、小さいグループは非常に小さく、大きいグループは非常に小さくなります。 large *グループが接続されている場合は、接続エッジを追加した場合と同じように動作します。*グループが接続されていない場合は、プロパティCを維持するためにツリーに上る必要があります。 'サブツリーサイズ)

  • 問題:どのようにして特性Bを維持しますか(木は密です)。

これが理にかなっていると思います:)


1


これはGo(日本ではIgo)のゲームで石の接続された文字列を計算する(グリッド上の4コネクティビティを仮定する)のと同じ問題であり、それを漸増的に行うことは高性能Goプレイアルゴリズムの1つの鍵です。

そうは言っても、この分野では、1つのグリッド要素をオンにしたとき(ボードに石を追加したとき)にも簡単なケースがあります。 問題となるのは、1つのグリッド要素をオフにしたとき(アルゴリズムの元に戻すために石を削除したとき)、1つのコンポーネントが2つの接続されていないコンポーネントに分割されることです。

この問題についての私の限られた理解に基づいて、ラベル付きグループをマージするために要素をONにするときはunion-findを使用し、グリッド要素をOFFにするときは関連するグループを最初から再計算することをお勧めします。 これを最適化するために、グリッド要素のオンとオフの両方をオンにするときはいつでも、最初にオフケースを処理し、共用体検索操作が無駄にならないようにします。 より高度なインクリメンタルアルゴリズムを使用したい場合は、要素ごとにインクリメンタル接続性データを維持し始めることができますが、ほとんどの場合は効果がありません。


0


面白い問題です。 これが私の最初の考えです。 うまくいけば私はもっと持っているでしょうし、彼らが来たらこの答えを更新するでしょう…​

  • [更新2] * 1つのグループしか気にしないので、A *検索は理想的です。 A *検索をプロファイルしましたか。 再ラベル? 私はよく書かれたA *検索が洪水盛り土よりも速いだろうと考えなければなりません。 そうでない場合は、最適化のために実際のコードを投稿することができますか?

  • [更新1] *新しくオフになったセル `+ C `がグループ ` G `にあることがわかっている場合、CCLアルゴリズムを再実行できますが、グループ ` G +`のセルにラベルを付けるだけです。 他のONセルは既存のラベルを保持できます。 グリッド全体の残りの部分を調べる必要はありません。これは、グリッド全体の初期CCLと比較して大幅な節約になる可能性があります。 (熱心なNurikabe解決者として、これは解決されたパズルで少なくとも33%の節約になり、進行中のパズルでは非常に大きな節約になるはずです。 私の推測では「33%」となっていますが、解決済みのパズルは黒が2/3、白が1/3です。

これを行うには、各グループに含まれるセルのリストを保存して、グループ「+ G +」のセルをすばやく繰り返し、それらのセルのみに再ラベル付けできるようにする必要があります。