有N个传教士和N个野人要过河，现在有一条船只能承载K个人（包括野人），K<N，在任何时刻，如果有野人和传教士在一起，必须要求传教士的人数多于或等于野人的人数。A*算法jave解决

这是一个经典的河流问题，可以使用A*算法来解决。

首先，我们需要定义状态空间和状态转移函数。在这个问题中，状态空间是所有可能的船上和河岸上的状态。每个状态由以下三个因素确定：左岸上的传教士数量，左岸上的野人数量和船的位置（左岸或右岸）。

状态转移函数是指从一个状态到另一个状态的转移。在这个问题中，转移的规则如下：

1. 船上最多只能有K个人。
2. 船只能从左岸到右岸或者从右岸到左岸。
3. 在任何时刻，如果有野人和传教士在一起，必须要求传教士的人数多于或等于野人的人数。

然后，我们需要定义启发函数。启发函数是一种估计从当前状态到目标状态的代价的函数。在这个问题中，我们可以使用以下启发函数：

1. 从左岸到右岸的传教士数量与野人数量的差异，因为我们的目标是在右岸上放置所有的传教士和野人，所以这个启发函数可以帮助我们快速找到一个可行的解决方案。
2. 船的位置，如果船在左岸上，这个启发函数的值为1，如果船在右岸上，这个启发函数的值为0。

最后，我们可以使用A*算法来搜索从初始状态到目标状态的最短路径。在这个算法中，我们需要维护一个优先队列，其中每个元素都是一个状态和其估计的代价。我们从初始状态开始，逐步扩展每个状态，直到找到目标状态。在扩展每个状态时，我们会计算其所有可能的后继状态，并将它们加入到优先队列中。

以下是Java代码的实现，其中State类表示一个状态，frontier是优先队列，heuristic是启发函数：

import java.util.*;

class State implements Comparable<State>{
    int m; // number of missionaries on left bank
    int c; // number of cannibals on left bank
    int b; // 0 for boat on left bank, 1 for boat on right bank

    public State(int m, int c, int b){
        this.m = m;
        this.c = c;
        this.b = b;
    }

    public boolean equals(Object o){
        State s = (State) o;
        return this.m == s.m && this.c == s.c && this.b == s.b;
    }

    public int hashCode(){
        return Objects.hash(m, c, b);
    }

    public int compareTo(State s){
        return this.m + this.c - s.m - s.c;
    }
}

public class RiverCrossing {
    PriorityQueue<State> frontier;
    Map<State, Integer> cost;
    Map<State, State> cameFrom;
    Map<State, Integer> heuristic;
    int K;

    public RiverCrossing(int K){
        this.K = K;
        frontier = new PriorityQueue<State>();
        cost = new HashMap<State, Integer>();
        cameFrom = new HashMap<State, State>();
        heuristic = new HashMap<State, Integer>();
    }

    public List<State> successors(State s){
        List<State> result = new ArrayList<State>();
        int mb = Math.min(s.m, K);
        int cb = Math.min(s.c, K);
        for(int i=0; i<=mb; i++){
            for(int j=0; j<=cb; j++){
                if(i+j == 0 || i+j > K) continue;
                if(i < j) continue;
                int new_m = s.m - i + (1-s.b)*i;
                int new_c = s.c - j + (1-s.b)*j;
                int new_b = 1 - s.b;
                State new_s = new State(new_m, new_c, new_b);
                result.add(new_s);
            }
        }
        return result;
    }

    public int distance(State s){
        return cost.getOrDefault(s, Integer.MAX_VALUE);
    }

    public void updateDistance(State s, int d){
        cost.put(s, d);
    }

    public int heuristic(State s){
        return heuristic.getOrDefault(s, 0);
    }

    public void updateHeuristic(State s){
        int h = Math.abs(s.m - s.c);
        if(s.b == 0) h += 1;
        heuristic.put(s, h);
    }

    public void aStar(State start, State end){
        frontier.offer(start);
        updateDistance(start, 0);
        updateHeuristic(start);
        while(!frontier.isEmpty()){
            State current = frontier.poll();
            if(current.equals(end)) break;
            for(State next : successors(current)){
                int newCost = distance(current) + 1;
                if(newCost < distance(next)){
                    updateDistance(next, newCost);
                    updateHeuristic(next);
                    cameFrom.put(next, current);
                    frontier.offer(next);
                }
            }
        }
    }

    public List<State> getPath(State start, State end){
        aStar(start, end);
        List<State> path = new ArrayList<State>();
        State current = end;
        while(!current.equals(start)){
            path.add(current);
            current = cameFrom.get(current);
        }
        path.add(start);
        Collections.reverse(path);
        return path;
    }

    public static void main(String[] args){
        RiverCrossing rc = new RiverCrossing(2);
        State start = new State(3, 3, 0);
        State end = new State(0, 0, 1);
        List<State> path = rc.getPath(start, end);
        for(State s : path){
            System.out.println(s.m + " " + s.c + " " + s.b);
        }
    }
}