基于间接矩阵法的商人过河问题数学模型

韩家宝 蒋伟

摘要：经典的商人过河问题是指“三商三随”安全过河问题，当商人和随从数量大于三或者商人与随从数量不同就会产生不同的结果。本文综合邻接矩阵和可达矩阵，提出间接矩阵的概念，并利用间接矩阵，针对多人等数量商人随从过河问题和多人不等数量商人随从过河问题是否有解以及最少步数问题提出解决方案，比传统的方法在讨论商人数量和随从数量较大且商人数量多时，运算量大大减小。

关键词：商人过河;邻接矩阵;最少步数;间接矩阵

一、引言

商人过河问题是一个经典的智力游戏问题，也是数学建模中的一个经典案例，在许多数学建模教材中都曾出现过。商人过河问题看起来比较简单，但其中蕴含的状态转移思想和多步决策思想是十分深刻的。其中经典的商人过河问题指的是三商三随过河问题，其中如何过河、最少步数等问题都已有结论。但是当商人和随从人数发生变化时，是否有解以及最小步数都还没有明确结论。

因此，本文提出间接矩阵的概念，针对当商人和随从人数发生变化时的各种情况下是否存在安全过河方案以及方案最小步数问题进行良好的解决。

二、模型建立

本文为解决商人过河问题中的是否有解及最小步数问题，提出间接矩阵和伪间接矩阵的概念。

（一）间接矩阵的提出

在此类比邻接矩阵的概念对间接矩阵进行定义：表示顶点i之间相间关系的矩阵。其中间接矩阵的级数k表示该间接矩阵中相间关系的相间步数，。表示顶点可以恰通过k次转移到达顶点j，表示顶点i不可以恰通过k次转移到达顶点j。

以图1为例，其1级间接矩阵即表示点之间间隔1步的相连情况，即为其邻接矩阵。其2级矩阵即为间隔2步的相连情况，如v1可以通过的方式与v5相连，则，但v1与v3之间没有间隔2步的连接方式，则。同理即可得到图1的2级间接矩阵，

三、模型求解

本文以三商三随、四商四随、四商三随三种情况为例，利用间接矩阵法，对其是否有解及最小步数进行求解。

（一）三商三随问题求解

由于在河的任一岸，一旦随从的人数比商人多，随从就会杀人越货。因此商人和随从的人数分布存在安全与不安全的不同情况，其中安全状态则为任一岸的商人人数不小于该岸随从人数（由于当此岸商人人数为0时，不存在杀人越货的可能，因此也是安全状态），通过穷举法可列举此岸全部安全状态向量。

由于在转移过程中必须保证永远处于安全状态，因此上述安全状态即可作为“图”的顶点集：

由于只有一艘船，所以每次船带人离开此岸后，下一次一定是船带人回到此岸，因此可得到以下状态转移向量：

小船回到此岸：d=（0，+1），（0，+2），（+1，0），（+1，+1），（+2，0）

小船離开此岸：-d（0，-1），（0，-2），（-1，0），（-1，-1），（-2，0）

各个安全状态之间的转移即可作为“有向图”的边，由于船离开此岸和回到此岸的状态转移向量不同，即两次的邻接矩阵不同，分别得到船离开此岸和回到此岸的邻接矩阵：

根据伪间接矩阵的性质，可以得到基于该问题的伪k级间接矩阵表达式：

其中即表示（3，-3）状态不可以经过k次转移到达（0，0）状态;表示（3，3）状态可以经过k次转移到达（0，0）状态，而其数值即为状态经过次转移到达状态的路径数。令的数值不等于0的最小的k值即为最小渡河次数，的数值即为通过最小渡河次数到达（0，0）状态的路径数。

由于该问题需要考虑的是船在彼岸时（0，0）状态能否达到的问题，所以只需要考虑k为奇数时的情况。

将三商三随问题的邻接矩阵带入其中可以求得当k≤9时;当k=11时，。即三商三随问题最小渡河步数为11步，该步数下路径有4条。

四、结论

可以利用间接矩阵整合邻接矩阵与可达矩阵，并且利用间接矩阵可以简单、直观表达图论中是否有解、最小步数、路径数等多种问题，更好的解决状态转移类问题。但间接矩阵难以表达实际的路径方案，因此在方案的表达上，需要结合图解法进行求解。

参考文献

[1] 姜英姿，赵建强，米军利. 数学建模教程[M]. 中国矿业大学出版社，2017：15-17.

[2] 周凯，邬学军，宋军全. 数学建模[M].浙江大学出版社，2017：17-18.

[3] 邵建锋.商人渡河问题的有解性分析[J]. 数学的实践与认识，2012（20）：139-146.

[4] 张念发，张宪新，刘长征. 基于状态空间搜索法的商人过河问题解决方案[J]. 电脑编程技巧与维护，2010（18）： 36-37+92.

[5] 王涛.用矩阵求图中路径数目的另一种证明方法[J].长沙民政职业技术学院学报，2018， 25（03）： 107-108.

[6] 原慧琳.汪定伟. 最短路径的可达矩阵算法[J].信息与控制，2011，40（02）： 202-208+213.

[7] 张静，李茂清. 由邻接矩阵求解可达矩阵的一种改进简便算法[J].电脑知识与技术（学术交流）， 2007（01）：177-178.