3

私たちは、大きな地図上で最短経路アルゴリズムを実行することを含むプロジェクトに取り組んでいます。

今のところ、AStarをAirDistanceheaursticで使用しています。

私たちのプロジェクトには、データベース内のリンクの更新を受け取ることが含まれます。現在、リンクの更新ごと、または事前定義された間隔ごとに検索を再開します。受信した更新ごとに検索を再開せずに検索を更新するようにAStarアルゴリズムを更新する方法はありますか？このタスクに適したより良いアルゴリズムはありますか？

開示：これは学生プロジェクトの一部です。

ありがとうございました。

4

1 に答える 1

2

あなたはルーティングアルゴリズムを探しているかもしれません（それは本質的に絶えず変化するグラフを扱います）。

これを実現する1つの方法は、距離ベクトルルーティングプロトコル（ベルマンフォードアルゴリズムの分散バージョン）を使用することで、次のように機能します1：

  • 定期的に、すべての頂点はその「距離ベクトル」を隣接する頂点に送信します[ベクトルは、送信する頂点から他の頂点に移動するのに「コスト」がかかることを示します。
  • そのネイバーは、ルーティングテーブルを更新しようとします[各ターゲットに移動するのに最適なエッジはどれですか]
  • あなたの場合、各ノードは隣接ノードに到達するための最速の方法を知っており（グラフが重み付けされていない場合は1）、その方法と方法を知るために、ノード（頂点）は距離ベクトルの各プリモピアットにこの番号を追加します目的地に着くまでにかなりの時間がかかります。変更が到着するたびに、関連するノードは、再収束するまでプロトコルの新しい反復を呼び出します。

ただし、このアルゴリズムには情報がないことに注意してください（ただし、グラフの変更には十分に対応しますが、特定の制限がありますが、無限にカウントされる問題があります） 。

（1）アルゴリズムの説明は、このスレッドでしばらく前に提供した説明に基づいていますが、いくつかの変更が加えられています。（結局のところ、これは同じ提案されたアルゴリズムです）。

于 2012-12-20T17:22:13.190 に答える