Last active
May 28, 2022 17:16
-
-
Save rkdgusrn1212/88b33b5b07256e0aacf1339168b32921 to your computer and use it in GitHub Desktop.
A-star model in java
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.PriorityQueue; | |
import java.util.ArrayList; | |
class Model{ | |
private class State implements Comparable<State>{ | |
int value; | |
int pathCost; | |
@Override | |
public int compareTo(State state){ | |
if(value<state.value){ | |
return -1; | |
}else if(value>state.value){ | |
return 1; | |
}else{ | |
return 0; | |
} | |
} | |
} | |
private class Action{ | |
State state; | |
State successor; | |
int cost; | |
} | |
PriorityQueue<State> mQueue = new PriorityQueue<>(); | |
void start(){ | |
State initialState = new State(); | |
initialState.pathCost = 0; | |
initialState.value = getHeu(initialState); | |
mQueue.offer(initialState); | |
while(!mQueue.isEmpty()){ | |
State state = mQueue.poll(); | |
if(isGoal(state)){ | |
//결과를 어떻게 할까요? | |
break; | |
}else{ | |
ArrayList<Action> actions = getActions(state); | |
for(Action action : actions){ | |
State successor = getSuccessor(state,action); | |
mQueue.offer(successor); | |
} | |
} | |
} | |
} | |
private ArrayList<Action> getActions(State state){ | |
ArrayList<Action> actions = new ArrayList<>(); | |
/*state에서 할수있는 action들을 추가하세요 | |
Action action = new Action(); | |
action.cost = ?; | |
action.successor = ?; | |
actions.add(action); | |
*/ | |
return actions; | |
} | |
private State getSuccessor(State state, Action action){ | |
State successor = new State(); | |
successor.pathCost = state.pathCost + action.cost; | |
successor.value = getValue(successor); | |
return successor; | |
} | |
private int getValue(State state){ | |
return state.pathCost + getHeu(state); | |
} | |
private int getHeu(State state){ | |
int heu=0; | |
//휴리스틱을 정의하세요 | |
return heu; | |
} | |
private boolean isGoal(State state){ | |
return state.value == state.pathCost; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment