4

A* アルゴリズムを使用して、任意の長さのスライディング ブロック パズルの最適解を見つけようとしています。

スライディング ブロック パズルは、白 (W) と黒 (B) のタイルを 1 つの空きスペース (-) のある直線状のゲーム ボードに配置するゲームです。ボードの初期状態を考えると、ゲームの目的は、タイルを目的のパターンに配置することです。

たとえば、ボード上の私の現在の状態は BBW-WWB であり、BBB-WWW 状態を達成する必要があります。タイルは次の方法で移動できます: 1. コスト 1 で隣接する空きスペースにスライドします。 2. コスト 1 で空きスペースに別のタイルを飛び越えます。 3. コスト 1 で空きスペースに 2 つのタイルを飛び越えます。 2の。

私はすべてを実装しましたが、ヒューリスティック関数についてはわかりません。現在の状態で誤って配置されたタイルから、目標状態で最も近くに配置された同じ色のタイルまでの最短距離 (最小コスト) を計算します。

現在の状態 BWB-W と目標状態 BB-WW に与えられた問題を考慮すると、ヒューリスティック関数の結果は 3 になります (最小距離によると: B=0 + W=2 + B=1 + W=0)。しかし、目標に到達するための実際のコストは 3 ではなく (置き忘れた W => コスト 1、次に置き忘れた B => コスト 1)、2 です。

私の質問は次のとおりです。この方法で最小距離を計算し、過大評価を気にする必要はありませんか、それとも 2 で割るべきですか? タイルが移動できる方法によると、1 つのタイルは同じコストで 2 倍の量を克服できます (移動 1 と 2 を参照)。

両方のバージョンを試しました。分割された距離は、達成された目標への最終的なパス コストを向上させますが、より多くのノードを訪問します => 分割されていないものよりも時間がかかります。それを計算する適切な方法は何ですか？どちらを使用する必要がありますか?

4

2 に答える 2

1

この問題で許容されるヒューリスティック関数がどのようなものかは私にはわかりません。そのため、「2で割った関数を使用する」とは言いません。しかし、あなたが思いついた素朴な機能は許容されないので、あなたに良いパフォーマンスを与えることはできません。A *が適切に機能するためには、使用されるヒューリスティックが許容可能である必要があります。許容されるためには、ヒューリスティックは絶対に常に楽観的な見積もりを与える必要があります。これは、例で強調表示している理由から、そうではありません。

（今私はそれについて考えていますが、2で割ることは許容性を強制するための合理的な方法のように思えます。私はそれにコミットするつもりはありません。）

于 2012-11-27T17:09:41.980 に答える
0

あなたのヒューリスティックは許容できないので、あなたの A* が毎回最適な答えを見つけるとは限りません。許容できるヒューリスティックは、決してコストを過大評価してはなりません。

ヒューリスティック コストを 3 で割るよりも優れたヒューリスティックは、次のようになります。各文字の距離 D を最終的な位置に追加する代わりに、ceil(D/2) を追加します。このように、文字が 1 または 2 離れると 1 の値が得られ、3 または 4 離れていると 2 の値が得られます。

于 2014-02-21T03:47:44.237 に答える