Я пытаюсь решить проблему 8 ферзей с помощью алгоритма восхождения на холм.У меня проблема с методом «generate_node» (этот метод дает узел, генерирует всех его соседей) следующего класса.В частности, проблема заключается в обновлении матрицы узла «родитель», но я не прогнозировал это обновление в своей реализации.Это обновление вызывает неправильное создание дочерних узлов.
package algoritmi_ricerca_locale;
import java.util.*;
public class Hill_Climbing {
private final Node root;
public Hill_Climbing(Node root){
this.root=root;
}
public Node getRoot(){
return root;
}
public List<Node> generate_child(Node parent){
List<Node> node_list=new LinkedList<>();
char [][] child_state;
for (int j=0;j<8;j++){
for (int i=0;i<8;i++){
if (parent.getState()[i][j]==' '){
int count_conf=0;
child_state=parent.getState();
for(int t=0;t<8;t++){
if(child_state[t][j]=='*'){
child_state[t][j]=' ';
break;
}
}
child_state[i][j]='*';
for (int m=0;m<8;m++){
for (int n=0;n<8;n++){
if(child_state[n][m]=='*'){
for(int k=m+1;k<8;k++){
if(child_state[n][k]=='*'){
count_conf++;
}
}
for (int h=n+1,k=m+1;h<8 && k<8;h++,k++){
if(child_state[h][k]=='*'){
count_conf++;
}
}
for (int h=n-1,k=m+1;h>0 && k<8;h--,k++){
if(child_state[h][k]=='*'){
count_conf++;
}
}
}
}
}
node_list.add(new Node(count_conf,child_state));
}
else{
continue;
}
}
}
System.out.println(node_list.size());
return node_list;
}
public Node choose_Node (List<Node> a,int fobj){
int min=fobj;
int index=-1;
System.out.println(a.size());
for(int i=0;i< a.size();i++){
if(a.get(i).getFunc_Obj()<min){
min=a.get(i).getFunc_Obj();
index=i;
}
}
if(index==-1){
return null;
}
else{
return a.get(index);
}
}
public Node algorithm(){
Node selected_node=new Node() ;
if ( root.getFunc_Obj()==0){
System.out.println("Root=Goal");
getRoot();
}
else {
List <Node> neighbours;
selected_node =root;
neighbours= generate_child(selected_node);
while (choose_Node(neighbours,selected_node.getFunc_Obj())!=null){
selected_node=choose_Node(neighbours,selected_node.getFunc_Obj());
if (selected_node.getFunc_Obj()==0){
System.out.println("Goal state trovato");
return selected_node;
}
neighbours.clear();
neighbours= generate_child(selected_node);
}
}
System.out.println("Goal state non trovato");
return selected_node;
}
}
Узел класса следующий:
public class Node {
private int func_obj;
private char state [][];
public Node(){
}
public Node(int func_obj, char [][] state){
this.func_obj=func_obj;
this.state=state;
}
public int getFunc_Obj(){
return func_obj;
}
public char [][] getState(){
return state;
}
}
РЕДАКТИРОВАТЬ Я попытался выполнить отладку, и когда я изменяю child_state, такжеparent.getState () изменен, они имеют одинаковые ссылки на память (в начале метода «generate_child ()» я назначаю parent.getState () для child_state).Как я могу передать значение, возвращаемое parent.getState () (то есть матрицу), в child_state, не обновляя при этом состояние родителя?