Java Heuristic Search

I’m trying to write a heuristic search for a River problem. The problem is, I have X people with X weight and X can sail the raft, and they all have to get from 1 side of the river to the other.

I attempted to write the following;

    public int heuristic(State state){

    PersonState sState = (PersonState) state;


        return sState.isGoal() ? 0 : Collections.max(sState.listPersonsSouth).getWeight();
    else {
        return sState.isGoal() ? 0 : Collections.min(sState.listPersonsNorth).getWeight();


This gets me to 1 node off of the expected answer and cost-wise 1 move off.

I’m aware that the code doesn’t really check the current state vs the goal state but I’m unsure how to write that.

Any suggestions on an alternative method or any adjustments I could make would be much appreciated!

Leave a Reply

1 Comment threads
0 Thread replies
Most reacted comment
Hottest comment thread
1 Comment authors
Jason Recent comment authors
newest oldest most voted
Notify of

Have you tried averaging the weight? Since the raft can only hold <= X amount of people, and also can only hold <= Y amount of weight, you could attempt to take the heaviest person(s) and group them with the lightest person(s) in an attempt to bring the average weight per person on the raft to optimal levels (optimal being the max weight the raft can hold / the max amount of people the raft can hold). It could look something like this (writing pseudo code since I don’t have your full code): Raft raft = getRaft(); Double maxWeight =… Read more »