問題は、前の最も近いノードから最も近いノードに到達できない場合はどうなるかということです。
この手順は必要ありません。のように、以前の最も近いノードから現在の最も近いノードへのパスを計算しているのではなく、目標ノードに到達しようとしており、現在最も近いノードだけが重要です (たとえば、アルゴリズムは最後の反復を気にしません)。この反復では 96 km しか離れていないため、100 km 離れていました)。
概説すると、A* はパスを直接構築しません。探索した領域内にパスが含まれていることが確実にわかるまで探索し、探索中に記録された情報に基づいてパスを構築します。
( Wikipedia の記事のコードを参照実装として使用して、説明を補助します。)
次の 2 つのノード セットがありますclosedset。openset
closedset完全に評価されたノードを保持します。つまり、それらがどれだけ離れているかを正確に把握しておりstart、すべての隣接ノードが 2 つのセットのいずれかに属しています。これにより、それらを使用して実行できる計算はこれ以上ないため、それらを (ある程度) 無視することができます。(基本的にこれらは境界内に完全に含まれます。)
opensetは「境界」ノードを保持します。これらが からどれだけ離れているかはわかってstartいますが、まだ隣接ノードに触れていないため、これまでの検索の端にあります。
(暗黙的に、3 番目のセットがあります。完全に手を加えられていないノードです。しかし、それらが入るまで実際には触れないopensetので、それらは重要ではありません。)
特定の反復で、探索するノード (つまり、 のノードopenset) がある場合は、探索するノードを決定する必要があります。これはヒューリスティックの仕事であり、基本的に、どのノードが への最短経路を持つと考えられるかを伝えることで、次に探索するのに最適な境界上のポイントについてのヒントを提供しますgoal。
以前の最も近いノードは関係ありません。新しいノードを に追加して、境界を少し拡張しただけopensetです。これらの新しいノードは、この反復で最も近いノードの候補になります。
最初はopensetのみが含まれてstartいますが、その後反復し、最終的に に到達するまで、各ステップで境界線が少し (最も有望な方向に) 拡張されますgoal。
A* が実際に探索を行っているときは、どのノードがどこから来たかは気にしません。startからの距離とヒューリスティック関数を知っているので、必要はありません。必要なのはそれだけです。
ただし、後でパスを再構築するには、パスの記録が必要camefromです。特定camefromのノードについて、 に最も近いノードにリンクするため、startから逆方向にリンクをたどることで最短パスを再構築できますgoal。
関数の引数として「グラフ」を実際にどのように取るのですか?
グラフの表現の 1 つを渡す。
A* が TSP にどのように適用されるかはよくわかりません。つまり、A から B へのルートを見つけるということです。しかし、TSP？接続がわかりません。
別のヒューリスティックと別の終了条件が必要です。goalもはや単一のノードではなく、すべてが接続された状態です。ヒューリスティックは、残りのノードを接続する最短パスの長さの推定値です。