14

ノードのクラスターをリンクするエッジを持つ重み付けされたノードの海があります。このグラフは、典型的なスモール ワールド レイアウトに従います。

ノードが最も有利に重み付けされ、最速のルートが最も重要な要素ではない、可能な限り最良のパスに沿ったパスを見つけるために、プロセッサの電力にコストがかからないパス検索アルゴリズムを見つけたいと思います。このアルゴリズムでは、ロード ベアリングとトラフィックの再ルーティングも考慮されます。

(補足: ここでニューラル ネットワークを使用できますか?)

ありがとう

私はACOを見ています。この種の問題に対して ACO より優れたものはありますか?

A*アルゴリズムは、ロードバランシングなしで、最小コストまたは最速のルートを見つけます。

最速または最短のルートが最も重要なルートではないとしましょう。より重要なのは、重み付けされたノードが特定の値を持つパスをたどることです。いいえ1。

no2. A* を使用すると、そのルートのトラフィックが過負荷になり、突然そのパスが冗長になります。A* と同じくらいクールですが、ACO に固有の負荷分散などの特定の機能はありません。

-- 私が間違ってA*を誤解していない限り

では、ACOに勝るものは何ですか？

本当に ACO と A* の対決のように見えます。A* について非常に多くの肯定的な話がありました。

まず、デビッドに応えて。バックグラウンドで ACO シミュレーションを実行し、最適なパスを見つけることができるので、初期のスタートアップ コストはかかりますが、幸運にもスタートアップは必須ではありません。そのため、シミュレーションを複数回実行する余裕があります。本当の問題の 1 つは、接続されたソース ノードと宛先ノードを見つけることです。A* はこれを非常に簡単に実行できるようです。このネットワークが何百万ものノードのように非常に大きくなるとどうなるでしょうか。A* は簡単にスケーリングできますか?

A*をさらに研究します。しかし、最後に質問をさせてください！

A* は Antnet (ACO) と同様にスケーリングできますか?

4

7 に答える 7

12

一般的な注意事項

ダイクストラのアルゴリズムと最適化されたバリアントA*は、グラフから「最小の」コストでパスを見つけます。重要なことは、a）グラフを正しく定義すること、およびb）適切なコスト関数を定義することです。

コスト関数の変化に直面して、Dijkstaは解を再計算する必要があります。

負荷分散については、ダイクストラを拡張して最適なパスを計算するだけでなく、ある種のフラッドフィル動作を使用して、代替案を見つけるための可能なパスのセット（コストでソート）を作成します。特定の問題とコスト関数に関する知識だけが、これが機能するかどうか、およびどのように機能するかについて答えることができます。

一方、蟻コロニー最適化は、コスト関数が変化した後/その間、反復を継続することにより、変化するコスト関数に適応する上ではるかに柔軟であるように思われます。

効率

これは、問題のドメインに大きく依存します。優れたヒューリスティックがあり（A *の記事の「複雑さ」セクションを参照）、コストの変更がほとんどない場合、A*の多項式ランタイムは再計算の繰り返しを優先する可能性があります。一方、ACOは、近似解に収束する前に、何度も繰り返す必要があります。コストの変更が非常に頻繁に発生する場合、情報はアルゴリズムの状態内に保持されるため、一定の速度で反復を継続する方がA*ソリューションを更新するよりも効率的である可能性があります。ACOは最適なソリューションを約束していませんが、おそらく「優れた」ソリューションに収束する前の初期費用が高くなります。繰り返しになりますが、それは特定のドメイン、グラフ、コスト関数、および最適性の要件に大きく依存します。

于 2008-10-21T11:07:34.310 に答える
8

A *を使用すると、パスコストを一定にする必要がないため、次のグラフから始めることができます。

A---1---B---1---C
|               |
\-------1-------/

ここで、AからCに移動します。最初に、パスファインディングアルゴリズムはABCが2であるのに対し、ACは1であるため、ACパスを選択します。パスに用語を追加できます。

A---r---B---r---C
|               |
\-------r-------/

と

r(NM) = k(NM) + users(NM) / 10

どこ

r(NM) is the cost for a connection between N and M,
k(NM) is the constant cost for a connection between N and M,
users(NM) is the number of objects using the connection

ユーザーがシステムに追加されると、ルートACは20ユーザー（1 + 20/10）= 3、ABCは2でABCよりも高価になります。ユーザーがシステムから削除されると、ACルートが最適なオプションになります。また。

A *の真の力は、各接続のコストを計算するために使用するヒューリスティックです。

于 2008-10-21T10:55:58.730 に答える
7

この問題で最も一般的に使用されるアルゴリズムはA* (A Star)です。これは、ヒューリスティックが追加された一般化されたダイクストラのアルゴリズム検索です。ヒューリスティックの目的は、典型的な検索がより速く終了するように、検索を検索目標に向けることです。

このアルゴリズムには多くのバリアント、派生バージョン、改良点があります。Google 検索またはウィキペディアのページが出発点として適しています。

于 2008-10-21T09:46:03.943 に答える
3

間違いなくA *。A* は可能な限り最適なパスを見つけるか、パスが存在しない場合はまったくパスを見つけません。たとえば、このボートの経路は A* を使用して計算されています

A* ゲームマップの例
(出典: cokeandcode.com )

これは、インタラクティブな Java デモです。このアルゴリズムはスリープによって速度が低下することに注意してください。この速度低下がなければ、1 秒もかからずにパスを見つけることができます。

アルゴリズムは単純ですが、強力です。各ノードには 3 つの値があり、g はこのノードまでのコストです。h はこのノードからターゲットまでの推定コストであり、f は両方の合計です (完全なパスの推測です)。A* は、Open リストと Closed リストの 2 つのリストを維持します。開いているリストには、これまで調査されていないすべてのノードが含まれています。Closed には、探索されたすべてのノードがリストされます。アルゴリズムがこのノードに接続されているすべてのノードをすでにテストしている場合、ノードは探索済みとしてカウントされます (接続されているとは、水平方向と垂直方向のみを意味しますが、ノード間の斜めの移動が許可されている場合は斜めも意味します)。

アルゴリズムは次のように記述できます。

  1. P を始点とする
  2. g、h、および f の値を P に割り当てます
  3. P を開いているリストに追加します (この時点で、P はそのリストの唯一のノードです)。
  4. B を Open リストからの最良のノードとする (最良 == 最小の f 値)
    • B がゴール ノードの場合 -> 終了すると、パスが見つかりました
    • 開いているリストが空の場合 -> 終了、パスは存在しません
  5. C を B に接続された有効なノードとする
    • g、h、および f を C に割り当てます
    • C がオープン リストまたはクローズ リストにあるかどうかを確認する
      • はいの場合、新しいパスが最も効率的かどうかを確認します (より低い f 値)。
        • その場合は、パスを更新します
      • それ以外の場合は、オープン リストに C を追加します
    • B に接続されているすべてのノードに対して手順 5 を繰り返します。
  6. B を Closed リストに追加します (すべての近隣を調査しました)。
  7. 手順 4 から繰り返します。

実装の詳細については、ウィキペディアもご覧ください。

于 2008-10-21T10:13:33.700 に答える
0

この種の問題も処理するためのNN実装について聞いたことがあります。したがって、NNを使用したい場合は、最終的には自分の道を見つけるでしょう;-)しかし、それらは「遺伝的アルゴリズム」と比較して劣っていなければなりません。

計算/時間の消費が問題になる場合は、遺伝的アルゴリズムを使用することを強くお勧めします。これはまさに彼らが例外的な問題のタイプです。

GAは、特定のソリューションに対する満足度を表す関数に基づいています。この関数は、ニーズに合わせて変更できます（つまり、パスコストだけでなく、必要な要素を含めることができます）。

于 2008-12-24T01:33:23.127 に答える
0

一般的なダイクストラでは不十分でしょうか?

http://improve.dk/generic-dijkstras-algorithm/

于 2008-10-21T09:47:17.747 に答える