深度优先算法的应用——农夫过河问题_算法农夫

本文原载于我的博客，地址：https://blog.guoziyang.top/archives/27/

农夫过河问题也算是个老问题了，小学的时候经常出现在奥数教材上，和鸡兔同笼一起（笑），但是原理可比鸡兔同笼高端多了。

我们看下题目：

农夫需要把狼、羊、菜和自己运到河对岸去，只有农夫能够划船，而且船比较小，除农夫之外每次只能运一种东西，还有一个棘手问题，就是如果没有农夫看着，羊会偷吃菜，狼会吃羊。请考虑一种方法，让农夫能够安全地安排这些东西和他自己过河。

我们在图结构这一章遇到了这个题目，就要思考怎么使用图相关的知识解决这个问题。

有一种比较有趣的抽象方法：状态抽象法，可用于解决这类问题。

我们将某一时刻的状态单独抽象出来，用一组布尔变量去表示这个状态。我们规定，某一时刻，如果农夫在河对岸，那么表示农夫的布尔变量就置为true，菜、山羊和狼同理。

我们规定，某一时刻的状态表示为（狼, 羊, 菜, 农夫）。两个状态之间就是可以相互转化的，如$(false,false,false,false)$和$(false,false,true,true)$这两个状态就是可以转化的，代表着“农夫带着菜过到了河对岸”。于是，整个过程就转化为了状态之间的转换。

现在，我们将状态抽象为图中的结点，那么状态间的转化就可以抽象为结点间的有向路。我们的任务就变成了在起始与结束状态间找到一条有向路即可。

以下是Node结点类的设计：

class Node {
    private boolean wolf;
    private boolean sheep;
    private boolean vegetable;
    private boolean farmer;
    public int index;
    public int flag = 0;

    public Node(boolean wolf, boolean sheep, boolean vegetable, boolean farmer) {
        this.wolf = wolf;
        this.sheep = sheep;
        this.vegetable = vegetable;
        this.farmer = farmer;
    }

    public void setIndex(int index) {
        this.index = index;
    }

    public int getIndex() {
        return index;
    }

    public boolean getWolf() {
        return wolf;
    }

    public boolean getSheep() {
        return sheep;
    }

    public boolean getVegetable() {
        return vegetable;
    }

    public boolean getFarmer() {
        return farmer;
    }
}
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

每个结点就是一个状态。

我们首先遍历所有的状态结点，如果是有效的，就添加到结点列表，以下是验证结点有效的代码，根据题目的描述，在农夫和羊的状态不同的情况下（羊没有农夫看着），狼不能和羊状态一样，羊不能和菜一样：

private static boolean isValid(boolean wolf, boolean sheep, boolean vegetable, boolean farmer) {
    if((farmer != sheep) && ((wolf == sheep) || (sheep == vegetable))) {
        return false;
    } else {
        return true;
    }
}
1
2
3
4
5
6
7

接着添加所有的状态有效的结点：

boolean booleans[] = new boolean[]{true, false};
for(boolean wolf : booleans) {
    for(boolean sheep : booleans) {
        for(boolean vegetable : booleans) {
            for(boolean farmer : booleans) {
                if(isValid(wolf, sheep, vegetable, farmer)) {
                    Node node = new Node(wolf, sheep, vegetable, farmer);
                    node.setIndex(nodes.size());
                    nodes.add(node);
                }
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

结点之间的连接状态是由邻接矩阵存储的，判断两个结点是否能连接使用canConnect方法，每次农夫可以带一样东西过河：

private static boolean canConnect(Node i, Node j) {
    int change = 0;
    if(i.getWolf() != j.getWolf()) change ++;
    if(i.getSheep() != j.getSheep()) change ++;
    if(i.getVegetable() != j.getVegetable()) change ++;
    if(i.getFarmer() != j.getFarmer() && change <= 1) {
        return true;
    }
    return false;
}
1
2
3
4
5
6
7
8
9
10

最后二重循环遍历判断每两个结点是否可连接：

edges = new int[nodes.size()][nodes.size()];
for(int i = 0; i < nodes.size(); i ++) {
    for(int j = 0; j < nodes.size(); j ++) {
        if(canConnect(nodes.get(i), nodes.get(j))) {
            edges[i][j] = 1;
        } else {
            edges[i][j] = 0;
        }
    }
}
1
2
3
4
5
6
7
8
9
10

完成了图的构建之后，使用暴力深度优先搜索即可，简单粗暴，注意，如果只想要搜出一条路即可，那么在搜索到之后直接退出即可，而如果想要搜出所有的路，则需要使用栈。

searchWay函数初始化一些参数，并且找到了初始状态结点（所有的都不在对岸）和结束状态结点（所有的都在对岸）：

private static void searchWay() {
    int firstNodeIndex = 0;
    int lastNodeIndex = 0;
    for(int i = 0; i < nodes.size(); i ++) {
        Node tempNode = nodes.get(i);
        if(!tempNode.getFarmer() && !tempNode.getSheep() &&   !tempNode.getVegetable() && !tempNode.getWolf()) {
            firstNodeIndex = i;
        }
        if(tempNode.getFarmer() && tempNode.getSheep() &&  tempNode.getVegetable() && tempNode.getWolf()) {
            lastNodeIndex = i;
        }
    }
    DFS(nodes.get(firstNodeIndex), nodes.get(lastNodeIndex));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

DFS方法是一个递归的深度优先搜索方法：

private static void DFS(Node startNode, Node lastNode) {
    stack.push(startNode);
    visit[startNode.index] = true;
    while(!stack.isEmpty()) {
        int tempNodeIndex = stack.getTop().getIndex();
        if(tempNodeIndex == lastNode.index) {
            results.add(stack.getList());
            stack.pop();
            visit[lastNode.index] = false;
            break;
        }
        while(startNode.flag < nodes.size()) {
            if(edges[tempNodeIndex][startNode.flag] == 1 && !visit[startNode.flag]) {
                DFS(nodes.get(startNode.flag), lastNode);
            }
            startNode.flag ++;
        }
        if(startNode.flag == nodes.size()) {
            stack.pop();
            startNode.flag = 0;
            visit[startNode.index] = false;
            break;
        }
    }
}
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

每个结点都有一个flag字段，用来标示当前结点已经搜索到和哪一个结点的连接，visit数组用于表示结点是否被访问过。

最终，results数组中就存有所有的路，你需要做的就只是将结果输出而已，我把输出结果格式化了一下：

private static void showResult() {
    for(int i = 0; i < results.size(); i ++) {
        System.out.println("第" + (i+1) + "种答案");
        ArrayList<Node> result = results.get(i);
        for(int j = 0; j < result.size() - 1; j ++) {
            Node before = result.get(j);
            Node after = result.get(j + 1);
            StringBuilder builder = new StringBuilder("农夫");
            if(before.getSheep() != after.getSheep()) {
                builder.append("带着羊");
            }else if(before.getWolf() != after.getWolf()){
                builder.append("带着狼");
            }else if(before.getVegetable() != after.getVegetable()) {
                builder.append("带着菜");
            }else {
                builder.append("什么都不带");
            }
            if(after.getFarmer()) {
                builder.append("过到对岸。");
            }else {
                builder.append("回到原岸。");
            }
            System.out.println(builder.toString());
        }
        System.out.println();
    }
}
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

运行结果：

GuodeMacBook-Air:DS04_Farmer guoziyang$ java Main
第1种答案
农夫带着羊过到对岸。
农夫什么都不带回到原岸。
农夫带着狼过到对岸。
农夫带着羊回到原岸。
农夫带着菜过到对岸。
农夫什么都不带回到原岸。
农夫带着羊过到对岸。

第2种答案
农夫带着羊过到对岸。
农夫什么都不带回到原岸。
农夫带着菜过到对岸。
农夫带着羊回到原岸。
农夫带着狼过到对岸。
农夫什么都不带回到原岸。
农夫带着羊过到对岸。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18