4

状況

単位正方形 [0, 1]x[0, 1] 上のn 個の点と正の実数rが与えられたとします。グラフG (点 1、点 2、...、点n、r ) を頂点 {1、2、...、n }上のグラフとして定義します。対応するポイント間の距離がr以下の場合。(ポイントは、範囲r内にある限り相互に通信できる送信機と考えることができます。)

単位正方形 [0, 1]x[0, 1] 上のn 個の点が与えられた場合、G(点 1、点 2、...、点n、r ) が接続される最小のrとして接続距離を定義します。 .

問題 1) G (点 1、点 2、...、点n、r ) が接続されているかどうかを判断するアルゴリズムを見つける

問題 2) 与えられた任意のn点の接続距離を求めるアルゴリズムを見つける

私の部分的な解決策

問題 1 のアルゴリズム (アルゴリズム 1) を念頭に置いています。まだ実装していませんが、機能すると確信しています。(大まかに言えば、頂点 1 から開始し、エッジを介して他のすべての頂点に到達しようとする考えです。これにいくぶん似ていると思います。)

残っているのは問題 2 だけです。この問題のアルゴリズムも考えています。ただ、時間的に効率が悪いと思います。それがどのように機能するかを説明しようとします：

最初に、接続距離r minが必ずpとqなどの指定された 2 つの点の間の距離であることを自分自身に納得させる必要があります。したがって、 r minの可能な値は最大で *n**( n -1)/2です。

したがって、最初に、私のアルゴリズムはすべての *n**( n -1)/2 距離を測定し、昇順で (たとえば、C の配列に) 格納します。次に、アルゴリズム 1 を使用して、保存されている各値を (昇順で) テストし、グラフがそのような範囲に関連付けられているかどうかを確認します。仕事をする最初の値は答えr minです。

私の質問は: 問題 2 のためのより良い (時間的に) アルゴリズムはありますか?

備考: ポイントはランダムに生成されます (10000 個のようなもの)。これは、アルゴリズムが「迅速に」解決することになっているタイプのものです。さらに、これを C で実装します (違いがあれば)。

4

4 に答える 4

2

あなたのアイデアはかなり良いと思いますが、改善点があります。

実際、測定に基づいて配列を作成し、配列を並べ替えます。非常に素晴らしい。少なくともポイントはあまりありません。

n(n-1)/2 の数は、ペアリング要件の論理的な結果です。したがって、10000 要素の場合、49995000 要素になります。速度を大幅に上げる必要があります。また、この数の要素はメモリ ストレージを大量に消費します。

どうすればより速い速度を達成できますか?

まず、配列を構築しないでください。すでに配列があります。第二に、トラバースすることで問題を簡単に解決できます。与えられた距離がすべてのノードを接続するのに十分かどうかを判断する関数があるとします。この関数を「有効」と呼びましょう。可能な最小値を見つける必要があるため、それだけでは十分ではありません。したがって、アルゴリズムの実行前にノードに関する詳細情報がない場合、私の提案は次の解決策です。

lowerBound <- 0
upperBound <- infinite
i <- 0
while i < numberOfElements do
    j <- i + 1
    while j < numberOfElements do
        distance <- d(elements[i], elements[j])
        if distance < upperBound and distance > lowerBound then
            if valid(distance) then
                upperBound <- distance
            else
                lowerBound <- distance
            end if
        end if
        j <- j + 1
    end while
    i <- i + 1
end while

すべての要素をトラバースした後、upperBound の値はネットワークを接続する最小距離を保持します。あまりにも多くの距離があり、単一のサイクルで問題を解決したため、すべての距離を保存しませんでした。私の答えがお役に立てば幸いです。

于 2013-03-16T00:58:56.697 に答える
2

ある程度の距離でグラフが接続される場合、距離が大きくなるとグラフも接続されます。最小の接続距離を見つけるには、すべての距離を並べ替えてバイナリ検索を使用します。

時間の複雑さは O(n^2*log n)、空間の複雑さは O(n^2) です。

于 2013-03-16T06:02:22.153 に答える