个人博客
0%

【智能算法】实验：传教士过河

发表于

智能算法基本实验之一：传教士，野人渡河问题的Java解决方案（自定义人数）

一、问题描述

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

二、代码实现

2.1 代码优化(Java)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
//记录河两岸状态的类
public class RiverState {
    private int missionaryLeft; //左岸传教士数量
    private int savageLeft; //左岸野人数量

    private int missionaryRight; //右岸传教士数量
    private int savageRight; //右岸野人数量

    private int boat; //船的位置，左1，右-1;

    //构造器
    public RiverState(){};
    public RiverState(int missionaryLeft, int savageLeft, int missionaryRight, int savageRight, int boat) {
        this.missionaryLeft = missionaryLeft;
        this.savageLeft = savageLeft;
        this.missionaryRight = missionaryRight;
        this.savageRight = savageRight;
        this.boat = boat;
    }

    //get、set方法
    public int getMissionaryLeft() {
        return missionaryLeft;
    }
    public void setMissionaryLeft(int missionaryLeft) {
        this.missionaryLeft = missionaryLeft;
    }
    public int getSavageLeft() {
        return savageLeft;
    }
    public void setSavageLeft(int savageLeft) {
        this.savageLeft = savageLeft;
    }
    public int getMissionaryRight() {
        return missionaryRight;
    }
    public void setMissionaryRight(int missionaryRight) {
        this.missionaryRight = missionaryRight;
    }
    public int getSavageRight() {
        return savageRight;
    }
    public void setSavageRight(int savageRight) {
        this.savageRight = savageRight;
    }
    public int getBoat() {
        return boat;
    }
    public void setBoat(int boat) {
        this.boat = boat;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
//优化后算法，可以自定义渡河人数，以船限载人数
public class CrossRiver {
    private int count = 0; //记录方案种类

    private int person; //传教士、野人人数（保持相同）
    private int boat; //船限载人数（小于person数）

    //构造器
    public CrossRiver(int person, int boat) {
        this.person = person;
        this.boat = boat;
    };

    /**
     * 计算渡河方法
     * @return crossMethods
     */
    public List<String> getCrossMethods() {
         List<String> crossMethods = new ArrayList<>();
         for(int i=0; i<=person; i++) { //传教士数
             for(int j=0; j<=person; j++) { //野人数
                 if(i != 0 || j !=0) { //过河必须有人，不能两者为0
                     if(i+j <= boat) {
                         crossMethods.add(i + " " + j);
                     }
                 }
             }
         }
         return crossMethods;
    }

    /**
     * 运河，并返回运河操作信息
     * @param riverState 两岸状态
     * @param missionary 运送传教士数
     * @param savage 运送野人数
     * @return 操作信息
     */
    private String acrossRiver(RiverState riverState, int missionary, int savage) {
        //初始状态信息（记录操作）
        String startState = "[左：传" + riverState.getMissionaryLeft() + ", 野" + riverState.getSavageLeft() + "] | " +
                "[右：传" + riverState.getMissionaryRight() + ", 野" + riverState.getSavageRight() + "]";

        //以船在左岸为基准，右移为正，左移为负
        int direction = riverState.getBoat();
        //修改传教士数
        if (missionary > 0) {
            riverState.setMissionaryLeft(riverState.getMissionaryLeft() - missionary * direction);
            riverState.setMissionaryRight(riverState.getMissionaryRight() + missionary * direction);
        }
        //修改野人数
        if (savage > 0) {
            riverState.setSavageLeft(riverState.getSavageLeft() - savage * direction);
            riverState.setSavageRight(riverState.getSavageRight() + savage * direction);
        }
        //修改船的状态
        riverState.setBoat(-riverState.getBoat());

        //结束状态信息（记录操作）
        String endState = "[左：传" + riverState.getMissionaryLeft() + ", 野" + riverState.getSavageLeft() + "] | " +
                "[右：传" + riverState.getMissionaryRight() + ", 野" + riverState.getSavageRight() + "]";
        //操作信息
        String operation = "";
        if (riverState.getBoat() == 1) {
            operation = " <---（传" + missionary + ", 野" + savage + "）---- ";
            return endState + operation + startState;
        } else {
            operation = " ----（传" + missionary + ", 野" + savage + "）---> ";
            return startState + operation + endState;
        }
    }

    /**
     * 判断数据是否出错，会出现负数情况
     * @param riverState 两岸状态
     * @return true/false
     */
    private boolean isWrong(RiverState riverState) {
        if (riverState.getMissionaryLeft() < 0 || riverState.getSavageLeft() < 0
                || riverState.getMissionaryRight() < 0 || riverState.getSavageRight() < 0) {
            return true;
        }
        return false;
    }

    /**
     * 判断是否发生吃人
     * @param riverState 两岸状态
     * @return true/false
     */
    private boolean isEat(RiverState riverState) {
        //判断左岸
        if (riverState.getMissionaryLeft() < riverState.getSavageLeft() && riverState.getMissionaryLeft() != 0) {
            return true;
        }
        //判断右岸
        if (riverState.getMissionaryRight() < riverState.getSavageRight() && riverState.getMissionaryRight() != 0) {
            return true;
        }
        return false;
    }

    /**
     * 判断是否达成目标
     * @param riverState 两岸状态
     * @return true/false
     */
    private boolean isFinish(RiverState riverState) {
        if (riverState.getMissionaryLeft() == 0
                && riverState.getSavageLeft() == 0
                && riverState.getBoat() == -1) {
            return true;
        }
        return false;
    }

    /**
     * 复制对象（对象作为参数是地址引用，修改对象时最好复制一份，方便还原）
     * @param riverState 两岸状态
     * @return RiverState
     */
    private RiverState copyRiverState(RiverState riverState) {
        return new RiverState(
                riverState.getMissionaryLeft(),
                riverState.getSavageLeft(),
                riverState.getMissionaryRight(),
                riverState.getSavageRight(),
                riverState.getBoat()
        );
    }

    /**
     * 判断是否重复操作（即：左向右传2野人， 右向左也传2野人，死循环）
     * @param riverState 两岸状态
     * @param history    历史数据
     * @return true/false
     */
    private boolean isRepeat(RiverState riverState, List<RiverState> history) {
        for (int i = 0; i < history.size() - 1; i++) { //遍历历史数据，查看是否有重复数据，有重复数据及循环回原点
            if (riverState.getMissionaryLeft() == history.get(i).getMissionaryLeft()
                    && riverState.getSavageLeft() == history.get(i).getSavageLeft()) {
                if (riverState.getBoat() == history.get(i).getBoat()) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 算法主程序（只有此为public）
     * @param riverState
     * @param history
     * @param operations
     */
    public void run(RiverState riverState, List<RiverState> history, List<String> operations) {
        //判断数据是否出错
        if (isWrong(riverState)) {
            return;
        }
        //判断是否被吃
        if (isEat(riverState)) {
            return;
        }
        //判断重复
        if (isRepeat(riverState, history)) {
            return;
        }
        //判断是否完成
        if (isFinish(riverState)) {
            count ++;
            System.out.println("第" + count + "种渡河方法：");
            for (String operation : operations) {
                System.out.println(operation); //打印操作
            }
            System.out.println();
            return;
        }

        String message = "";
        RiverState currentState = new RiverState();
        List<String> crossMethods = getCrossMethods();

        for (String crossMethod : crossMethods) { //遍历渡河方法
            String[] s = crossMethod.split(" "); //按空格切割字符串，s[0]为传教士数，s[1]为野人数
            
            currentState = copyRiverState(riverState); //创建一个新对象，用于修改后不影响原对象
            message = acrossRiver(currentState, Integer.valueOf(s[0]), Integer.valueOf(s[1]));//调用渡河方法
            operations.add(message); //新增记录用数据
            history.add(currentState);
            run(currentState, history, operations); //递归
            operations.remove(operations.size() - 1); //递归失败后清除新增的数据，恢复原样
            history.remove(history.size() - 1);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
//调用算法运行
public class Main {
    public static void main(String[] args) {
        RiverState riverState = new RiverState(3, 3, 0, 0, 1);
        List<RiverState> history = new ArrayList<>();
        history.add(riverState); //把初始状态添加到历史状态中
        List<String> operations = new ArrayList<>();

        CrossRiver crossRiver = new CrossRiver(3, 2); //经典3传教士，3野人，船限载2人问题
        crossRiver.run(riverState, history, operations);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
运行结果：
第1种渡河方法：
[左：传3, 野3] | [右：传0, 野0] ----（传0, 野2）---> [左：传3, 野1] | [右：传0, 野2]
[左：传3, 野2] | [右：传0, 野1] <---（传0, 野1）---- [左：传3, 野1] | [右：传0, 野2]
[左：传3, 野2] | [右：传0, 野1] ----（传0, 野2）---> [左：传3, 野0] | [右：传0, 野3]
[左：传3, 野1] | [右：传0, 野2] <---（传0, 野1）---- [左：传3, 野0] | [右：传0, 野3]
[左：传3, 野1] | [右：传0, 野2] ----（传2, 野0）---> [左：传1, 野1] | [右：传2, 野2]
[左：传2, 野2] | [右：传1, 野1] <---（传1, 野1）---- [左：传1, 野1] | [右：传2, 野2]
[左：传2, 野2] | [右：传1, 野1] ----（传2, 野0）---> [左：传0, 野2] | [右：传3, 野1]
[左：传0, 野3] | [右：传3, 野0] <---（传0, 野1）---- [左：传0, 野2] | [右：传3, 野1]
[左：传0, 野3] | [右：传3, 野0] ----（传0, 野2）---> [左：传0, 野1] | [右：传3, 野2]
[左：传0, 野2] | [右：传3, 野1] <---（传0, 野1）---- [左：传0, 野1] | [右：传3, 野2]
[左：传0, 野2] | [右：传3, 野1] ----（传0, 野2）---> [左：传0, 野0] | [右：传3, 野3]

第2种渡河方法：
[左：传3, 野3] | [右：传0, 野0] ----（传0, 野2）---> [左：传3, 野1] | [右：传0, 野2]
[左：传3, 野2] | [右：传0, 野1] <---（传0, 野1）---- [左：传3, 野1] | [右：传0, 野2]
[左：传3, 野2] | [右：传0, 野1] ----（传0, 野2）---> [左：传3, 野0] | [右：传0, 野3]
[左：传3, 野1] | [右：传0, 野2] <---（传0, 野1）---- [左：传3, 野0] | [右：传0, 野3]
[左：传3, 野1] | [右：传0, 野2] ----（传2, 野0）---> [左：传1, 野1] | [右：传2, 野2]
[左：传2, 野2] | [右：传1, 野1] <---（传1, 野1）---- [左：传1, 野1] | [右：传2, 野2]
[左：传2, 野2] | [右：传1, 野1] ----（传2, 野0）---> [左：传0, 野2] | [右：传3, 野1]
[左：传0, 野3] | [右：传3, 野0] <---（传0, 野1）---- [左：传0, 野2] | [右：传3, 野1]
[左：传0, 野3] | [右：传3, 野0] ----（传0, 野2）---> [左：传0, 野1] | [右：传3, 野2]
[左：传1, 野1] | [右：传2, 野2] <---（传1, 野0）---- [左：传0, 野1] | [右：传3, 野2]
[左：传1, 野1] | [右：传2, 野2] ----（传1, 野1）---> [左：传0, 野0] | [右：传3, 野3]

第3种渡河方法：
[左：传3, 野3] | [右：传0, 野0] ----（传1, 野1）---> [左：传2, 野2] | [右：传1, 野1]
[左：传3, 野2] | [右：传0, 野1] <---（传1, 野0）---- [左：传2, 野2] | [右：传1, 野1]
[左：传3, 野2] | [右：传0, 野1] ----（传0, 野2）---> [左：传3, 野0] | [右：传0, 野3]
[左：传3, 野1] | [右：传0, 野2] <---（传0, 野1）---- [左：传3, 野0] | [右：传0, 野3]
[左：传3, 野1] | [右：传0, 野2] ----（传2, 野0）---> [左：传1, 野1] | [右：传2, 野2]
[左：传2, 野2] | [右：传1, 野1] <---（传1, 野1）---- [左：传1, 野1] | [右：传2, 野2]
[左：传2, 野2] | [右：传1, 野1] ----（传2, 野0）---> [左：传0, 野2] | [右：传3, 野1]
[左：传0, 野3] | [右：传3, 野0] <---（传0, 野1）---- [左：传0, 野2] | [右：传3, 野1]
[左：传0, 野3] | [右：传3, 野0] ----（传0, 野2）---> [左：传0, 野1] | [右：传3, 野2]
[左：传0, 野2] | [右：传3, 野1] <---（传0, 野1）---- [左：传0, 野1] | [右：传3, 野2]
[左：传0, 野2] | [右：传3, 野1] ----（传0, 野2）---> [左：传0, 野0] | [右：传3, 野3]

第4种渡河方法：
[左：传3, 野3] | [右：传0, 野0] ----（传1, 野1）---> [左：传2, 野2] | [右：传1, 野1]
[左：传3, 野2] | [右：传0, 野1] <---（传1, 野0）---- [左：传2, 野2] | [右：传1, 野1]
[左：传3, 野2] | [右：传0, 野1] ----（传0, 野2）---> [左：传3, 野0] | [右：传0, 野3]
[左：传3, 野1] | [右：传0, 野2] <---（传0, 野1）---- [左：传3, 野0] | [右：传0, 野3]
[左：传3, 野1] | [右：传0, 野2] ----（传2, 野0）---> [左：传1, 野1] | [右：传2, 野2]
[左：传2, 野2] | [右：传1, 野1] <---（传1, 野1）---- [左：传1, 野1] | [右：传2, 野2]
[左：传2, 野2] | [右：传1, 野1] ----（传2, 野0）---> [左：传0, 野2] | [右：传3, 野1]
[左：传0, 野3] | [右：传3, 野0] <---（传0, 野1）---- [左：传0, 野2] | [右：传3, 野1]
[左：传0, 野3] | [右：传3, 野0] ----（传0, 野2）---> [左：传0, 野1] | [右：传3, 野2]
[左：传1, 野1] | [右：传2, 野2] <---（传1, 野0）---- [左：传0, 野1] | [右：传3, 野2]
[左：传1, 野1] | [右：传2, 野2] ----（传1, 野1）---> [左：传0, 野0] | [右：传3, 野3]