したがって、現在の状態が与えられるこの 3x3 ゲームに取り組んでいます。たとえば、次のようになります。
1 5 6
3 7 b
2 8 4
そして、次の目標状態に到達したいと考えています。
b 1 2
3 4 5
6 7 8
そのため、以下に投稿したコードに他のすべてのメソッドを記述しました。私が今抱えている問題は、実際の A* 検索にあります。私は 2 つのヒューリスティックを使用したいと考えています。1 つは間違った場所にあるピースの数をチェックするものであり (たとえば、ヒューリスティック関数は、現在の状態で H=8 ピースが間違った場所にあることを示します)、もう 1 つはどのくらい離れているかを計算するヒューリスティックです。ピースの合計は (つまり、私の現在の状態では、ピース 1 は 1 移動分、ピース 2 は 3 移動分、など、すべての合計が H 値になります) です。gameBoardそのため、文字列の配列に記録しています。
だから今、私の実際の問題に。以下に示すように、私の A* 以外のすべてが現在機能しています。
まず、現在の状態と目標の状態を比較できるようにsetFinalGoalState()、変数を作成する whichを呼び出します。finalGoalState
次に、各ノードが G 値 (G はツリー内の距離)、H 値、親への参照、および現在の状態を持つ s の であるpriorityQueueべきa を作成します。ArrayListNode
最初にイニシャルを呼び出してhuesticOneHValue()、最初の状態の H 値を取得します。次に、"h1" のステートメントを実行しますif(後で別の方法を追加すると述べたように、これは最初のヒューリスティックな方法です)。Root次に、ツリー内の最初のノードとなる初期ノードを作成し、これを優先キューに追加する必要があります。
次に、優先キューを通過する必要があります。現在のノードを の最初の要素として取得しpriorityQueue、キューから削除します。現在のノードとgameBoard同じ状態としてmy actual を設定します。gameBoard次にArrayList、可能な移動の を作成します (これは を呼び出しisValidMoves()、実際に上下左右に移動できるかどうかを確認し、それをリストに入れます)。次に、可能な移動のサイズを実行する for ループを作成し、move()メソッドを呼び出して実際の移動を行います (現在の状態で b を上に移動できるため、最初の呼び出しでint i = 0は move "up" が呼び出されます)。次に、をNode含む子を作成する必要がありますgValue私がどこにいるのか（1に等しいはずです）、新しいH値（場合によってはこれは同じままかもしれませんが、H値を下げる方向に取り組んでいるはずです）、その親（私はそうあるべきだと思いますcurrentNodeか？）、そしての状態currentNode(ボードの外観)。
次に、次の for ループ チェックで、優先度キューのどこに配置する必要があるかが確認されます。値が小さいノードg+hはキューの先頭に配置する必要があります。最初にそれらをチェックして、目標状態に到達したかどうかを確認する必要があるためです。そのため、キューが空の場合は初期条件を設定して先頭に追加し、そうでない場合はpriorityQueueatが子よりもj大きいかどうかを確認し、大きい場合は子が(および他のすべてg+hのインデックスに追加されます)j最後に、すべての移動が完了した後、priorityQueueフロント ノードの状態が目標状態と等しいかどうかを確認し、そうでない場合は while ループの先頭に戻り、再び実行されます。
最終的には、ノードで何かを台無しにしていると思います。デバッグを実行すると、子を作成するたびに、親ノードの状態が子の状態に更新されることがわかりました。これは、子が親の特定の動き (上、下、左、または右）。ノードクラスを作成するか、ノードを作成してキューに追加する方法を台無しにしたと思います。priorityQueue子供をatに追加しようとすると、 indexOutOfBounds も取得します
else if((priorityQueue.get(j).getG()+priorityQueue.get(j).getH()) > (child.getG()+child.getH())){
私のコードの残りの部分は以下の通りです：
EightPuzzle クラス
public class EightPuzzle{
static String[][] gameBoard = new String[3][3];
static String[][] finalGoalState = new String[3][3];
static int[] bLocation = new int[2];
String board;
String dir;
/*public void ReadFromTxt(String file) throws FileNotFoundException, IOException {
String read;
FileReader f = new FileReader(file);
int i = 0;
int j;
BufferedReader b = new BufferedReader(f);
System.out.println("Loading puzzle from file...");
while((read = b.readLine())!=null){
if(read.length()==3){
for(j=0;j<3;j++){
board[i][j] = (int)(read.charAt(j)-48);
}
}
i++;
}
b.close();
System.out.println("Puzzle loaded!");
}*/
public void setState(String board){
gameBoard[0][0] = board.substring(0,1);
gameBoard[0][1] = board.substring(1,2);
gameBoard[0][2] = board.substring(2,3);
gameBoard[1][0] = board.substring(4,5);
gameBoard[1][1] = board.substring(5,6);
gameBoard[1][2] = board.substring(6,7);
gameBoard[2][0] = board.substring(8,9);
gameBoard[2][1] = board.substring(9,10);
gameBoard[2][2] = board.substring(10,11);
System.out.println(Arrays.deepToString(gameBoard));
}
public static void setFinalGoalState(){
finalGoalState[0][0] = "b";
finalGoalState[0][1] = "1";
finalGoalState[0][2] = "2";
finalGoalState[1][0] = "3";
finalGoalState[1][1] = "4";
finalGoalState[1][2] = "5";
finalGoalState[2][0] = "6";
finalGoalState[2][1] = "7";
finalGoalState[2][2] = "8";
}
public static void setGoalState(){
gameBoard[0][0] = "b";
gameBoard[0][1] = "1";
gameBoard[0][2] = "2";
gameBoard[1][0] = "3";
gameBoard[1][1] = "4";
gameBoard[1][2] = "5";
gameBoard[2][0] = "6";
gameBoard[2][1] = "7";
gameBoard[2][2] = "8";
bLocation[0] = 0;
bLocation[1] = 0;
}
public void randomizeState(int numMoves){
setGoalState();
for(int i=0;i<numMoves;i++){
ArrayList<String> validMoves3 = isValidMove();
Random r = new Random();
int mIndex = r.nextInt(validMoves3.size());
String choice = validMoves3.get(mIndex);
move(choice);
System.out.println(Arrays.deepToString(gameBoard));
}
}
public ArrayList<String> isValidMove(){
ArrayList<String> validMoves = new ArrayList<String>();
if(bLocation[0] != 0){
//can move up
validMoves.add("up");
}
if(bLocation[0] != 2){
//can move down
validMoves.add("down");
}
if(bLocation[1] != 0){
//can move left
validMoves.add("left");
}
if(bLocation[1] != 2){
//can move right
validMoves.add("right");
}
return validMoves;
}
public void move(String dir){
ArrayList<String> validMoves2 = isValidMove();
if(validMoves2.contains("up") && dir.equals("up")){
String temp1 = new String();
temp1 = gameBoard[bLocation[0]-1][bLocation[1]];
gameBoard[bLocation[0]][bLocation[1]] = temp1;
gameBoard[bLocation[0]-1][bLocation[1]] = "b";
bLocation[0] = bLocation[0]-1;
}
else if(validMoves2.contains("down") && dir.equals("down")){
String temp2 = new String();
temp2 = gameBoard[bLocation[0]+1][bLocation[1]];
gameBoard[bLocation[0]][bLocation[1]] = temp2;
gameBoard[bLocation[0]+1][bLocation[1]] = "b";
bLocation[0] = bLocation[0]+1;
}
else if(validMoves2.contains("left") && dir.equals("left")){
String temp3 = new String();
temp3 = gameBoard[bLocation[0]][bLocation[1]-1];
gameBoard[bLocation[0]][bLocation[1]] = temp3;
gameBoard[bLocation[0]][bLocation[1]-1] = "b";
bLocation[1] = bLocation[1]-1;
}
else if(validMoves2.contains("right") && dir.equals("right")){
String temp4 = new String();
temp4 = gameBoard[bLocation[0]][bLocation[1]+1];
gameBoard[bLocation[0]][bLocation[1]] = temp4;
gameBoard[bLocation[0]][bLocation[1]+1] = "b";
bLocation[1] = bLocation[1]+1;
}
}
public static void printState(){
System.out.println(Arrays.deepToString(gameBoard));
}
public void getbLocation(){
for(int i=0; i<gameBoard.length; i++){
for(int j=0; j<gameBoard[i].length; j++){
if(gameBoard[i][j].equals("b"))
{
bLocation[0] = i;
bLocation[1] = j;
break;
}
}
}
System.out.println(Arrays.toString(bLocation));
}
public int heuristicOneHValue(){
int hValue = 0;
if(!gameBoard[0][0].equals("b")){
hValue++;
}
if(!gameBoard[0][1].equals("1")){
hValue++;
}
if(!gameBoard[0][2].equals("2")){
hValue++;
}
if(!gameBoard[1][0].equals("3")){
hValue++;
}
if(!gameBoard[1][1].equals("4")){
hValue++;
}
if(!gameBoard[1][2].equals("5")){
hValue++;
}
if(!gameBoard[2][0].equals("6")){
hValue++;
}
if(!gameBoard[2][1].equals("7")){
hValue++;
}
if(!gameBoard[2][2].equals("8")){
hValue++;
}
return hValue;
}
public void solveAstar(String heuristic){
setFinalGoalState();
ArrayList<Node> priorityQueue = new ArrayList<Node>();
int h = heuristicOneHValue();
if(heuristic.equalsIgnoreCase("h1"))
{
Node root = new Node(0,h,null,gameBoard);
priorityQueue.add(root);
while(priorityQueue != null){
Node currentNode = priorityQueue.get(0);
priorityQueue.remove(0);
gameBoard = currentNode.state;
ArrayList<String> moves = isValidMove();
for(int i = 0; i < moves.size(); i++){
move(moves.get(i));
Node child = new Node(currentNode.getG(),heuristicOneHValue(),currentNode,currentNode.getState());
for(int j = 0; j <= priorityQueue.size(); j++){
if(priorityQueue.size() == 0){
priorityQueue.add(0, child);
}
else if((priorityQueue.get(j).getG()+priorityQueue.get(j).getH()) > (child.getG()+child.getH())){
priorityQueue.add(j, child);
}
}
}
if(priorityQueue.get(0).getState() == finalGoalState){
priorityQueue = null;
}
}
}
//h2 here
}
public static void main (String[]args){
EightPuzzle b1=new EightPuzzle();
b1.setState("156 37b 284");
b1.getbLocation();
b1.solveAstar("h1");
}
}
ノード クラス
class Node {
public String[][] state;
public Node parent;
public int g;
public int h;
public Node(int g, int h, Node parent, String[][] state){
this.g = g;
this.h = h;
this.parent = parent;
this.state = state;
}
public String[][] getState(){
return state;
}
public int getG(){;
return g;
}
public int getH(){
return h;
}
public Node getParent(){
return parent;
}
public void setState(String[][] state){
this.state = state;
}
public void setG(int g){
this.g = g;
}
public void setH(int h){
this.h = h;
}
public void setParent(Node parent){
this.parent = parent;
}
}