Rubikの立方体のヒューリスティック

Question

ヒューリスティックを設計するためのパターンデータベースを理解しようとしています。私はRichard E. Korfの本ヒューリスティック検索を読んでいます。その段落の1つは

と言います。ルービックキューブの明らかな経験則は、マンハッタン距離の3次元バージョンです。各キュービについて、キューブの位置と方向を正しく合わせるために必要な最小移動数を計算し、これらの値をすべてのキュービットで合計します。残念ながら、許容できるようにするには、すべてのツイストが8キューブを移動するため、この値を8で割る必要があります。マンハッタン距離の合計を4で除算し、エッジキュービの合計の最大値を4で割った値の最大値を取ることがより良いヒューリスティックである。エッジキュービのマンハッタン距離の期待値は22/4 = 5.5であり、コーナーキューブの対応する値は12.333/4であり、エッジキューブは12であるがコーナーキューブは8であるため、3.08にほぼ等しい。

私の質問は、なぜ4で割ったコーナーcubiesのためのマンハッタン距離の和の最大値を取っているし、4で割ったエッジcubiesのためのマンハッタン距離の合計の最大値は、マンハッタン距離の和をとるよりも良いヒューリスティックです8で割った？

さらに、期待値5.5と3.08はどうやって得られますか？

Answer 1

コーナー/エッジキュービクルの動きが誘発される誤差の量が少ないことを考慮すると、この意味では距離の真値に近い方がよい。誘発された誤差によって、私はあなたがすでに別のものを計算していてもあなたの立方体を修正しても、ある距離を計算することを意味するので、現在の計算は誤差を伴い、次のものと次のものがあります。 （単純合計）独立性各運動の仮定しているので、認めるべきヒューリスティックがまだ保証されている（ほぼ）独立した要素が好ましい。これは単にルービックキューブには当てはまらない。したがって、独立の違反の数が少ないほど、ヒューリスティックはより信頼性が高くなります。