【算法思想】过河问题(续)

​ 前一篇文章用人、狗、鸡、米过河问题介绍了解决过河问题的普适解决方法以及其改进算法。本文先用该算法解决我们常见的六只老虎过河问题，然后用特殊方法解决另外一种过河问题。

六只老虎过河问题：

问题描述：有三只大虎( A , B , C ) 和三只小虎(a , b, c) , 正好母子三对。要过一条河, 岸边有一条船, 一次最多只能载两只虎. 今知三只大虎和小虎a 能划船。限制条件是,只有自已的母虎在身边, 小虎才能与其他母虎同船、同岸或岸边遭遇, 不然会被吃掉请问怎样往返渡船, 才能使六只虎平安过河？

问题分析：这是一个具有趣味性的数学问题，答案有多个，方法也可以不同。用上一篇文章中的算法来分析：我们可以用一个六维向量来表示所有可能的状态向量，用一个二维向量来表示船上状态的运算向量。过河就是这些可能的状态向量与运算向量进行异或运算。我们用前一篇文章的图论法来解决的话，就是将每一个状态向量作为图的一个顶点，如果一个状态向量能够与另一个状态向量能够通过与运算向量(有限制)相乘得到，就将这两个状态向量用一条边连接起来，这样我们就可以得到一个图。

问题解决：我们可以枚举出可能的状态向量和运算向量：

运算变量： c =

1 1 0 0 0 0

1 0 1 0 0 0

0 1 1 0 0 0

1 0 0 1 0 0

0 1 0 0 1 0

0 0 1 0 0 1

0 0 0 1 1 0

0 0 0 1 0 1

1 0 0 0 0 0

0 1 0 0 0 0

0 0 1 0 0 0

0 0 0 1 0 0

状态向量：ab =

1 1 1 1 1 1

1 1 1 1 1 0

1 1 1 1 0 1

1 1 1 0 1 1

1 1 1 1 0 0

1 1 1 0 0 1

1 1 1 0 1 0

1 1 1 0 0 0

1 1 0 1 1 0

1 0 1 1 0 1

0 1 1 0 1 1

0 0 0 0 0 0

0 0 0 0 0 1

0 0 0 0 1 0

0 0 0 1 0 0

0 0 0 0 1 1

0 0 0 1 1 0

0 0 0 1 0 1

0 0 0 1 1 1

0 0 1 0 0 1

0 1 0 0 1 0

1 0 0 1 0 0

有了状态变量和运算变量后，我们就可以根据前面的算法构造图，然后通过图的最短路径算法求解得到，由于时间有限，并且前一篇文章已经实现，我就不再实现了。下面讲一下，算法中应该注意的地方：

1、考虑运算变量的选取限制

for i=1:length(ab)%ab是状态向量的集合
    result(:,:,i)=xor(repmat(ab(i,:),12,1),c);%将ab(i,:)的内容复制12遍，从而与c的维数相同，并且进行异或运算
    [x(i,:),y(i,:)]=ismember(result(:,:,i),ab,'rows');%判断异或运算的结果向量是否在可能的状态变量中
    %下面的方法是考虑运算变量选取的限制问题
    mark=[];
    for j=1:length(c)
        a1=find(ab(i,:));%找到状态向量中为1的位置
        a2=find(ab(i,:)==0);%找到状态向量中为0的位置
        if(sum(c(j,a1)>=1)&&sum(c(j,a2)>=1))%这里是运算变量的限制条件
            mark=[mark j];%将不符合条件的向量标记出来
        end
    end
    x(i,mark)=0;%祛除不符合的运算向量
    y(i,mark)=0;
    
end

根据上面的程序我们可以得到哪些状态向量是可以通过运算向量进行转化的。其中y是一个$22\times 12$的矩阵：

y =

0 0 0 11 10 9 6 7 0 0 0 4

0 0 0 0 0 0 8 0 0 0 9 7

0 0 0 0 0 0 0 8 0 10 0 6

0 0 0 0 0 0 0 0 11 0 0 1

0 0 22 0 0 0 0 0 0 0 0 8

20 0 0 0 0 0 1 0 0 0 0 3

0 21 0 0 0 0 0 1 0 0 0 2

0 0 0 0 0 0 2 3 0 0 0 5

17 0 0 21 22 1 0 0 0 0 2 0

0 18 0 20 1 22 0 0 0 3 0 0

0 0 16 1 20 21 0 0 4 0 0 0

0 0 0 22 21 20 17 18 0 0 0 15

0 0 0 0 0 0 19 0 0 0 20 18

0 0 0 0 0 0 0 19 0 21 0 17

0 0 0 0 0 0 0 0 22 0 0 12

0 0 11 0 0 0 0 0 0 0 0 19

9 0 0 0 0 0 12 0 0 0 0 14

0 10 0 0 0 0 0 12 0 0 0 13

0 0 0 0 0 0 13 14 0 0 0 16

6 0 0 10 11 12 0 0 0 0 13 0

0 7 0 9 12 11 0 0 0 14 0 0

0 0 5 12 9 10 0 0 15 0 0 0

虽然说上面限制了运算变量的选取，但是还需要满足一个条件：奇数时，状态变量为1的位置，运算变量对应位置才可以为1；偶数时，状态变量为0的位置，运算变量对应的位置才可以为0，这里是编程需要注意的，本文中没有考虑。

2、如何构造邻接矩阵

y(1,4)=10说明第1个状态向量可以通过与运算向量异或变成第11个运算向量。因此我们可以根据该图构造邻接矩阵。那么我们如何将上面的矩阵变成c语言形式的数组了，只需要在上面程序添加下面三句：

fid = fopen('y.txt','wt');

fprintf(fid,'{%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d},\n',y');

fclose(fid）

得到的txt文件如下：

对于该问题的结果，我就不在给出了，百度上都有结果。下面介绍比较特别的算法。

2.商人、随从过河问题

问题提出：商人各带一名随从要乘一凉最多只能容纳两人的小船过河随从们密约, 在河的任何一岸只要他们的人数超过商人就杀人越货, 但乘船的安排权属于商人且商人知这项密约请你为商人制定一种安全渡河方案.

问题分析：我们同样可以用前面提到的状态转移的图论算法来求解。但是我们可以根据该问题的特殊型来用巧妙的解法：我们可以用坐标轴的方法来求解。假设x轴代表商人的个数，y轴代表随从的个数，可行的状态如下坐标轴的黑点。我们的目的就是从（3，3）到(0 , 0)点。由于小船容纳两人，则在坐标轴中，表示我们可以沿坐标线走一步、或则两步。奇数步时，是将人运到对岸，岸这边的人数是减少的，因此这时只能向左走，或则向下走，偶数步时，反之亦然。图解如下：

从上图可以看出，过河方案为：(3,3)——>(3,1)——>(3,2)——>(3,0)——>(3,1)——>(1,1)——>(2,2)——>(0,2)——>(0,3)——>(0,1)——>(0,2)——>(0,0)