4

NxNルームとして組織された博物館があります。一部の部屋は施錠され、アクセスできません。他の部屋は開いていて、警備員がいる部屋もあります。警備員は東西南北にのみ移動でき、開いた部屋と博物館内でのみ移動できます。各部屋について、警備員までの最短距離を見つけます。アルゴリズムの時間計算量は?

4

8 に答える 8

3

まず、比較的単純なアプローチを検討してください。

各ガード G を一連の部屋の頂点として使用すると、R=N*N となり、隣接する部屋 (エッジ) 間の可能なパス E.

すべての部屋の最小距離を知る必要がある場合は、各警備員から各部屋までの BFS。

これには 、または のような時間がかかるはずG * (R+E)です。G*(N*N+E)G*(N*N)

これは、各 BFS が既に完了したサブツリーを繰り返し計算するため、メモ化によって確実に最適化できます。部屋の構成によっては、上記の時間の複雑さから G を大幅に削減できます。しかし、これよりも優れたものがあるに違いないと確信しています。

于 2010-07-24T21:27:00.313 に答える
2

グラフィカルなソリューション 各部屋はノードです ドアが開いている部屋の間にのみエッジがあります Floyd-Warshall アルゴリズムを使用してから、各部屋と各警備員の間の最小距離を確認します

部屋数 - R = N^2

ガードの数 - G

時間計算量は O(R^3 +R*G)= O(R^3) = O(N^6) です。

Floyd–Warshall の R^3

于 2010-07-24T21:32:32.887 に答える
2

IVladとthrowawayacctによって言及された最適解 ( O(N^2) ) の概要を次に示します。何らかの理由で彼らの声が聞こえません:)

NxN グリッドは、ノードが部屋を表し、エッジが隣接する部屋間のドアを表すグラフであると考えてください。すべてのエッジの重みは 1 です。一連のノード U は、「保護された部屋」としてマークされます。

アイデアは、すべての保護された部屋に接続された新しいノードから開始し、v0 からの距離が増加する順序で部屋をスキャンする BFS トラバーサルを使用することです。ノードが訪問されるたびに、それに到達するために行われたステップの数は、保護された部屋からの距離を表し、パス展開順序により最小であることが保証されます。

Add an artificial node v0 and connect it to all nodes in U
Create a simple queue Q, that stores pairs <node, dist>
Q.enqueue(<v0, -1>) 
Create a hash set S, that contains all visited nodes
S.add(v0)
while not Q.isEmpty() {
    pathTail := Q.dequeue()
    output distance pathTail.dist for node pathTail.node
    for all neighbours v of pathTail.node
        if not S.contains(v)
            Q.add(<v, pathTail.dist + 1>)

    S.add(pathTail.node)

}

複雑さの分析

グラフは平面であるため、|V|+|E|=O(|V|) であることに注意してください。したがって、この BFS は O(|V|)=O(N^2) 時間で実行されます。

エッジの重みが均一であるという事実は、物事を単純にします。キューは単調な距離値を持つことが保証されています。たとえば、ダイクストラでは、エッジの重みが異なる可能性があるため、優先キューが必要であり、これは時間の複雑さに影響します。ここで示したのと同じ問題で、部屋ごとに重みが異なると、O(N N log N) の時間が必要になります。

于 2010-07-25T09:58:23.497 に答える
2

人工ソースとソースから各ガードまでの長さゼロのエッジでミュージアム グラフを拡張すると、時間Õ(n 2 + g )は、各部屋から最も近い警備員までの距離を示します。

于 2010-07-25T02:22:52.277 に答える
0

その博物館を 1 つのグラフとして見て、Dijikstra アルゴリズムを使用するだけです。

ウィキリンク

特定のページで複雑さについて議論しています。

于 2010-07-24T21:24:52.903 に答える
0

この一連の投稿で実装されたダイクストラの最短パス アルゴリズムを見つけることができます。

幅と深さの最初の検索

于 2010-07-24T21:25:31.640 に答える
0

部屋 i から部屋 j への遷移のコストを返す関数 edgeCost(i,j) を想定しています (何もない場合は無限、それ以外の場合は 1)。また、edgeCost(i,i) = 0 であり、負のサイクルはありません。R を部屋の数とします (この場合は R = N^2):

int path[R][R];
/*
 * Each path[i][j] is initialized to
 * edgeCost(i,j) or infinity if there is no 
 * edge between i and j.
 */

function play():
 for k = 1 to R:
  for i = 1 to R:
   for j = 1 to R:
    path[i][j] = min(path[i][j], path[i][k] + path[k][j]);

または、ご存じかもしれませんが、O(|R|^3) 時間の計算量を持つ Floyd-Warshall アルゴリズム (すべてのペアの最短パス)。

于 2010-07-24T21:47:35.920 に答える
0

各エントリが整数とともに 1 つの正方形のアドレスを保持するキューを用意します。すべての警備員の場所をキューに入れ、それぞれに整数 "0" のタグを付けます。すべての正方形には数字を入れるスペースが必要で、最初はすべて空白にする必要があります。

次に、キューに何かがある限り、キューからエントリを引き出し、問題の正方形にマークされた値があるかどうかを確認します。その場合は、そのキュー エントリを無視して、次のエントリに進みます。それ以外の場合は、正方形をキューからの値でマークし、直接到達可能なすべての隣接する正方形を、現在の現在のエントリの値よりも 1 大きい値でキューに入れます (正方形の最初のバッチのそれぞれがキューから引き出されるように、それらは値「1」を取得します）。空白の場合、各マスは 1 回だけ訪問され、訪問された各マスは、最大で 4 つの追加のマスがキューに入れられるため、キューを通過するアイテムの総数は、マスの数の 4 倍に警備員の数を加えたものになります。 . この値は、キューに追加する前に各正方形をチェックして空白かどうかを確認することにより、一定の係数で簡単に減らすことができます。これにより、冗長なキューイングがすべてなくなるわけではありませんが、一部は解消されます。

于 2010-07-25T02:29:16.723 に答える