图论与渡河问题

大家好，我是南海一号。今天给大家讲一个关于图论的非常有趣的问题。这个问题大家想必都知道，但是它和图论有什么关系呢？就让我给大家讲一下。

问题：某人带狼羊以及一筐蔬菜过河，小船需要人滑动，而且每次只能带一样东西（羊，狼，或者蔬菜）。而且人不在场时，狼会吃羊，羊会吃菜。请问这个人应该如何过河？

大家一看到这个问题，恐怕都笑了。这样的问题太简单，我小学就会做。只需要用到枚举法，心算都能算出来。

但今天，我们需要把这个问题抽象成一个数学问题。首先，我们需要用一个向量来存储这个人和三件东西的状态，状态只有两种，此岸和彼岸。我们用一个四维向量来存储，人或者物在此岸为1，在彼岸为0。那么我们就可以存储所有的状态了，[x1,x2,x3,x4]。这就是那个四维向量。x1表示人，x2表示狼，x3 表示羊，x4表示蔬菜。，

例如[1,1,0,0]表示人和狼在此岸，羊和蔬菜在彼岸。下面就是这个问题抽象后的图。Node1代表都在此岸。Node10代表都在彼岸。我们需要从Node1到达Node10。

接下来，我们就要表示出所有可行的状态了，因为三件东西都不能有损失，所以有些状态是不行的，比如[1,1,0,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)；

这些状态都是可行的。

显然，我们的目标就是让所有的东西安全过河，也就是(1,1,1,1)到（0,0,0,0）。

下面见证奇迹的时候到了，这玩意怎么和图论沾上关系呢！

我们只需要将这些可行状态看作节点就可以了，有人说：“不对，图论还有边呢，你这个图的边在哪里？”

不要慌，请看下面。

我们来构造转移状态，我们也用一个四维向量来表示转移状态，转移状态表示在当前这一步中，有那几样东西（人）在渡河。我们用1表示渡河，用0表示不渡河。同样的，在[y1,y2,y3,y4]中，y1表示人，y2表示狼，y3 表示羊，y4表示蔬菜。因为y1(人）每次都要划船.所以y1=1恒成立，例如[1,1,0,0]表示人带着狼从河的一边到另一边。

模拟渡河的过程需要用到异或运算：即0+0=0,1+0=1,0+1=1,1+1=0。对于0+0=0，第一个0表示此物的可行状态，第二个0表示此物的转移状态，这个算式的意思是：在彼岸（0）的物体在这一次运输中没有上船（0），结果0表示这个东西还在彼岸。1+0=1表示此岸（1）的东西没上船（0），结果还在此岸（1）。0+1=1表示彼岸（0）的东西上了船（1），到达了此岸（1）1+1表示此岸（1）的东西上了船（1）。到达了彼岸（0）。

哈哈哈，现在，图的节点和边都有了。只需要画出这个图了。然后根据这个图找出[1,1,1,1]到[0,0,0,0]的最短路径，就可以了。找出最短路径可以用一个简单的工具箱：graphshortestpath（）。

在这里留下一道课后题：有三只母狮子带着她们的小狮子过河。三只母狮子都会划船，三只小狮子只有一个会划船。船一次只能带两只狮子，当母狮子与自己的小狮子分开时。别的母狮子会吃掉这个小狮子。请问：这些狮子应该怎么过河？

下面是我的关于羊和狼的代码：

a=[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]; %每一行是一个可行状态
b=[1 0 0 0;1 1 0 0;1 0 1 0;1 0 0 1]; %每一行是一个转移状态
w=zeros(10); %邻接矩阵初始化
for i=1:9
    for j=i+1:10
        for k=1:4
            if findstr(mod(a(i,:)+b(k,:),2),a(j,:))
                w(i,j)=1;
            end
        end
    end
end
w=w'; %变成下三角矩阵
[i,j,v]=find(w);  %找非零元素
c=sparse(i,j,v,10,10) %构造稀疏矩阵
[x,y,z]=graphshortestpath(c,1,10,'Directed',false)  % 该图是无向图
h = view(biograph(c,[],'ShowArrows','off','ShowWeights','off'));
Edges = getedgesbynodeid(h); %提取句柄h中的边集
set(Edges,'LineColor',[0 0 0]); %为了将来打印清楚，边画成黑色
set(Edges,'LineWidth',1.5);  %线型宽度设置为1.5

参考文献：数学建模算法与应用（司守奎，孙兆亮）

图片来源：由Irana Nasrin在pixabay上发布