A *アルゴリズムを使った8個のパズルを解く

Question

JavaでA *アルゴリズムを使って8個のパズル問題を解決/実装したいと思います。誰かが私にそれを解決するために従わなければならないステップを私に説明することで助けてくれるか尋ねています。私はネット上でA *の仕組みを読みましたが、Javaで実装を開始する方法はわかりません。

皆さんが私を助けて、私がJavaで自分自身を実装できるようにガイドラインを与えることができれば、非常に感謝します。私は本当にそれを理解できるようにしたいので、私は開始するためのガイドラインが必要です。

---

私はプライオリティキューを使用し、例えばのように見えるテキストファイルから初期設定を読み込みます。この：より詳細な説明/チュートリアルのために、他のサイトへ

4 3 6 
1 2 5 
7 8 

ポインタは歓迎されています。

Answer 1

私はゲームボードの状態をどのように表現したいのかを決め始めます。 は、演算子を実装します（例えば、移動（空白）タイルアップ、移動（空白）タイルダウン...）。 通常、開いているリストを表すデータ構造（すなわち、 がまだ発見されていない（つまり、目標状態と比較された）状態と、 閉じられたリストの状態 開いているリストを開始状態でシードし、繰り返し「次の」状態を にして、開いているリストから探索し、演算子を適用して新しい可能な状態 などを生成します。

http://www.cs.rmit.edu.au/AI-Search/

..

私が何年も前に準備チュートリアルがあります

ステートスペースの検索での決定的な言葉とはまったく異なりますが、これは単に概念の新しいブランドのための単なる教育ツールです。

Answer 2

A *はDjikstraのアルゴリズムとよく似ていますが、それにはヒューリスティックが含まれています。 wikiを読んだり、一般的にシングルソースの最短パスアルゴリズムについて読んでみてください。

多くの基本的なものは重要ですが、明らかです。ボードを表現し、可能な次の状態を生成する方法を作成する必要があります。

任意の位置の基本スコアは、実際に到達するための最小の実際の移動数であることは明らかです。 A *が機能するためには、次の状態の可能な最良のオプションを選択するのに役立つヒューリスティックが必要です。 1つのヒューリスティックは、正しい位置にあるピースの数です。

Answer 3

「http://olympiad.cs.uct.ac.za/presentations/camp1_2004/heuristics.pdf」にチェックすると、この問題に取り組む方法が説明されています。

Answer 4

ゲームの状態を表す方法を選択する必要があります。 8-puzzleの問題の状態は、3x3グリッド、9要素の整数配列、9要素のchar配列、文字列または単なる整数（436125780は例の状態を表すことができます）、空白セルは0として表されます。ちょうど整数を使用するとスペース効率が最も良くなり、非常に効率的なセット挿​​入/メンバーシップチェック（クローズドセットの実装のため）をサポートします。しかし、後継国を見つけることはより困難になるでしょう。 9要素のchar配列を使用すると、後続の状態を簡単に見つけることができます。私は両方を使用することをお勧めします。後続の検索にはchar配列表現を、閉じた集合には整数表現を使用してください。

次に、ヒューリスティック関数を選択する必要があります。 8パズルの場合、一貫性のあるヒューリスティックであり、A *グラフ探索アルゴリズムの最適性を保証するマンハッタン距離を用いることができる。

A *の問題を解決するには、状態を表す方法を見つけ、状態の後継者を生成し、ヒューリスティック関数を選択する必要があります。残りのアルゴリズムはブラックボックスとして扱うことができます。

私は*検索アルゴリズムの記事を書いたし、ここにヒューリスティックとして*とマンハッタン距離を使用してN-パズル問題のPython実装を提供する：あなたは、リンクのためにログインする必要A* search explanation and N-puzzle python implementation