重み付けされていない有向グラフ システム (特に EVE Online の場合) で 2 点からルートを計算できる PHP クラスを開発しています。私はグラフ ソリューションを開発したことがないので、グラフ パスを計算する最速の方法が何であるかはよくわかりません。そのため、数学中心の議論や特殊すぎるソリューションしか見つけられなかったとしても、ネットで調べてみました。
私の最初のアイデアは、ノード A からノード B へのすべてのパスを見つけて、それらの長さを比較することでした。比較する必要はなく、最初の最短パスを見つける必要があるため、それは不要であることに後で気付きました。
次に、Deepening Depth-First Search アルゴリズム (ここで提案しています) を実装する再帰システムを作成しましたが、2 つのノード間の距離が大きくなると、それを使用するにはまだ重すぎます。数秒で 16 ステップ以下の経路をたどることに成功しました。もっと遠くのノードを探すとなると、90秒では終わらない。
より迅速な解決策を見つけるのを手伝ってもらえますか? さまざまなノード間のすべての距離とパスを含むテーブルを作成することを考えましたが、数千のノードについて話しているため、それを作成 (および維持) するのは永遠に続きます。
http://hastebin.com/tilusubeli.coffee
クラス「ジャンプ」。
- コンストラクトは、文字列または整数の形式で、起点 (from) ノードと目標 (to) ノードを受け入れます。前者の場合、ID (整数) を解決して使用します (メソッド getSystemID、無視できます)。「jumpsTable」初期化子は、次の形式で配列を作成します。
$this->jumpsTable[node_id] = array(next_node_id_1, next_node_id_2, ...)
jumpsTable は、グラフのデータ表現です。
- public メソッド「analyse」は IDDFS を呼び出すだけです。
アルゴリズム:
IDDFS は、深さ 0 から DLS を呼び出し、DLS が有効なパスを返すまで (最大深さ) まで続けます。このようにして、同じ長さの 2 つのルートから選択するのではなく、最初のルートを選択します。
DLS は再帰的なメソッドであり、その「子」ノードを探します。子の 1 つがゴール ノードである場合、パスを返します。それ以外の場合は、各子を深さの値を減らして「開始ノード」として呼び出します。DLS の呼び出しでパスが返された場合は、サイクルを終了します。パスを返す DLS がない場合は、null を返します。