13

目標を簡潔に説明する方法がわかりません。これが、十分な検索にもかかわらず適用可能なアルゴリズムを見つけることができなかった理由かもしれませんが、画像はそれを明確に示しています。

連動アイテム

左側のグリッド内のアイテムの状態を考えると、右側のグリッドに示されている終了位置を効率的に見つけるアルゴリズムを知っている人はいますか? この場合、すべてのアイテムが「落ちた」「落ちた」のですが、もちろん方向は任意です。要点は次のとおりです。

  • 任意の形状のアイテムの集まりがありますが、すべて連続した正方形で構成されています
  • アイテムは重複できません
  • すべてのアイテムは、壁に触れるまで、または[...別のアイテムに無限に触れている...]壁に触れている別のアイテムに触れるまで、指定された方向に最大距離移動する必要があります。

これは宿題ではありません。私は学生ではありません。これは、幾何学とプログラミングに対する私自身の興味のためです。それは問題ではないので、私は言語について言及していません。取り組んでいる特定のプロジェクトに使用している言語で、どんなアルゴリズムでも実装できます。有用な答えは、言葉またはコードで説明できます。重要なのはアイデアです。

この問題は、依存関係とスラック スペースのある種のグラフ (数学的な意味で) に抽象化される可能性があるため、ラグ タイムを最小限に抑えることを目的としたアルゴリズムを適応させることができます。

答えがわからないが、その場でアルゴリズムを作成しようとしている場合は、連動するピンク (後方) の「C」と青色の「T」の形など、循環依存関係が存在する可能性があることを覚えておいてください。T の部分は C の下にあり、C の部分は T の下にあります。連動するアイテムが複数のピースの「ループ」によってロックされている場合、これはさらに厄介です。

適用可能なアルゴリズムに関するいくつかの注意事項: グリッド オブジェクト管理フレームワークを構築した方法により、以下のすべてが非常に簡単かつ迅速に実行できます。

  • ピース内の個々の正方形を列挙する
  • すべてのピースを列挙する
  • グリッド全体で特定の正方形を占めるピースがある場合はそれを見つけます

答えに関するメモ: maniek が最初にそれをほのめかしましたが、bloops が素晴らしい説明を提供してくれました。絶対的な鍵は、同じ量を移動するすべてのピースが互いに関係を維持しているという洞察であり、したがって、それらの関係を考慮する必要はないと思います.

人口がまばらなボードの追加のスピードアップは、すべてのピースをシフトして、完全に空の行を排除することです。空の行を数えて、空の行の片側 (「上」) にあるピースを識別するのは非常に簡単です。

最後のメモ:私は実際に bloops で記述されたアルゴリズムを実装しましたが、実装固有の変更がいくつかありました。美しく機能します。

4

5 に答える 5

10

アイデア

凍結されたオブジェクトのセットを次のように帰納的に定義します。

  • 底に触れている物体は凍っています。

  • 凍結されたオブジェクトの上にあるオブジェクトは凍結されます。

直感的に、凍結されたオブジェクトは最終的な場所に到達しました。凍結されていないオブジェクトをアクティブと呼びます。

主張：すべてのアクティブなオブジェクトは、同時に1ユニット下に落ちることができます。

証明：もちろん、アクティブオブジェクトは、互いに対する相対的な位置が変わらないため、別のアクティブオブジェクトにぶつかることはありません。アクティブオブジェクトは、フリーズされたオブジェクトにもヒットしません。そうであれば、アクティブオブジェクトは実際にはフリーズされていました。これは、フリーズされたオブジェクトの上にあるためです。これは私たちの仮定と矛盾します。

私たちのアルゴリズムの非常に高レベルの擬似コードは次のようになります。

while (there are active objects):
    move active objects downwards simultaneously until one of them hits a frozen object
    update the status (active/frozen) of each object

whileループの各反復で少なくとも1つのオブジェクトがフリーズすることに注意してください。また、すべてのオブジェクトが1回だけフリーズします。これらの観察結果は、実際のアルゴリズムの実行時の複雑さを分析するときに使用されます。

アルゴリズム

時間の概念を使用して、ほとんどの操作の効率を向上させます。時間は0から測定され、アクティブオブジェクトのすべての単位移動には1単位時間がかかります。時間にいるときt、時間に現在アクティブになっているすべてのオブジェクトの変位は、t正確にt下向きの単位であることに注意してください。

各列では、各セルの相対的な順序が固定されていることに注意してください。これが意味することの1つは、各セルが最大で1つの他のセルの落下を直接停止できることです。この観察結果は、次の衝突の時間を効率的に予測するために使用できます。また、すべてのセルを最大で1回「処理」することもできます。

1から始まり、左から右に向かって増加する列にインデックスを付けます。実装を容易にするために、bottom-という新しいオブジェクトを導入します。これは、最初にフリーズされ、高さ0のすべてのセルで構成される唯一のオブジェクトです。

データ構造 効率的な実装のために、次のデータ構造を維持しています。

  • A各セルの最終変位を含む連想配列。セルがアクティブな場合、そのエントリは、たとえば、である必要があります-1。

  • 列ごとに、列内のアクティブセルの初期行番号のkセットを維持します。このセットに対する後続のクエリと削除をサポートできる必要があります。Van Emde Boasツリーを使用して、 ;のすべてのクエリに答えることができます。ここで、はグリッドの高さです。または、これらの操作を;で実行できる平衡二分探索木を使用することもできます。ここで、は列のセルの数です。S_kkO(log log H)HO(log N)Nk

  • Q将来の衝突の予想時間として、アクティブセルとそのキーを格納する優先キュー。繰り返しになりますが、クエリ時間のvEBツリー、または操作ごとの時間O(log log H)の優先キューのいずれかを選択できます。O(log N)

実装

アルゴリズムの詳細な擬似コードは次のとおりです。

Populate the S_k's with active cells
Initialize Q to be an empty priority queue

For every cell b in bottom:
    Push Q[b] = 0

while (Q is not empty):
    (x,t) = Q.extract_min()     // the active cell x collides at time t
    Object O = parent_object(x)
    For every cell y in O:
        A[y] = t                // freeze cell y at displacement t
        k = column(y)           
        S_k.delete(y)
        a = S_k.successor(y)    // find the only active cell that can collide with y
        if(a != nil):
            // find the expected time of the collision between a and y
            // note that both their positions are currently t + (their original height) 
            coll_t = t + height(a) - height(y) - 1
            Push/update Q[a] = coll_t

オブジェクトの最終的な位置は、Aそのオブジェクトに属するセルの変位を照会することで取得できます。

実行時間

すべての細胞を1回だけ処理して凍結します。すべてのセルをフリーズしながら、一定数のルックアップを実行します。parent_objectルックアップは一定時間で実行できると想定しています。アルゴリズム全体の複雑さは、O(N log N)使用O(N log log H)するデータ構造によって異なります。ここで、Nはすべてのオブジェクトにわたるセルの総数です。

于 2012-07-10T12:05:26.127 に答える
6

そして今、完全に異なる何か:)

地面に置かれている各ピースは固定されています。固定されたピースの上にある各ピースは固定されています。残りは動くことができます。固定されていない部分を1マス下に移動し、何も移動できなくなるまで繰り返します。

于 2012-07-10T11:01:47.690 に答える
3

さて、これは次のように見えます-

  • ステップに進みます
  • 各ステップで、頂点がオブジェクトセットであり、エッジが次のような有向グラフを作成します=>

1）xとyが2つのオブジェクトである場合、yが移動するまでxが移動できない場合は、エッジx->yを追加します。x->yとy->xの両方のエッジを持つことができることに注意してください。

2）さらに、下部にあるため移動できなくなったオブジェクトがあるため、頂点を青色で色付けします。残りの頂点は赤です。

2）有向グラフでは、コサラジュのアルゴリズム/タージャンのアルゴリズムなどを使用して、すべての強連結成分を見つけます（SCCに慣れていない場合は、非常に強力な手法であり、コサラジュのアルゴリズムを参照できます）。SCCを取得したらそれらを小さな頂点に縮小します。つまり、すべての外部（SCCへの）エッジを保持しながら、SCCを単一の頂点に置き換えます。ここで、SCCの頂点のいずれかが青の場合は、新しい頂点を青に色付けし、そうでない場合は赤に色付けします。これは、1つのオブジェクトがSCCで移動できない場合、誰も移動できないことを意味します。

3）取得するグラフは有向非巡回グラフになり、トポロジカルソートを実行できます。頂点を一番上の番号の昇順でトラバースし、赤い色の頂点が表示されている限り、頂点によって表されるオブジェクトを移動します。

手順3で頂点を移動できなくなるまで、この手順を続けます。

2つのオブジェクトAとBが重なっている場合、それらは互いに一貫性がないと言います。正しさを証明するために、次の見出語を主張します1）「SCCを移動した場合、その中のオブジェクトはどれもそれらの間で矛盾を引き起こしません。」2）「ステップ3でオブジェクトを移動すると、不整合が発生しません」

ここでの課題は、正当性を正式に証明し、それを効率的に解決するための適切なデータ構造を見つけることです。ヘルプが必要な場合はお知らせください。

于 2012-07-10T04:24:43.390 に答える
2

数回編集。私はこれがあなたがする必要があるすべてだと思います：

  1. 互いに依存し合うことしかできないピースをすべて見つけて、それらを結合して同等の大きなピースにします (例: 写真のTと 後方C)。

  2. すべてのピースを反復処理し、何かにぶつかる前に最大方向に移動します。何も動かなくなるまで繰り返します。

于 2012-07-09T23:30:19.373 に答える