Java 启发式搜索

Question

我正在尝试编写一个针对河流问题的启发式搜索。问题是，我有 X 个人，体重 X，可以驾驶木筏，他们都必须从河的一侧到达另一侧。

我尝试写以下内容； https://pastebin.com/h4adeVnv

    public int heuristic(State state){

    PersonState sState = (PersonState) state;

    if(sState.isBoatIsSouth()){

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

}

这让我比预期答案少了 1 个节点，并且在成本方面也少了 1 个节点。

我知道代码并没有真正检查当前状态与目标状态，但我不确定如何编写。

任何有关替代方法的建议或我可以做出的任何调整将不胜感激!

Answer 1

您尝试过平均重量吗？由于筏只能容纳 <= X 的人，并且只能容纳 <= Y 的重量，因此您可以尝试将最重的人与最轻的人分组，以尝试使木筏上每人的平均重量达到最佳水平(最佳是木筏可容纳的最大重量/木筏可容纳的最大人数)。

它可能看起来像这样(编写伪代码，因为我没有完整的代码):

Raft raft = getRaft();
Double maxWeight = raft.getMaxWeight();
Double maxCapacity = raft.getMaxCapacity();
People[] people = getAllPeople();
Double optimalWeight = maxCapacity / maxWeight;
while(people > 0){
Person heaviestPerson = people.getHeaviestPerson();
Person lightestPerson = people.getLightestPerson();
Person secondLightestPerson = people.getSecondLightestPerson();

if((optimalWeight * 3 - (heaviestPerson.weight + lightestPerson.weight + secondLightestPerson.weight))
 < (optimalWeight * 2 - (heaviestPerson.weight + lightestPerson.weight))){
    raft.add(heaviestPerson);
    raft.add(lightestPerson);
    people.remove(heaviestPerson); 
    people.remove(lightestPerson);
}else{
    raft.add(heaviestPerson);
    raft.add(secondLightestPerson);
    raft.add(lightestPerson);
    people.remove(heaviestPerson); 
    people.remove(lightestPerson);
    people.remove(secondLightestPerson);
}
}

如果您将最重和最轻的人配对，您将从最佳体重中删除方差最大的人，并将所述方差抵消为更“正常”。当你这样做时，将人员添加到筏中会变得越来越容易，因为当你删除每个具有高方差的人时，你会留下更接近最佳权重的人。

您也可以使用给出的方法进一步优化它(也可能检查第二重的人，等等)