狼羊过河模型

思维训练：“过河”智力题
趣味思维
看题目：
一个农民带着一头狼、一只山羊和一篮子白菜去赶集。

他遇到一条河，河边有一条小船。

他一次只能把一样东西带到船上。

狼和羊不能留在一起，同样羊和白菜也不能留在一块，原因很明显。

还好，狼不喜欢吃白菜。

那么，农民怎样才能把这三样东西都带过河呢？
一题多变1
继续提醒：
独立思考先
上面那个题目
我小时候做过
感觉挺有趣的！
把这个题目变化一下：
三只羊，三只狼过河。

有一条船，般上最多放两只动物。

狼的数量多于羊的数量时，羊会被吃掉。

请问怎样才能都过河？
趣味题
许多辅导书籍都为孩子提供了值得尝试的经典数学趣味题。

但就我个人角度而言，最好的教育方式不在于让孩子去做那些所谓“超水平”的数学题，或者去买一些数学相关方面的书籍让他们来阅读。

我们的培养目标是让孩子自主地形成数学思维，并学会去提问题，鼓励孩子将他们的想法付诸实践。

我们应该能够发现，市面上常见的思维题、趣味题、智力游戏类的书籍，并不完全适合孩子、辅助孩子。

我的目标是：选择孩子们适合的趣味思维题目，以此促进和提升孩子的思维能力。

一题多变2
把上面的题目再变化一下：
三只狼、三只羊过河，船上必须有一只羊，船上最多能有两只动物，狼比羊多时，狼会吃羊，该怎样过河？。

农夫过河——狼⽺菜问题
话说⼀位农夫带着⼀只狼、⼀只⽺和⼀个卷⼼菜过河，⽆奈船⼩，农夫每次只能运送⼀样东西，考虑到狼吃⽺、⽺吃菜，因此运送的顺序⾄关重要。

在现实世界⾥解决这个问题并不困难，相信很多⼈都已经有了答案，但是如何⽤程序来解决这⼀问题，就需要动动脑筋了。

这⼜是⼀个与移动物品有关的问题，在前⾯汉诺塔的例⼦中，我们已经领略了解决这类问题的⽅法，⼤致分为三个步骤：
1. 将现实问题转化为数学问题，即，建⽴模型；
2. 将数学问题转化为程序问题，即，给出数据结构及算法；
3. 编写程序解决问题。

下⾯我们就沿着这样的思路来寻找问题的答案。

阅读原⽂。

人、狼、羊、菜安全渡河问题安全渡河问题又称作“人狼羊菜”问题，其具体描述为：一个人带着一条狼、一只羊、一筐白菜过河但由于船太小，人一次只能带一样东西乘船过河。

狼和羊、羊和白菜不能单独留在同岸，否则羊或白菜会被吃掉。

该问题可使用图论中的最短路算法进行求解。

问题分析根据题意，人不在场时，狼要吃羊，羊要吃菜，因此，人不在场时，不能将狼与羊、羊与菜留在河的任一岸。

可用四维向量v=（m，n，p，q）来表示状态，m表示人，n代表狼，p代表羊，q代表白菜，且m,n,p,q ∈{0,1},0代表在对岸，1代表在此岸。

例如，状态（0,1,1,0）表示人和菜在对岸，而狼和羊在此岸，这时人不在场，狼要吃羊，因此，这个状态是不可行的。

通过穷举法将所有可行的状态列举出来，可行的状态有（1,1,1,1）,（1,1,1,0）,（1,1,0,1）,（1,0,1,1）,（1,0,1,0）,（0,1,0,1）,（0,1,0,0）,（0,0,1,0）,（0,0,0,1）,（0,0,0,0）。

可行状态共有十种。

每一次的渡河行为改变现有的状态。

现构造赋权图G=(V,E,W),其中顶点集V={v1,…, v10}中的顶点（按照上面的顺序编号）分别表示上述１０个可行状态，当且仅当对应的两个可行状态之间存在一个可行转移时两顶点之间才有边连接，并且对应的权重取为１，当两个顶点之间不存在可行转移时，可以把相应的权重取为∞。

因此问题变为在图Ｇ中寻找一条由初始状态（１,１,１,１）出发，经最小次数转移到达最终状态（０,０,０,０）的转移过程，即求从状态（１,１,１,１）到状态（０,０,０,０）的最短路径。

该问题难点在于计算邻接矩阵，由于摆渡一次就改变现有状态，为此再引入一个四维状态转移向量，用它来反映摆渡情况。

用１表示过河，０表示未过河。

例如，（１,１,０,０）表示人带狼过河。

状态转移只有四种情况，用如下向量表示：（１,０,０,０），（１,１,０,０），（１,０,１,０），（１,０,０,１）现在规定状态向量与转移向量之间的运算为0+0=0,1+0=1,0+1=1,1+1=0通过上面的定义，如果某一个可行状态加上转移向量得到的新向量还属于可行状态，则这两个可行状态对应的顶点之间就存在一条边。

过河问题引言过河问题是一类经典的数学逻辑问题，涉及到河岸上有一群人/动物需要通过一条狭窄且危险的河流，但只有一艘小船。

这个问题涉及到一系列规则和条件，并要求找到一种最优的解决方案，使得所有人/动物都能够安全地通过河流。

这个问题可以被视为一种思维训练，有助于提高逻辑推理和问题解决能力。

问题描述在典型的过河问题中，通常会有一群人/动物（如农夫、狼、羊、菜）需要通过一条河流。

以下是一个典型的问题描述：- 河岸上有一个农夫、一只狼、一只羊和一颗菜。

- 这个小船只能够携带农夫以及一样其他物品。

- 如果农夫不在场，狼会吃掉羊，羊会吃掉菜。

- 目标是将所有的人/动物都安全地从一岸带到另一岸，而不违反上述条件。

解决方案为了解决这个过河问题，需要找到一个安全且合理的船运策略。

以下是一个可能的解决方案：1. 农夫将羊带到另一岸，然后返回原岸。

2. 农夫将菜带到另一岸，然后把羊带回原岸。

3. 农夫将狼带到另一岸，然后返回原岸。

4. 农夫将羊带到另一岸。

在这个解决方案中，农夫每次都会携带一只人/动物过河，并在返回时如果出现潜在的危险，则在另一岸留下该人/动物。

通过这种方式，可以确保没有任何一种组合会出现危险情况。

思考扩展过河问题可以被进一步扩展和改变，以增加难度和挑战性。

以下是一些可能的扩展：1. 添加更多的人物/动物：例如，增加一只狗和一个猫到过河问题中。

这样会增加更多的可能性和限制条件，使得解决方案更加复杂。

2. 调整规则和条件：可以根据需要调整问题的规则和条件，以提供更多的难度和挑战性。

例如，可以添加时间限制或改变特定物品之间的关系。

3. 使用不同的交通工具：除了小船之外，也可以考虑使用其他交通工具，如桥梁、绳索等。

这些不同的工具可能会改变问题的解决方案。

实际应用过河问题虽然是一个数学逻辑问题，但它可以反映现实生活中的许多情况。

例如，在项目管理中，团队需要合作解决一系列问题，每个问题都有特定的限制和条件。

通过训练逻辑思维和解决问题的能力，可以更好地应对实际挑战。

协调博弈经典例子
协调博弈是研究有限次博弈的多项和双方决策的一种博弈。

它特
别适用于两个或多个参与者都具有相似利益的博弈，即每个人都想得
到最大利益、最大回报。

它是基于一种“否定协商”思想，即每个参
与者都希望达到最佳解，但他们都不能做出任何让步。

在这样的情况下，他们改为寻找一种使双方共赢的协议，而不是让步。

经典例子之
一是《狼与羊》：
在狼与羊的协调博弈中，有三位参与者：一只狼和两只羊，它们
共享同一条河岸。

在一个传统的中等游戏里，如果狼在一边，羊就在
另一边，它们都无法过河。

但如果狼和羊同时过河，那么就可以减少
对方的食物供给。

在这种情况下，狼将是最大赢家，因为它可以捕捉
一只羊，而羊不能捕捉狼。

如果羊们过河，但狼并未过河的话，羊们
至少可以保护自己，但它们也没有任何收获。

因此，参与者必须要做
出一个让大家都满意的决定，而狼和羊都有各自的目的，这就是“协调”的目的。

解决狼与羊的协调博弈的方法有两种：第一种是使用一个正数表
示羊们的奖励，而将负数用作代价以阻止狼过河；第二种是发放羊群
奖励给狼，让它们放弃捕捉羊，而不要过河。

根据上述解决方案，可
以得出一个最优解：狼获得一定的报酬，而羊们则没有损失，即满足
了双方的利益。

因此，经典的协调博弈例子“狼与羊”可以用来说明，做出最优决策的前提是双方能够共同协商来达成一致，而不是以胜者
为准。

狼羊草过河问题描述•一位农夫带了狼、羊、草，准备过河。

可是小船每次只能容下农夫和一件物品。

渔民不在时，狼会吃羊、羊会吃草。

而且，我们假设，狼或羊在农夫不在时不会自己跑掉或被人牵走且农夫会划船。

要求我们设计一个方案，使人、狼、羊、草都能安全过河。

问题分析及假设过河问题相当于状态的转移。

初状态是人，狼，羊，草均在此岸，目标终状态是人，狼，羊，草均在对岸。

定义以下两种向量表示状态的转移：•状态向量：用四维向量(人，狼，羊，草)表示人，狼，羊，草各自的状态，记“在此岸”时各分量为“1”，否则为“0”。

例如：(1，1，1，1)表示人，狼，羊，草均在此岸，(0，0，0，0)表示人，狼，羊，草均在对岸。

•运载向量：用四维向量(人，狼，羊，草)表示他们各自被运载的情况，记“被运载”时各分量为“1”，否则记为“0”。

例如：(1，1，0，0)表示被运载的是人和狼，又如(1，0，1，0)表示被运载的是人和羊。

模型定义根据题设要求，在满足系统限定条件下，可得以下状态向量和运载向量集合：•用S表示所有允许状态向量的集合，则S={(1，1，1，1)，(1，1，1，0)，(1，1，0，1)，(1，0，1，1)，(1，0，1，0)，(0，1，0，1)，(0，0，0，1)，(0，0，1，0)，(0，1，0，0)，(0，0，0，0)}•用D表示所有允许运载向量的集合，则D={(1，0，0，0)，(1，1，0，0)，(1，0，1，0)，(1，0，0，1)}状态转移方程：原状态⊕运载=现状态运算规则：1+1=0，1+0=1，0+1=1，0+0=0可取状态向量允许运载方式：可取状态向量+ 可取运载向量=模型求解(1，1，0，0)(1，0，1，0)(1，0，0，1)(1，0，0，0)1.(1，1，1，1) += (0，0，1，1)×= (0，1，0，1)√= (0，1，1，0)×= (0，1，1，1)×(1，1，0，0)(1，0，1，0)(1，0，0，1)(1，0，0，0)2.(0，1，0，1) += (1，0，0，1)×= (1，1，1，1) ×= (1，1，0，0)×= (1，1，0，1)√解法一：初始状态（1，1，1，1）经多次运载状态变化成最终状态（0，0，0，0）(1，1，0，0)(1，0，1，0)(1，0，0，1)(1，0，0，0)3.(1，1，0，1) += (0，0，0，1)√= (0，1，1，1) ×= (0，1，0，0)√= (0，1，0，1)√(1，1，0，0)(1，0，1，0)(1，0，0，1)(1，0，0，0)4.1. (0，0，0，1) += (1，1，0，1)√= (1，0，1，1) √= (1，0，0，0)×= (1，0，0，1)×(1，1，0，0)(1，0，1，0)(1，0，0，1)(1，0，0，0)4.2.(0，1，0，0) += (1，0，0，0)×= (1，1，1，0) √= (1，1，0，1)√= (1，1，0，0)×4.3. (0，1，0，1)与上述第二步重复，必定不是最优解，故不用进行下去。

⼈狼⽺菜过河问题的解法及代码⼈狼⽺菜问题是计算机领域中的经典问题。

之所以经典，⼀⽅⾯这是编译原理等课程中的⼀个建模及编码问题，另⼀⽅⾯也经常被作为智⼒题⽤在⾯试中。

本⽂讨论的是怎么建模、编码的问题。

问题描述：⼀个农夫有⼀条船，和狼、⽺、菜，农夫要把这3样东西运到河到另⼀边，农夫每次最多只能通过这个船运⼀样东西，要防⽌狼吃⽺、⽺吃⽩菜（即不能在没有农夫在的情况下同时在同⼀岸边），该怎么过？该问题的解决分为2个阶段，第⼀阶段是对状态建模，第⼆阶段是⽤⼴度遍历来找到问题的解。

其中⼴度遍历阶段和“量⽔问题”的⼴度遍历解法类似。

问题抽象：建⽴⼀个struct型的state，其中包括4个bool型的变量a1 a2 a3 a4分别对应⼈、狼、⽺、菜的状态，值为true代表在起始的河岸边，false代表在对岸，起始时4个分量都为true。

农夫每过⼀次河⽣成⼀个新的state。

根据题⽬可知，农夫过⼀次河a1取反，且a2 a3 a4值与a1相同的分量也可以分别取反分别⽣成⼀个新的state代表被农夫运到河的对岸的各种选择。

只有a1取反⽽a2 a3 a4都没取反⽣成的新状态代表农夫⾃⼰过河没有带东西。

每次⽣成⼀个新状态后，⾸先要检查是否达到了终⽌状态（a1 a2 a3 a4都为false），其次要检查是否是合法状态（要同时考虑⼀个state对应的河两岸是否有狼吃⽺、⽺吃⽩菜的情况出现），如果状态合法、没到终⽌状态且没有在⼴度遍历队列中出现过，则将状态插⼊⼴度遍历队列，否则将该状态丢弃。

在此过程中我们没有考虑正在渡河的情况，因为每次过河船上总是有⼈，不会出现冲突，视其为不稳定状态直接忽略。

代码如下：#include<iostream>using namespace std;#define MAX 500struct state{bool a1,a2,a3,a4;int parentId;//⽤于回溯输出解决步骤state(){a1 = a2 = a3 = a4 = true;//true表⽰在A地（起始岸边）parentId=-1;}};bool equal(state& astate,state& bstate){if(astate.a1==bstate.a1&&astate.a2==bstate.a2&&astate.a3==bstate.a3&&astate.a4==bstate.a4){return true;}return false;}void assign(state& astate,state& bstate){astate.a1=bstate.a1;astate.a2=bstate.a2;astate.a3=bstate.a3;astate.a4=bstate.a4;astate.parentId = bstate.parentId;}state currentState;state sQueue[MAX];int startPos = 0;int endPos = 1;bool isInQueue(state& newState){for(int i=0;i<endPos;i++){if(equal(newState,sQueue[i])){return true;}}return false;}bool isValidState(state& newState){//总共可能有16种状态。

农夫过河问题是一个经典的人工智能搜索问题，其中一个农夫需要将一只狼、一只羊和一颗白菜从一侧河岸运到另一侧。

在此过程中，农夫要保证狼不吃羊，羊不吃白菜。

邻接矩阵是一种表示图形数据的方法，它可以用矩阵的形式来表示节点之间的关系。

对于农夫过河问题，我们可以将其表示为一个有向图，其中每个节点表示一个状态，每个边表示两个状态之间的转换。

设农夫、狼、羊、白菜分别用F、W、S、C表示，每个状态都包含四个元素的二进制数，表示它们是否在左侧河岸。

例如，初始状态可以表示为(1,1,1,1)，即FWSC都在左侧河岸。

下面是农夫过河问题的邻接矩阵：(1,1,1 ,1) (0,1,0,1)(0,0,0,1)(0,0,0,0)(1,0,1,0)(1,0,0,0)(1,1,0,1)(1,1,0,0)(1,1,1,1)0 0 0 0 0 0 0 0(0,1,0,1)0 0 1 0 0 0 1 0(0,0,0,1)0 0 0 0 0 0 0 1(0,0,0,0)0 0 0 0 1 0 0 0(1,0,1,0)0 0 1 0 0 1 0 0(1,0,0,0)0 0 0 1 0 0 0 0(1,1,0,1)0 0 0 0 0 0 0 0(1,1,0,0)0 0 0 0 0 0 0 0在该邻接矩阵中，每个元素(i, j)表示从状态i到状态j是否存在一条转移边。

例如，第二行第三列的元素为1，表示从状态(1,1,1,1)到状态(0,0,0,1)存在一条转移边。

注意到邻接矩阵是对称的，即(i, j)和(j, i)的值相同，因为我们可以反过来将船驶回去。

同时，由于初始状态和最终状态都在左侧河岸，因此它们之间的转移边值都为0。