小さな世界グラフを通るパスを見つける最も効率的な方法は何ですか？

StackOverflow https://stackoverflow.com/questions/221311

質問

ノードのクラスターを一緒にリンクするエッジを持つ重み付きノードの海があります。このグラフは、典型的な小さな世界のレイアウトに従います。

ノードが最も有利に重み付けされている最適なパスに沿ってパスを見つけるために、プロセッサパワーに負担をかけないパス検索アルゴリズムを見つけたいです。最速のルートは最も重要な要素ではありません。 このアルゴリズムでは、耐荷重性とトラフィックの再ルーティングも考慮されます。

（補足：ここでニューラルネットワークを使用できますか？）

ありがとう

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

A * アルゴリズムが最も低いコストを見つけるまたは最速ルート、負荷分散なし。

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

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

-imが誤ってA *を誤解しない限り

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

ACOとA *の間のショーダウンのように見えます。A*については非常に前向きな話があります。

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

A *をさらに調査します。しかし、最後の質問を残します！

A *はAntnet（ACO）と同様にスケーリングできますか？

役に立ちましたか？

解決

一般的な注意事項

DijkstraのアルゴリズムとバリアントA *を最適化すると、「the」でパスが見つかります。あなたのグラフを通して最小コスト。重要なことは、a）グラフを正しく定義すること、b）適切なコスト関数を定義することです。

変化するコスト関数に直面して、ダイクスタはソリューションを再計算する必要があります。

ロードバランシングでは、Dikstraを拡張して最適なパスを計算するだけでなく、何らかの種類のフラッドフィル動作を使用して、（コストでソートされた）可能なパスのセットを作成し、代替を見つけます。特定の問題とコスト関数に関する知識のみが、これが機能するかどうかとその方法に答えることができます。

Ant Colony Optimisation は、変化への適応においてはるかに柔軟であるようです。コスト関数の変更後/変更中に反復を継続することにより、コスト関数。

効率

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

他のヒント

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

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

AからCに移動する場所。最初は、A-B-Cが2でA-Cが1であるため、パス検索アルゴリズムはA-Cパスを選択します。パスに追加の用語を追加できます。

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

with 

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

where 

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よりも高くなります。ABCは2です。ユーザーがシステムから削除されると、ACルートは再び最適なオプション。

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

この問題で最もよく使用されるアルゴリズムは、 A *（星）です。これは、ヒューリスティックを追加した一般化されたダイクストラのアルゴリズム検索です-ヒューリスティックの目的は、通常の検索がより速く終了するように、検索目標に向かって検索します。

このアルゴリズムには多くのバリエーション、派生バージョン、改良点があります。Google検索またはWikipediaページが出発点として適切です。

間違いなくA *。 A *は、最適なパスを見つけるか、パスが存在しない場合はパスをまったく見つけません。例えば。このボートのパスはA *

を使用して計算されています

A *ゲームマップの例
（ソース： cokeandcode.com ）

インタラクティブなJavaデモをお試しください。このアルゴリズムはスリープによって速度が低下するため、パフォーマンスが向上していることに注意してください。この速度が低下しないと、1秒未満でパスが見つかります。

アルゴリズムはシンプルでありながら強力です。各ノードには3つの値があり、gはこのノードまでのコストです。 hはこのノードからターゲットまでの推定コストで、fは両方の合計です（フルパスの推測です）。 A *は、オープンリストとクローズリストの2つのリストを保持しています。 Openリストには、これまでに調査されていないすべてのノードが含まれます。 Closedは、探索されたすべてのノードをリストします。アルゴリズムが既にこのノードに接続されているすべてのノードをテストしている場合、ノードは探索済みとしてカウントされます（接続は水平および垂直のみを意味しますが、ノード間の対角移動が許可されている場合は対角も意味します）。

アルゴリズムは次のように説明できます

  1. Pを出発点とする
  2. g、h、fの値をPに割り当てる
  3. Pを開いているリストに追加します（この時点で、Pはそのリスト上の唯一のノードです）。
  4. BをOpenリストの最良のノードにします（最良==最小f値）
    • Bが目標ノードの場合-＆gt;やめて、パスを見つけました
    • オープンリストが空の場合-＆gt;終了、パスが存在しません
  5. CをBに接続された有効なノードにする
    • g、h、fをCに割り当てる
    • Cがオープンリストまたはクローズリストにあるかどうかを確認する
      • はいの場合、新しいパスが最も効率的かどうかを確認します（f値が小さい）
        • その場合、パスを更新します
      • Cをオープンリストに追加する
    • Bに接続されているすべてのノードに対して手順5を繰り返します
  6. BをClosedリストに追加します（すべてのネイバーを調査しました）
  7. ステップ4から繰り返します。

実装の詳細については、 Wikipedia もご覧ください。

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

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

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

一般的なダイクストラでは十分ではありませんか？

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

Dijkstrasアルゴリズム、あなたのための小さな例

graph = {}

graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2
graph["a"] = {}
graph["a"]["finish"] = 1
graph["b"] = {}
graph["b"]["a"] = 3
graph["b"]["finish"] = 5
graph["finish"] = {}

infinity = float("inf")
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["finish"] = infinity
print "The weight of each node is: ", costs

parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["finish"] = None

processed = []

def find_lowest_cost_node(costs):
    lowest_cost = float("inf")
    lowest_cost_node = None
    for node in costs:
        cost = costs[node]
        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node

node = find_lowest_cost_node(costs)
print "Start: the lowest cost node is", node, "with weight",\
    graph["start"]["{}".format(node)]

while node is not None:
    cost = costs[node]
    print "Continue execution ..."
    print "The weight of node {} is".format(node), cost
    neighbors = graph[node]
    if neighbors != {}:
        print "The node {} has neighbors:".format(node), neighbors
    else:
        print "It is finish, we have the answer: {}".format(cost)
    for neighbor in neighbors.keys():
        new_cost = cost + neighbors[neighbor]
        if costs[neighbor] > new_cost:
            costs[neighbor] = new_cost
            parents[neighbor] = node
    processed.append(node)
    print "This nodes we researched:", processed
    node = find_lowest_cost_node(costs)
    if node is not None:
        print "Look at the neighbor:", node

# to draw graph
import networkx
G = networkx.Graph()
G.add_nodes_from(graph)
G.add_edge("start", "a", weight=6)
G.add_edge("b", "a", weight=3)
G.add_edge("start", "b", weight=2)
G.add_edge("a", "finish", weight=1)
G.add_edge("b", "finish", weight=5)

import matplotlib.pyplot as plt
networkx.draw(G, with_labels=True)
plt.show()

print "But the shortest path is:", networkx.shortest_path(G, "start", "finish")
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top