4

部屋のセットで最小スパン回廊を見つけるアルゴリズムを実装しています。現在、私はアルゴリズムを理解しており、それを実装しようとしています。その一部には、特定の部屋のいわゆる「特別なポイント」を見つけることが含まれます。長方形の「特別な点」は、別の長方形の最も遠い点までの最小距離を持つ点です。例えば：ここに画像の説明を入力

部屋 R1 の特別なポイントは v6 または v7 になります。どちらも R1 以外の長方形の最も遠いポイントまでの最小距離が同じだからです。同様に、長方形 R8 の特別な点は v13 または v14 です。どちらも R8 以外の長方形の最も遠い点までの最小距離が同じだからです。現在、リスト内のすべての隣接ポイントを含む隣接リストでポイントを表しています。さらに、各境界点を値として持つ隣接リストにすべての部屋があります。また、それが属するすべての部屋にすべてのポイントがあります。

現在、その点の周りのすべての長方形の最も遠い点までの距離を見て、特別な点を計算しています。これは高速ですが、次の例では明らかに失敗しています。 ここに画像の説明を入力

私の現在の実装では、V1 と V2 を R9 の特別なポイントのタイとして識別しますが、V2 が特別なポイントであることは明らかです (V2 から R3 の最も遠いポイントまでの距離は、V1 から最も遠いポイントまでの距離よりも明らかに小さいため)。 R2で）。グラフ内のすべての長方形の最も遠い点までの距離を計算し、最小値を選択することで実装できますが、より効率的な方法があると感じています。私の考えでは、部屋を並べ替えて一部の部屋のみをチェックする方法について考えていますが、まだ完全なアルゴリズムはありません。何か案は？

前もって感謝します。

4

2 に答える 2

2

要約すると、変更された停止条件を使用して、ソース四角形のすべてのポイントからダイクストラのアルゴリズムを同時に実行することをお勧めします。アルゴリズムは、検索中にこれまでに見つかった現在の最小特別距離を追跡し、現在の最小特別距離よりもすでに離れているポイントをそれ以上検索しません。以下の疑似コードでは、ディクショナリを使用してターゲット ポイント => (最適距離、ソース ポイント) マッピングを格納します。

enqueue all points on source rectangle
special distance = infinity
while (queue not empty) {
    point = dequeue
    if (distance to point < best distance found to point AND 
        distance to point < special distance) {
        best distance found to point = distance to point
        rect = rectangle of point
        if (all points found in rect) {
            special distance to this rect = max(distances found to this rect)
            if (special distance to this rect < special distance) {
                special distance = special distance to this rect
            }
        } 
    }
}

以下の動機付けの詳細：

ダイクストラのアルゴリズムを実行して、ソース四角形の各ソース ポイントから一連のターゲット ポイントまでのすべてのポイントを見つけることができます。基本的に、ダイクストラのアルゴリズムは幅優先検索であり、ソース ポイントからそのポイントまでの最短パスであるという条件を満たしている場合にのみ、キューの先頭にあるポイントからさらに検索します。

この条件を使用すると、すべてのポイントへの最短パスが見つかります。次に、各ターゲット四角形の最長距離を計算し、これらの最小値、つまりそのソース ポイントの「特別な距離」を取得します (次に、ソース四角形のすべてのポイントに対して再実行し、最小の特別距離を見つけます)。ただし、ソース ポイントから遠く離れており、考慮する必要のない多くのポイントを検索に含めることになるため、これは非常に手間がかかります。

できることは、アルゴリズムの実行中に見つかった現在の最小特別距離を維持することです。これは、長方形のすべてのポイントを見つけたときにスポットし、それに応じて現在の最小特別距離を更新することによって行われます ( INT_MAXC ）。次に、ソース ポイントからの距離も現在の最小特別距離よりも小さくなければならないことを示すことによって、ポイントを前方に移動するための条件を拡張します (明らかに、現在のポイントが現在の最小特別距離よりも遠い場合は何もできません)。そこからつながるパスを検討することでより良い結果が得られます。)

四角形ごとに特別な点を見つけようとしている場合は、点のすべてのペア間の最短距離を計算するFloyd–Warshall アルゴリズムの実行を検討することをお勧めします。

于 2013-06-01T22:34:35.703 に答える
1

これは完全な答えではありません。「特別なポイント」の定義を確認/策定することを目的としています。

OPからの引用：

長方形の「特別な点」は、別の長方形の最も遠い点までの最小距離を持つ点です。

これが私の理解です。v*部屋の特別なポイントは次のrように与えられます。

ここに画像の説明を入力

どこ

  • V_r部屋の周りの頂点のセットですr
  • Rすべての部屋のセットです
  • D(v,v')指定された 2 つの頂点間の距離

したがって、次のことがわかります。

  • 宛先頂点v'は、からできるだけ遠くにあるように選択されますv
  • ただし、距離を最小限に抑えるために選択されたv'目的地の部屋の中にいる必要がありますr'

私がこの定義からそれほど離れていなければ、v*(r)ネストされたループを 3 つだけ使用してブルート フォース検索を実行できるはずです。

もちろん、より効率的な方法に興味があります。ただし、最初に「特別なポイント」を正しく理解していることを確認してください。

于 2013-06-02T15:43:53.277 に答える