1
\$\begingroup\$

I am currently using the BestFirst algorithm to solve the puzzle 15. It works well when I have a simple inputs and takes about 1-20 seconds to solve the puzzle. But when it comes to complicated inputs, it might takes forever to run. I'm just wondering if there is any way to improve my algorithm's performance.

Main.java

final int _ = 0;
State initialState = new State(
_,  1, 4,  2,  
9,  5, 3,  12, 
8,  6, 7, 11, 
14, 10, 13, 15);

cList open = new cList();
cList closed = new cList();
open.InsertFront(initialState);

while(!open.isEmpty()){
   State st = open.RemoveFront();
   closed.InsertBack(st);
   if(st.isGoal()) {showPath(st); break;}
   State[] ss = st.NextStates();
   for(State s:ss){
      if(!closed.isExist(s))
         if(!open.ExistOrSubstitue(s))
            open.InsertSorted(s);
    }
 }

cList

private ArrayList<State> list = new ArrayList<State>(1000);
public void InsertFront(State s){ list.add(0,s); }
public void InsertBack(State s){ list.add(s);}
public State RemoveFront(){ return list.remove(0); }
public boolean isEmpty(){ return list.isEmpty(); }
public void InsertSorted(State s){
  int i=0;
  while(i<list.size()){
    if(list.get(i).compareTo(s)>0) break;
    i++;
  }
  list.add(i,s);
}

public boolean isExist(State s){
  for(Object state:list) if (state.equals(s)) return true;
  return false;
}

public boolean ExistOrSubsitute(State s){
  for(int i=0;i<list.size();i++){
    State state =list.get(i);
    if(state.equals(s)) {
        if(s.getEV()<state.getEV()){
          list.remove(i);
          InsertSorted(s);
        }
        return true;
    }
  }
  return false;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.