2

我目前正在研究一个使用适应度函数解决 15 个难题的项目。有3种健身功能可以使用，

  1. 适应度函数1= 1 - （错位棋子数/棋子总数）；
  2. 适应度函数2 = 1-（所有错位瓷砖距离目标位置的距离之和/64）
  3. 适应度函数3=（适应度2+适应度1）/2

求解器旨在搜索提高适应度函数 VALUE 的可能移动，直到解决整个拼图板（其中适应度函数 = 1）。我在尝试生成动作时备货，因为求解器会打印不成功的搜索路线以及实际路线，例如 W,S,W,N,S,N,S,N,S,N,S,N,S,N,S ,N,S,N （顺序相反），表示 NWSW。然而，求解器来回搜索多次，并打印出不需要的路线。我想在递归中排除以前访问过的位置，并且只打印有效的移动而不是不成功的移动。代码如下：

<pre><code>
enter code here

package Definitions;

public class Puzzle {
public TreeNode boardsTree;
public Boolean searching;
public int lastPos;


Puzzle(Board b) {
 boardsTree = new TreeNode(b);
 lastPos = b.Blank_pos;
}

public String solver(Board b, String route, int level, double fitVal){
//System.out.println("route in the level " + level +": " +route + " Fitness: ");                          
//System.out.print(b.f1.getFitnessVal()); 
//If the depth of the Tree is level 15 or Board is solved return route(moves e.g. WNS)
if(level == 15||b.solved){
//if(route != ""){
//if(route.length()>1){
// return route.substring(0, route.length()-1);
//}else{
return route;
//}
}else{
//Create a temporary store for the last position 
//Create four auxilliary puzzle boards has child puzzles
//Perform the different moves on the blank space on each board in different directions      
//(N=0,S=1,E=2,W=3)
lastPos = b.Blank_pos;
Board auxN = new Board(4,b.tilesList);
Board auxS = new Board(4,b.tilesList);
Board auxE = new Board(4,b.tilesList);
Board auxW = new Board(4,b.tilesList);
//Builds the tree

//MOVES TO NORTH
//b.isValidMove(North=0,South=1,East=2,West=3)
if( b.isValidMove(0)){ 
 //If the lastPosition (blankPosition in the parent board) is not the position of the  
 //cell in the north MoveBlank to North
 if(lastPos != (lastPos - 4)){
 auxN.MoveBlank(0);
 boardsTree.addSon(0,auxN);
 if(fitVal > boardsTree.getSon(0).getState().f1.getFitnessVal()){
  auxN.print();
  searching = false;
  return route + "N"; 
    }
   }
  }

//MOVES TO SOUTH
//b.isValidMove(North=0,South=1,East=2,West=3)
if( b.isValidMove(1) ){ 
 //If the lastPosition (blankPosition in the parent board) is not the position of the  
 //cell in the north MoveBlank to North
if(lastPos != (lastPos + 4)){
 auxS.MoveBlank(1);
 boardsTree.addSon(1,auxS);
 if(fitVal > boardsTree.getSon(1).getState().f1.getFitnessVal()){
  auxS.print();
  searching = false;
  return route + "S"; 
   }
  }
 }

 //MOVES TO EAST
 if( b.isValidMove(2) ){
    if(lastPos != (lastPos + 1)){
       auxE.MoveBlank(2);
       boardsTree.addSon(2,auxE);
       if(fitVal > boardsTree.getSon(2).getState().f1.getFitnessVal()){
       auxE.print();
       searching = false;
       return route + "E";
     }
    }
   }

//MOVES TO WEST
if( b.isValidMove(3) ){ 
if(lastPos != (lastPos -1)){
 auxW.MoveBlank(3);
 boardsTree.addSon(3,auxW);
 if(fitVal > boardsTree.getSon(3).getState().f1.getFitnessVal()){
  auxW.print();
  searching = false;
  return route + "W"; 
  }
 }
}

//EVALUATE NEW STATES

if(searching && b.isValidMove(0)){
  System.out.println("Actual: " +auxN.Blank_pos+ " Previo: "+lastPos );
  if(lastPos != auxN.Blank_pos){
     lastPos = auxN.Blank_pos;
     route = solver(auxN,route + "N", level+1, fitVal); //NORTH
     }else{
     //If  a solution is not generated enter a recursion to find further solutions at a    
     //further depth of the tree
     solver(auxN,route, level+1, fitVal); //NORTH
          }
 }
 if(searching  && b.isValidMove(1)){
  //System.out.println("Actual: " +auxS.Blank_pos+ " Previo: "+lastPos );
  if(lastPos != auxS.Blank_pos){
    lastPos = auxS.Blank_pos;
    route =solver(auxS,route + "S", level+1, fitVal); //NORTH
  }else{
    solver(auxS,route, level+1, fitVal); //NORTH
      }
 }
 if(searching  && b.isValidMove(2)){
   //System.out.println("Actual: " +auxE.Blank_pos+ " Previo: "+lastPos );
   if(lastPos != auxE.Blank_pos){
   lastPos = auxE.Blank_pos;
   route = solver(auxE,route + "E", level+1, fitVal); //NORTH
   }else{
   solver(auxE,route, level+1, fitVal); //NORTH
        }
   }
   if(searching  && b.isValidMove(3)){
    //System.out.println("Actual: " +auxW.Blank_pos+ " Previo: "+lastPos );
     if(lastPos != auxW.Blank_pos){
     lastPos = auxW.Blank_pos;
     route =solver(auxW,route + "W", level+1, fitVal); //NORTH
     }else{
     solver(auxW,route, level+1, fitVal); //NORTH
           }
      }
     }
     return route;

     }
     }
4

0 回答 0