迷路内の複数の目標を検索するための星アルゴリズムを改善する

Question

迷路で単一のゴールへの最短経路を見つけるためにA *アルゴリズムを実装した場合（私は現在のヒューマニス私のアルゴリズムが迷路で複数の目標をサポートするように（目標までのマンハッタン距離+これまでの走行コスト）。基本的には、私は迷路内のすべての目標を通過する最短経路を見つけたいと思っています。パスが最適であることを確認するためには、問題の一貫性を無視して、ヒューリスティック関数を許容する必要があります。

これは旅行のセールスマンの問題のようなものですが、今は比較的少量のデータしか扱っていないので、私はA開始アルゴリズムを使いたいと思います。

ご迷惑をおかけしておりません。ありがとう！

Answer 1

A *はあるポイントから別のポイントへの最短パスを検出します。

許容パスに制約を追加することはできません（途中でこれらすべてのノードをA @に移動する必要があります）。また、最短パスを生成することはできません。

A *を使用して目的地間の距離（および経路）を見つけ、目的間の移動セールスマン問題（その距離を使用して）を解決し、最短経路。

Answer 2

まだ訪問していない最も近い目標までの距離を使用できます。最後のゴールが訪れたときには0になるだけです。