A *検索アルゴリズムを使用して3x3の3次元ボックスパズルを解く？

Question

私は宿題で3x3の三次元のボックスパズルの問題に取り組んでいます。私はそこに26箱があり、最初は、最初の場所が空である

C.

でコーディングします。ボックスをスライドさせることによって、それらを正しい順序で並べなければなりません。赤い数字は正しい順序を示し、27位は最後に空でなければなりません。私はあなたにコードを与えることを望んでいません。フォーラムで検索したところ、 A* search algorithmを使用する必要があるようですが、どうですか？

あなたは私がこの問題にA *アルゴリズムを使用する方法についてのヒントを与えることはできますか？どのようなタイプのデータ構造を使用する必要がありますか？

Answer 1

あなたはグラフがどのように機能するかを知っているとどのように*は、右の彼らの最短経路を見つけますか？

基本的な考え方は、パズルの各構成は、グラフの頂点と考えることができ、エッジが（移動前後の構成を接続することによって）移動を表すことです。

問題を発見パスと見なすことができ、所望のものに元の構成からリード移動のセットを見つけます。

Answer 2

状態グラフとして問題を定義：
G=(V,E)V=S={(x_1,x_2,...,x_54) | all possible states the 3d board can be in}を[各数値は、3D基板上の単一の「正方形」を表しています]。あなたはまたadmissible heuristic function、することができ、この問題のためのかなり良いものが必要になりますsuccessors(v)={all possible boards you can get, with 1 step from v}

：Vの各Vが
：
とE={(v1,v2)| it is possible to move from state v1 to state v2 with a single step}にEのための別の定義[同じ]を定義するには、機能successors(v)を使用することです： h(state)=Sigma(manhattan_distance(x_i)) where i in range [1,54])は基本的には、ターゲットからの各数値に対してmanhattan distancesの合計です。私たちは、このデータを得た後、

今、私たちは、定義されたヒューリスティックで、定義されたグラフG上で*の実行を開始することができます。そして、我々のヒューリスティック関数は許容可能であるので[理由をあなた自身に納得させる]、admissibility and optimality of A*のために、A *の解が最適であることが保証される。
実際のパスを見つける：ターゲット状態を作成するとA *が終了します。 [先に使用した意味でx_i=i]。各ノードのparentフィールドを使用して、ターゲットからソースにステップバックすることで、そのパスを見つけることができます。