8

私は最近よく考えていたコンピュータ サイエンスの問題を抱えており、他の人のフィードバックを聞きたいと思っています。

3D ブロックワールド (Minecraft など) があるとします。任意のブロックについて、そのブロックからブロックの一番下の行への確実なパスが存在する場合、その世界は「安定」しています。世界が生成されたとき、それは安定していることが保証されていますが、プレイヤーがブロックを掘り起こしていると、世界が不安定になる可能性があります. たとえば、プレイヤーは木の幹を掘り出すことができます。その場合、木のてっぺんが空中に浮かんでいるため、世界が不安定になります。

目標は、掘削の結果として世界が不安定になるかどうか、および世界を安定した状態に戻すためにどのキューブを削除する必要があるかをすばやく把握することです。アルゴリズムは高速であり、多くの発掘が行われている世界のコンテキストで機能する必要があります。そのほとんどは世界を不安定にするものではありません。

単純なアプローチの 1 つは、掘削後に隣接する各キューブを取り、地底への道を見つけることです。隣人から底への道が見つからない場合、世界は不安定です (また、プロセスの一部としてどのキューブを削除するかを学習します)。底への道が非常に長い場合、これは崩壊します。これが計算コストが高くなる例を思いつくのは非常に簡単です (大きな曲がりくねった塔の上部を取り除くことを想像してください)。

この問題は、1 つの頂点がグラフを 2 つ以上のコンポーネントに分割できるかどうかをすばやく検出するグラフの問題と考えることができます。

この問題を扱いやすくする方法について他のアイデアを持っている人がいるかどうかを知りたいです。

4

5 に答える 5

5

リンク/カットツリーが役立つ場合があります。 その構造の著者の1 人であるDaniel Sleatorは、同様の問題に対する彼の解決策を共有しました。codeforces.ruに関する彼のコメントを見てください。役に立つかもしれません。

ここに私の考えを書きます。一番下のレベルの下に 1 つの頂点を作成しましょう。この頂点は、建物の地下です。basement_vertex を最下層のすべての頂点に接続します。地下頂点から深さ優先探索 (DFS) を実行します。この dfs は根付きツリーを生成します。このツリーは、何らかのリンク カット ツリーのベース (初期段階) である必要があります。

アップデート

Link-Cut Trees は、与えられたグラフがツリーである場合にのみ機能します。どのグラフでも、動的接続の問題を解決する必要があり ます。 動的接続の問題に関する詳細はこちら。

于 2013-08-07T03:32:56.223 に答える
1

各ブロックが「unstable-if-dug」( cut-vertexまたはbiconnected componentとも呼ばれる) である場合、保存を検討します。その後、クリックすると一定時間で検索できます。

基本的には、安定しているかどうかをすぐに知ることができるという考えです。次に、次のユーザー入力を待っている間にグラフを再計算します。ユーザー エクスペリエンスはよりスムーズになり、クリックが非常に速くならない限り、速度の低下に気付くことはありません。

DFS を使用すると、グラフのすべてのカット頂点を O(n) 時間で見つけることができます。

二重接続コンポーネントに関するウィキペディアから:

アイデアは、次の情報を維持しながら深さ優先検索を実行することです。

  • 深さ優先探索ツリーの各頂点の深さ (アクセスされた後)
  • 各頂点 v について、深さ優先探索ツリー内の v のすべての子孫の近傍の最低深さであり、ローポイントと呼ばれます。

v の低点は、 v のすべての子孫を訪問した後に計算できます ... の最小値として:

  • v の深さ
  • v のすべての近傍の深さ (深さ優先探索ツリーの v の親の横)
  • 深さ優先探索ツリーの v のすべての子の低点。

重要な事実は、非ルート頂点 v は、そのようなの子yがある場合にのみ、2 つの二重接続されたコンポーネントを分離するカット頂点 (または関節点) であるということです。vlowpoint(y) ≥ depth(v)

ルート頂点は個別に処理する必要があります。少なくとも 2 つの子がある場合にのみ、ルート頂点がカット頂点になります。

于 2013-08-07T21:09:27.760 に答える
0

Flood-fillノードにラベルを付けて、メンバーシップが同じかどうかを確認する、いわゆるアルゴリズムを検討できます。

これが簡単なグラフです。元のグラフ G があり、それぞれ 1 つの立方体を削除してグラフ H と I を取得します。

ここに画像の説明を入力

このigraphパッケージは、グラフの接続性をテストするのに最適です。上記のテスト例では、G と H は問題ありませんが、エッジ (3,5) を削除すると、5、6、7 のメンバーシップがノード 1 (「アース ノード」) のメンバーシップとは異なります。(したがって、3 番目のグラフであるグラフ I では、立方体 5、6、および 7 を削除する必要があります。)

R 言語では igraph ライブラリを使用

library(igraph)
edges <- c(c(1,2), c(2,3), c(2,4), c(3,5), c(5,6), c(5,7), c(6,7))
g<- graph(edges, directed=FALSE)
clusters(g)$membership  # 1 1 1 1 1 1 1

edges <- c(c(1,2), c(2,3), c(2,4), c(3,5), c(5,6), c(5,7)) # drop edge(6,7)
h<- graph(edges, directed=FALSE)
clusters(h)$membership # 1 1 1 1 1 1 1


edges <- c(c(1,2), c(2,3), c(2,4), c(5,6), c(5,7), c(6,7)) # drop (3,5)
i<- graph(edges, directed=FALSE)
clusters(i)$membership # 1 1 1 1 2 2 2

clustersigraph パ​​ッケージに付属の関数です。そのmembership値は、グラフ内の各ノードのラベルを示しています。いずれかのノード (この場合はキューブ) のメンバーシップ値が「アース ノード」とは異なる場合、それは地面に接続されていないため、削除する必要があります。

于 2013-08-07T04:23:33.510 に答える
0

簡単な解決策の 1 つは、BFS (幅優先探索) を使用して、削除されたノード (マインクラフト ブロック) のすべての隣接ノードが同じ接続コンポーネントに属しているかどうかを確認することです。

最初のネイバーにラベルが付けられ、他のすべてのネイバーがラベル付きノードに接続されているかどうかがチェックされます。

テストしたコード (C#) は次のとおりです。

public bool CanRemoveNode(int indexNode)
{
    var initialNeighbors = this.nodeNeighbors[indexNode];

    if (initialNeighbors.Count() < 2)
    {
        // leaf node - can be safely removed
        return true;
    }

    HashSet<int> nodesComponent = new HashSet<int>(initialNeighbors.Take(1));
    HashSet<int> nodesProcessed = new HashSet<int>();
    Queue<int> nodesVisit = new Queue<int>();

    foreach (int indexNodeStart in initialNeighbors.Skip(1))
    {
        nodesProcessed.Clear();

        nodesVisit.Clear();
        nodesVisit.Enqueue(indexNodeStart);

        while (nodesVisit.Any())
        {
            int indexNodeCurrent = nodesVisit.Dequeue();

            nodesProcessed.Add(indexNodeCurrent);
            nodesComponent.Add(indexNodeCurrent);

            foreach (int indexNodeNeighbor in this.nodeNeighbors[indexNodeCurrent])
            {
                    if (indexNodeNeighbor == indexNode)
                    {
                        // do not inspect removed node
                        continue;
                    }

                    if (nodesProcessed.Contains(indexNodeNeighbor))
                    {
                        // neighbor node already processed
                        continue;
                    }

                    if (nodesComponent.Contains(indexNodeNeighbor))
                    {
                        // neighbor node belongs to the component - we can terminate search
                        goto NextStartNode;
                    }

                    // mark neighbor node for further inspection
                    nodesVisit.Enqueue(indexNodeNeighbor);
            }
        }

        return false;

        NextStartNode:
        ;
    }

    return true;
}

「nodeNeighbors」ディクショナリには、各ノードの隣接インデックスが含まれています。

最悪のシナリオでは、隣接する 2 つのノード間の最長パスの長さと同じ数の BFS 反復を実行する必要があります。

より高速な方法は、一意の数値ラベルを使用して各直近にラベルを付けてから、連結成分のラベル付けを実行することです。各ラベルに対して並列 BFS 検索を実行し、2 つのラベルが一致するたびに終了し、基になる Union-Find 構造で Union 操作を実行できます。

初期ラベルから 1 を引いた数のユニオン操作が実行されると、検索全体が終了する可能性があります。つまり、すべてのラベルが同じコンポーネントに属します。

もう 1 つの速度向上は、複数の「シード」を除去ポイントの周囲に均一に分散させることです。各シードは、一意のラベルを持つノードです。これにより、コンポーネントがより早く 1 つに接続されることが保証されます。

また、反復回数 (10,000 回など) 後に検索を終了することもできます。これは、立方体が非常に長い距離で接続されていることを意味し、プレーヤーは切断があることにさえ気付かないためです。

この時点以降、バックグラウンドで検索を実行することもできます。

于 2016-07-13T11:36:21.703 に答える