A-star は、グラフの開始ノードと終了ノードの間の最短経路を見つけるために使用されます。ターゲットの状態が具体的に知られておらず、代わりにターゲットの状態の基準しかない場合、何かを解決するためにどのアルゴリズムが使用されますか?
たとえば、Astar のようなアルゴリズムで数独パズルを解くことはできますか? 最終状態がどのように見えるか (どの数字がどこにあるか) はわかりませんが、数独のルール (勝利状態の基準) は知っています。したがって、開始ノードと終了ノードの基準だけがあります。どのアルゴリズムを使用すればよいですか?
A* には、グラフ、そのグラフを走査するためのコスト関数、グラフ内のノードが別のノードよりも目標に近いかどうかに関するヒューリスティック、および目標に到達したかどうかのテストが必要です。
数独ソリューション スペースの検索には、最小化するトラバーサル コストは実際にはなく、グローバル コスト (未解決の四角形の数) のみがあるため、すべてのトラバーサル コストは等しいため、A* は実際には役に立ちません - 割り当てることができる任意のセルは 1 手のコストがかかり、ゴールに 1 近づきます。したがって、A* は次のステップを無作為に選択することに勝るものはありません。
各ポイントでさまざまな手法を適用する推定/測定コストに基づいて A* 検索を適用することは可能かもしれません。これにより、最小の計算コストで解空間を通るパスを見つけようとします。その場合、グラフはパズルの解の状態だけでなく、その時点で適用する手法を選択することになります。遷移のコストの見積もりはわかりますが、その遷移の場所はわかりません。ただし、成功すれば目標に一歩近づきます。
はい、特定の目標状態を特定できない場合に A* を使用できます。( Pete Kirkham の回答はこれを暗示していますが、あまり強調していません。)
特定の目標状態を特定できない場合、部分的なソリューションを完了するために必要な残りのコストについて、有効なヒューリスティック下限を見つけるのが難しい場合があります。また、A* の効率は、効果的なヒューリスティックの選択に依存します。しかし、適用できないわけではありません。 コンピューターで解決できる問題はすべて、幅優先検索と、状態が以前に見られたかどうかを示すフラグの配列を使用して解決できます。これは、ヒューリスティックな下限が常にゼロの A* と同じです。(もちろん、これは多くの問題を解決するための最も効率的なアルゴリズムではありません。)
正確なターゲットの終了状態を知る必要はありません。それはすべてヒューリスティック関数に帰着します。0 が返された場合、有効な終了状態の 1 つが (少なくとも) 見つかったと見なすことができます。
したがって、a* の間、current_node == target_node かどうかをチェックする代わりに、current_node.h() が 0 を返すかどうかをチェックします。