次の問題は、人工知能コースで見つけた試験問題です。
「ヒルクライミング アルゴリズムを使用して、この問題を解決できるヒューリスティック メカニズムを提案してください。(S=開始点、F=最終点/ゴール)。斜めの移動は許可されません。」
マンハッタン距離またはユークリッド距離がロボットを (3,4) に送り、バックトラックが許可されないことは明らかなので、この問題に対する可能な解決策 (ヒューリスティック メカニズム) は何ですか?
編集: 問題をより明確にするために、ボード上のマンハッタン距離のいくつかをマークしました。
マンハッタン距離を使用すると、ヒューリスティック値が 2 であるため、ロボットの次の移動は (3,4) になることは明らかです。HC はそれを選択し、永遠に立ち往生します。目的は、適切なヒューリスティック アルゴリズムを見つけることによって、決してその道に進まないようにすることです。
障害物が熱いと思ったら、その熱が上がる。セルの正味コストは、F までのマンハッタン メトリック距離と熱ペナルティの合計です。したがって、ロボットを F に向かって引き寄せる引力と、ロボットを障害物から遠ざける反発力があります。
ヒート ペナルティには次の 2 種類があります。
1) 障害物に触れるのは非常に悪い。特定のセルのすぐ下の行にあるセルに隣接する 2 つまたは 3 つのセルを見てください。指定されたセルの真下にある障害物セルごとに 15 を加算し、真下にある斜めの隣接セルごとに 10 を加算します。
2) 指示書と直接接触していない細胞の場合、熱はより拡散します。セルの下の障害物ブロックの平均数の 6 倍として、セルの列と隣接する列の両方で計算します。
以下は、これらすべてを組み合わせた結果と、S から F までのパスを示しています。
重要なポイントは、平均化により、ロボットが一番上の列に当たったときに右ではなく左に曲がる方法です。左に向かって加熱されていない柱は、それをより冷たい方向にします. すべてのセル (右上隅の 2 つのセルを除く) が、このヒューリスティックによってどのように F に描画されるかを確認するのは興味深いことです。