因此,我正在研究这个3x3游戏,其中为您提供了当前状态,例如:
1 5 6
3 7分
2 8 4
并且您希望达到以下目标状态:
1 2
3 4 5
6 7 8
因此,我在下面发布的代码中编写了所有其他方法。我现在遇到的问题是我实际的A *搜索。我想使用两种启发式方法,一种用于检查在错误的位置有多少个片段(例如,启发式函数将显示当前状态在错误的位置具有H = 8个片段),另一种启发式将计算距离多远总的总和是(因此,对于我当前的状态,第一部分是1个移开,第二部分是3个移开,依此类推,所有这些的总和就是我的H值)。因此,我将我的gameBoard
记录在字符串数组中。
所以现在是我的实际问题。如下所示,除了我的A *以外的所有东西都在工作。
首先,我叫setFinalGoalState()
,使它成为变量finalGoalState
,以便可以将当前状态与目标状态进行比较。
然后,我制作一个priorityQueue
,应该是ArrayList
的Node
,其中每个节点将具有一个G值(G是它在树中的距离),H值,对父级的引用以及当前州。
因此,首先我调用一个初始huesticOneHValue()
以获得我的第一个状态的H值。然后,我为“ h1”运行一个if
语句(这只是我的第一个启发式方法,正如我所说的,稍后再添加一个)。然后,它应该创建一个初始节点Root
,它将是我在树中的第一个节点,并将其添加到优先级队列中。
然后,它应该在优先级队列中运行。它将当前节点作为priorityQueue
中的第一个元素,然后将其从队列中删除。它将我的实际gameBoard
设置为与当前节点相同的gameBoard
状态。然后,它创建一个可能移动的ArrayList
(调用isValidMoves()
,它检查您是否可以实际向上,向下,向左或向右移动,然后将其放在列表中)。然后,我进行一个for循环以遍历所有可能移动的大小,然后通过调用move()
方法进行实际移动(因此,对int i = 0
的第一次调用将调用move上移,因为您可以移动b然后在当前状态下创建一个Node
子对象,其中包含我所在的位置gValue
(应该等于1),新的H值(在某些情况下,该值可能保持不变,但应朝降低H值),其父级(我认为应该是currentNode
?),然后是currentNode
的状态(板的外观)。
然后,下一个for循环检查以查看将其放置在优先级队列中的位置。 g+h
值较小的节点应该放在队列的前面,因为我们要先检查它们是否达到目标状态。因此,如果队列为空,则将其设置为初始条件,以将其添加到最前面,否则它将检查priorityQueue
处的j
是否大于子代的g+h
,如果是,则子代获得最后,在完成所有移动之后,它检查j
的前节点状态是否等于我们的目标状态,并且如果不是,它将返回while循环的前面并再次运行。
我认为最终我在用节点搞砸了一些东西。进行调试时,我发现每次生孩子时,父节点的状态都会更新为孩子的状态,这不会发生,因为孩子应该是父母的某个举动(上,下,左,或正确)。我想我弄乱了一些东西来创建节点类或创建节点并将其添加到队列中的方式。当我尝试将我的孩子添加到priorityQueue
时,我也得到了indexOutOfBounds
else if((priorityQueue.get(j).getG()+priorityQueue.get(j).getH()) > (child.getG()+child.getH())){
我的其余代码如下:
八级拼图
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;
}
}
参考方案
首先,我不知道我是否已经完全理解您的问题,但是如果我是对的,那么您所说的节点状态并没有什么不同。
如果是这种情况,那么您的问题就在此行中:
Node child = new Node(currentNode.getG(),heuristicOneHValue(),currentNode,currentNode.getState());
您将在不同节点之间共享指向状态对象的指针,因此您需要使用状态副本。我认为,Node类中的getState方法将是制作副本的最佳位置,因此,当其他对象修改状态时,可以避免任何进一步的问题。
例:
public String[][] getState(){
String[][] returnState = new String[this.state.length][this.state[0].length];
for (int i = 0; i < this.state.length; i++) {
for (int j = 0; j < this.state[0].length; j++) {
returnState[i][j] = this.state[i][j];
}
}
return returnState;
}
Java Double与BigDecimal - java我正在查看一些使用双精度变量来存储(360-359.9998779296875)结果为0.0001220703125的代码。 double变量将其存储为-1.220703125E-4。当我使用BigDecimal时,其存储为0.0001220703125。为什么将它双重存储为-1.220703125E-4? 参考方案 我不会在这里提及精度问题,而只会提及数字…
当回复有时是一个对象有时是一个数组时,如何在使用改造时解析JSON回复? - java我正在使用Retrofit来获取JSON答复。这是我实施的一部分-@GET("/api/report/list") Observable<Bills> listBill(@Query("employee_id") String employeeID); 而条例草案类是-public static class…
Java-父类正在从子类中调用方法? - java抱歉,我还是编码的新手,可能还没有掌握所有术语。希望您仍然能理解我的问题。我想得到的输出是:"Cost for Parent is: 77.77" "Cost for Child is: 33.33" 但是,我得到这个:"Cost for Parent is: 33.33" "Cost f…
Java Map,如何将UTF-8字符串正确放置到地图? - java我有一个地图,LinkedHashMap更确切地说。我想在上面放一个字符串对象。然后,我读取此值以查看实际存储的内容。字符串本身具有非ASCII字符(西里尔文,韩文等)。将其放到地图上然后阅读后,这些字符将替换为??? s。一些代码:Map obj = new LinkedHashMap(); System.out.println("name: &…
java.net.URI.create异常 - javajava.net.URI.create("http://adserver.adtech.de/adlink|3.0") 抛出java.net.URISyntaxException: Illegal character in path at index 32: http://adserver.adtech.de/adlink|3.0 虽然n…