A* で解決すべき問題がありますが、適切なヒューリスティックを設計するのが困難です。
私の問題は次のとおりです。
負荷を最大化し、移動時間を最小化することを目的として既知の地図上を移動する都市のごみ収集車が達成するための最適なルートを決定します。
ノードには、Geral ノード、Dump ノード、Garbage ノード、Gas ノードの 4 種類があります。
ごみ収集車のガスが不足している可能性があり、車両を補充する機会があります。配達先のゴミ収集場が複数ある場合もあります。
この問題を解決するための最良のヒューリスティックは何ですか?
よろしく
優れた初回通過検索ヒューリスティックは、貪欲なアルゴリズムを使用することです。たとえば、一般的なルート計画アルゴリズム (都市間の最短ルートを見つける) では、カラスが飛んでいるときに常に目的地に最も近い次の都市に行く貪欲なアルゴリズムを使用するのがまともなヒューリスティックです。これは線形時間のヒューリスティックであり、解を過大評価することはありません。あなたの場合、ゴミ収集車が常に次に近いゴミノード、またはゴミが最も多いゴミノードに行く貪欲なアルゴリズムを使用できるかもしれません。使用している 4 つのノードの詳細を知らなければ、これ以上具体的なことは言えませんが、アイデアはわかります。解を過大評価しない線形時間アルゴリズムで十分であり、次のパスで微調整できます。(ほとんどの場合、nlog(n) ヒューリスティックも受け入れられます。
A* は、2 地点間の最速/最短ルートを見つけるのに最適です。
しかし、ごみ収集車の問題は、おそらくまったく別の問題です。一連のポイントを順序付けることによって、最速/最短のルートを見つける必要があります。これは基本的に、巡回セールスマン問題 (TSP) または配車ルート問題 (VRP) の兄弟であり、どちらもNP 完全です。
A* は NP 完全問題を処理できません。メタヒューリスティックなどのアルゴリズムが必要です。たとえば、OptaPlanner (Java、オープン ソース) の TSP と VRP の例 (このビデオで示されています)など、TSP と VRP の問題の解決策を探します。