I have a State object and a QueueList of State objects. I am implementing the BFS algorithm, so each State have a doule cost in it. The problem is, sometimes i want to see if cost from the current State to a specific State, is smaller then the cost i already addedd to the State in former path.
but I can't access praticular State's in the PriorityQueue!! this is the State object:
public class State<T> implements Comparable<T> {
private T state;
private double cost;
private State<T> cameFrom;
public State(T state)
{
this.state=state;
}
public double getCost() {
return cost;
}
public void setCost(double cost) {
this.cost = cost;
}
public State<T> getCameFrom() {
return cameFrom;
}
public void setCameFrom(State<T> cameFrom) {
this.cameFrom = cameFrom;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((state == null) ? 0 : state.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
State other = (State) obj;
if (state == null) {
if (other.state != null)
return false;
} else if (!state.equals(other.state))
return false;
return true;
}
public T getState() {
return state;
}
@Override
public int compareTo(Object arg0) {
@SuppressWarnings("unchecked")
double cost1=(( State<T>)arg0).cost;
if(cost<cost1)
return -1;
if(cost>cost1)
return 1;
return 0;
}
}
now, sometimes there is a State in the openList and a State that comes from getAllPossibleStates - Which the state field is equals, but the cost is not! (because getAllPossibleStates allocate a new State, which i havn't updated the cost field yet)
public Solution search(Searchable s)
{
openList.add(s.getInitialState());
HashSet<State> closedSet = new HashSet<State>();
while(openList.size()>0)
{
State n = popOpenList();
closedSet.add(n);
if(n.equals(s.getGoalState()))
{
return backTrace(n,s.getInitialState());
}
ArrayList<State> successors = s.getAllPossibleStates(n);
for(State state:successors)
{
if(closedSet.contains(state)==true)
continue;
if(openList.contains(state)==false)
{
state.setCameFrom(n);
state.setCost(n.getCost()+1);
openList.add(state);
}
//state is coming from successors - but if it is coming from successeros, the cost field is 0 always, and i want to access the cost i already updated once from a former path.
else if(n.getCost()+1<state.getCost())
{
state.setCost(n.getCost()+1);
state.setCameFrom(n);
if(!openList.contains(state))
{
openList.add(state);
}
}
}
}
return null;
}
i hope you understand my problem.
Aucun commentaire:
Enregistrer un commentaire