商人渡河问题的算法实现（常用版）(可以直接使用，可编辑完整版资料，欢迎下载）第42卷第19期数学的实践与认识Vbl．42．No．192021年10月MATHEMATICSINPRACTICEANDTHEoRYoct．．2021商人渡河问题的算法实现邵建峰，许丙胜(南京工业大学理学院，江苏南京210009)摘要：“商人渡河问题”是一个传统的智力游戏问题，常常是作为数学模型、数据结构与智能算法分析等学科中很重要的教学或实验案例被引用．其求解算法尚未得到很好的解决，问题解的存在性等还缺少一般性和明确的结论．将首先从算法实现方面对这个问题进行深入地探讨．设计出思想方法较简单的、能在Matlab中编程实现的算法，且算法能求出问题的全部最少步数解．此外还报告了该类问题在各种情形下有趣的计算结果．关键词：商人渡河问题；数学模型；多步决策问题；智能算法l引言“商人渡河问题”是一个流传中外，经典的智力游戏问题，许多数学模型教材I卜3】上也都引用了这样一个趣味问题．在国外该问题也被称为传教士和野人问题(onariesandcannibalsproblem，M—C问题)【9】．商人渡河问题看起来较简单，实则其蕴含的思想与方法非常深刻．所以它往往也作为数据结构与智能算法分析等学科中很重要的教学或实验案例被引用【10-1引．就其数学建模思想来说，一般采用将该问题转化为一个多步决策模型，模型求解的方法大多为图解法．然而一旦问题的条件(例如商人、仆人或者小船上每次渡河人数等)发生变化，图解法求解犹如大海捞针、很难奏效．因此计算机编程求解模型的方法就显得非常重要了．该问题求解编程的难点在于“搜索”与“回溯”这两个方面的处理与实现．文献(阻8，10】等)讨论了这个问题的计算机求解算法，但算法往往都存在某些不足或缺陷．例如将“渡河步数是否已很大?”作为停机条件，从而理论上不能保证得到问题的最优解，或无法保证搜索出问题所有的最少步数解．也有的运用数据结构等学科中的堆栈等搜索技术编程，使算法更复杂．还有的算法由于搜索与回溯过程的处理技术问题，仍然存在使算法运行时间过长(例如需要几个小时)的情况等l41．此外，当渡河问题中的商人数，仆人数或者小船上每次渡河人数发生了变化，这类问题的一般情况还是否还一定有解，何时有解，最少的解题步数是什么?至今研究很少，也没有明确的结论．对此，本文将首先从算法方面，对这个问题进行深入和彻底地探讨，给出思想方法较简单的、能在Matlab中编程实现的算法，并报告了多个计算实例．此外还将另文讨论该类问题在理论上何时有解的一般性结论，以及渡船上安全策略的选择问题．收稿日期：2021一08．05资助项目：得到国家级教学研究项日“科学思维、科学方法在高校数学课程教学创新中的应用与实践”(数学。一4)和南京工业大学数学基础平台项目资助．万方数据138数学的实践与认识42卷2算法实现传统的商人过河问题；有三名商人各带一个随从乘船渡河，渡河的小船至多只可以容纳二人，随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货，但是如何乘船渡河的决策权掌握在商人们手中，商人们怎样才能安全渡河?现将“商人渡河问题，’记为Ⅳ(吼m，^)，其中n为商人数，m为仆人数，^为小船上每次渡河人数．设z凫为第七次渡河后此岸的商人数，弧为第七次渡河后此岸的仆人数，则数组5七=【z七，骓】为第七次渡河后此岸的当前状态．初始状态即为so=[zo，如]_而第七次渡河后彼岸的状态为￡七一so—sk=(zo—z七，蛳一鲰)．又记“k，"k分别为第七次渡河时渡船上的商人与仆人数，即数组靠={挂b，弘≈]-为第％次渡河策略，则有状态转移方程粤无=s七一l+(一1)七d七，七=l，2，在上面记号中分别用口，()和{}来表示此岸的、彼岸的状态与小船上渡河的商人、仆人数等，同样都是二维数组，只是符号上加以区别的意思．另外状态转移方程中此岸的、彼岸的状态一定要符合“安全性”约定(当h=2时，小船上不存在安全性问题)．假设1当每次渡河时小船上的商人与仆人数上限h大于2时，小船上同样要考虑安全性问题；假设2不论每次渡河时小船上的商人与仆人数上限h是否大于·2，皆认为小船上没有安全性问题(或认为两岸的安全性决定了船上的安全性，这样的假设也算是可行的)；下面将采用基于矩阵存储与搜索技术的Matlab编程方法求解．利用Matlab中矩阵运算与存储的便利性，能使状态转移，以及路径的回溯，最优解搜索，全部解查找与等都可以得到较简单的解决．算法不仅编程结构最简单，而且计算量与运行耗时也很