artificial-intelligence - スライド タイル問題のヒューリスティック

Question

アイデアは、すべての右側の要素を左側に移動し、左側を右側に移動して、真ん中に空のスペースを配置することです。要素は、1 つまたは 2 つのピースを飛び越えて空のスペースに入ることができます。

LLL[ ]RRR

このタスクのヒューリスティックを考えようとしています。ヒューリスティックは可能な解決策を見つけるのを助けることを意図していますか、それとも解決策として実際に多くの動きを返しますか? このようなヒューリスティックをどのように表現すればよいでしょうか?

Answer 1

ヒューリスティックとは何かについて少し混乱しているようですね。

大まかな定義は「単純化した仮定」または「まともな推測」です

たとえば、バスケットボールチームを編成する必要があり、プレーしたい人の連絡先情報、生年月日、身長が記載されたファクトシートがあるとします。各候補者の特定のスキルをテストするトライアウトを開催できます。ただし、すべての候補者を連れてくる必要があり、それには長い時間がかかる可能性があります。ヒューリスティックを使用して検索を絞り込みます。身長が6フィート2インチ以上の人にのみ電話をかけます。これは、一部の優れたバスケットボールプレーヤーを無視する可能性がありますが、かなり適切な推測です。

ヒューリスティックの別の例：請求書の支払いに最小数のコインを使用しようとしています。ヒューリスティック（単純化するアプローチ）は、最初に最大値（残りの請求額よりも少ない）のコインを選び、請求書から値を差し引いて、繰り返すことです。これが毎回機能することは保証されていませんが、ほとんどの場合、適切な場所に移動できます。

問題のヒューリスティックは、「Lsを右に移動したり、Rsを左に移動したりしない」ことです。これは、最初からいくつかの可能性を排除することにより、すべての可能な移動の「検索スペース」を狭めます。

Answer 2

ヒューリスティックまたはアルゴリズムをお探しですか? ヒューリスティックは、特定の問題を解決する場合と解決しない場合があります。これは、解決策がおそらくある方向を示すことを目的としています。アルゴリズムは、特定の問題を実際に解決する必要があります。

Answer 3

ヒューリスティックは一般に「ヒント」であり、通常（常にではありませんが）手順を正しい方向に導きます。ヒューリスティックを使用すると、手順（アルゴリズム）が高速化されます。これも通常ですが、常にではありません。これは、多くの場合正しいアルゴリズムへの「アドバイス」のようなものです。

説明が少し曖昧なので、何を探しているのかわかりません。アルゴリズムが必要な場合は、特定の動きが現在の状況にどのような影響を与えるか、そしてすべての可能な動きを毎回前進させる方法を研究する必要があります。あなたは特定の一連の動きをします）。

また、現在の位置が達成したいもの（目的の最終位置）にどれだけ近いかが重要であることがわかります。したがって、初期状態から最終状態が見つかるまでのすべての可能なパスを計算する代わりに、 「現在の状態が目的の状態にどれだけ近いか」というヒューリスティックに基づくアルゴリズムで、ツリーの一部のみをトラバースします。