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

     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

     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

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*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');

   fpr intf(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)点。由于小船容纳两人，则在坐标轴中，表示我们可以沿坐标线走一步、或则两步。奇数步时，是将人运到对岸，岸这边的人数是减少的，因此这时只能向左走，或则向下走，偶数步时，反之亦然。图解如下：