# 智能算法实验：传教士和野人渡河

**Repository Path**: letere/crossRiver

## Basic Information

- **Project Name**: 智能算法实验：传教士和野人渡河
- **Description**: 智能算法的基本实验，用Java代码来实现，可以自定义渡河人数和船载人数
- **Primary Language**: Java
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2021-01-03
- **Last Updated**: 2024-03-12

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

### 一、问题描述
```text
有 N 个传教士和 N 个野人来到河边渡河，河岸有一条船，每次至多可供 k 人乘渡。
问：传教士为了安全起见，应如何规划摆渡方案，使得任何时刻， 河两岸以及船上的野人数目总是不超过传教士的数目(否则不安全，传教士有可能被野人吃掉)。 
即求解传教士和野人从左岸全部摆渡到右岸的过程中，任何时刻满足 M (传教土数) ≥ C 野人数)和 M+C≤k 的摆渡方案
```

---

### 二、代码实现
+ 参考代码：https://blog.csdn.net/joebug/article/details/78302544

#### 2.1 代码解析

+ (1) 根据人数和船限载数，计算出可行的渡河方案
```java
/**
 * 计算渡河方法
 * @return crossMethods
 */
public List<String> getCrossMethods(int missionarySize, int savageSize) {
    // 初始化数据，将传教士人数/野人数将为传的大小
    missionarySize = Math.min(missionarySize, boat);
    savageSize = Math.min(savageSize, boat);
    // 计算可行的渡河方法(全野人 | 全传教士 | 传教士>=野人)
    List<String> crossMethods = new ArrayList<>(16);
    for (int i=1; i<=savageSize; i++) {
        crossMethods.add(0 + " " + i);
    }
    for (int i=1; i<=missionarySize; i++) {
        crossMethods.add(i + " " + 0);
    }
    for (int i=1; i<=savageSize; i++) {
        for (int j=i; j<=Math.min(missionarySize, boat-i); j++) {
            crossMethods.add(j + " " + i);
        }
    }
    return crossMethods;
}
```

+ (2)递归执行渡河，若成功渡河，记录渡河方案
```java
/**
 * 递归渡河
 * @param riverStatus 两岸状态
 * @param history 两岸状态历史数据
 * @param operations 操作信息
 */
public void recursionCrossRiver(RiverStatus riverStatus, List<RiverStatus> history, List<String> operations) {
    // 判断是否被吃
    if (isEat(riverStatus)) {
        return;
    }
    // 判断重复操作
    if (isRepeat(riverStatus, history)) {
        return;
    }
    // 判断是否完成（完成则记录操作方案）
    if (isFinish(riverStatus)) {
        List<String> riverWay = Arrays.asList(new String[operations.size()]);
        Collections.copy(riverWay, operations);
        crossRiverWays.add(riverWay);
        return;
    }
    // 获取渡河方法
    List<String> crossMethods;
    if (Objects.equals(riverStatus.getBoat(), 1)) {
        crossMethods = getCrossMethods(riverStatus.getMissionaryLeft(), riverStatus.getSavageLeft());
    } else {
        crossMethods = getCrossMethods(riverStatus.getMissionaryRight(), riverStatus.getSavageRight());
    }
    // 无可行的渡河方法（结束递归）
    if (crossMethods.size() == 0) {
        return;
    }
    // 递归遍历渡河方法
    String operation = "";
    RiverStatus currentState;
    for (String crossMethod : crossMethods) {
        // 按空格切割字符串，s[0]为传教士数，s[1]为野人数
        String[] s = crossMethod.split(" ");
        // 渡河
        currentState = copyRiverStatus(riverStatus);
        operation = crossRiver(currentState, Integer.parseInt(s[0]), Integer.parseInt(s[1]));
        operations.add(operation);
        history.add(currentState);
        // 递归渡河
        this.recursionCrossRiver(currentState, history, operations);
        // 递归回溯清除数据
        operations.remove(operations.size() - 1);
        history.remove(history.size() - 1);
    }
}
```