1

ダイクストラ アルゴリズムの j2ME 実装を高速化するのを手伝ってくれる人はいますか? 2 つのループがあり、1 つは別のループです。このような

while(for each item in Q)
{
    //...do something.

    //the following loop is to find the minimum
    for(all un-visited nodes in Q)
    {
       //.. do something to get min.
    }
}

ほぼ 23000 のノードとそれらを接続する 50000 のエッジがあります...以下で説明するすべての改善の後、内側のループは平均 169330131 回実行されます。w910i モバイルでは完了までに 5 分かかり、エミュレータでは数分以上かかります。これは私には多すぎるように見えます。改善のための提案はありますか？私はすでに以下の改善を実装しています。

  1. ベクトルの代わりに配列を使用します。
  2. 内側のループが訪問したノードを考慮していないことを確認してください。訪問したすべてのノードは配列の最後にあり、ノードはその数を知っています。だから、私は簡単にそれらを完全にスキップすることができます.
4

3 に答える 3

2

問題のアルゴリズムは間違っていると思います。内側のループは、外側のループ内のアイテムの未訪問の各ネイバーを確認する必要があります。

for each (item in Q)
{
  for each (unvisited neighbour of item)
  {
  }
}

ウィキペディアの擬似コードの実装と比較してください。

 1  function Dijkstra(Graph, source):
 2      for each vertex v in Graph:           // Initializations
 3          dist[v] := infinity               // Unknown distance function from source to v
 4          previous[v] := undefined          // Previous node in optimal path from source
 5      dist[source] := 0                     // Distance from source to source
 6      Q := the set of all nodes in Graph
        // All nodes in the graph are unoptimized - thus are in Q
 7      while Q is not empty:                 // The main loop
 8          u := vertex in Q with smallest dist[]
 9          if dist[u] = infinity:
10              break                         // all remaining vertices are inaccessible
11          remove u from Q
12          for each neighbor v of u:         // where v has not yet been removed from Q.
13              alt := dist[u] + dist_between(u, v) 
14              if alt < dist[v]:             // Relax (u,v,a)
15                  dist[v] := alt
16                  previous[v] := u
17      return previous[]
于 2009-05-10T07:59:16.410 に答える
1

私はこのアルゴリズムを参照しました。私は他の場所でより単純なアルゴリズムを見つけました。ウィキペディアで実装する必要がある場合、2つの内部ループがあることに注意してください。

while Q is not empty: //Outer loop. 
  u := vertex in Q with smallest dist[];// First inner loop. 
  .... 
  for each neighbor v of u: //Second inner loop.

2番目の内側のループは小さくなっています。各ノードには最大5つのエッジがあるため、最大4〜5を実行する可能性があります。エッジが2つを超えるノードの数は、合計23000ノードのうち1000ノードです。したがって、内部ループの実行時間はごくわずかです。最初の内側のループが問題です。最小のノードを見つける。これはj2MEデバイスで実行する必要があるため、できるだけ少ないスペースで実行する必要があります。

于 2009-05-10T08:12:56.487 に答える
1

実装に問題があります。その複雑さは O(E + V * log2 (V)) です。

つまり、50000 + 23000 * ~15 = 400 000 回の反復です。

現在の複雑さはほぼ O(V^2) です。

于 2009-05-10T07:47:02.167 に答える