商人渡河问题的有解性分析（常用版）(可以直接使用，可编辑完整版资料，欢迎下载）第42卷第20期数学的实践与认识Vbl．42．No．202021年10月MATHEMATICSINPRACTICEANDTHEORYoct．．2021商入渡河问题的有解性分析邵建峰·，邵硕z(1．南京工业大学理学院，江苏南京210009)(2．麦克马斯特大学工学院，汉密尔顿加拿大)摘要：“商人渡河问题”是一个传统的智力游戏问题，常常作为数学模型、数据结构与智能算法分析等学科中很重要的教学与实验案例被引用．其求解算法尚未得到很好的解决，尤其是问题解的存在性等还缺少一般性和明确的结论．对此，将主要从理论上探讨该类问题何时有解的一般性结论，并给出严格的数学证明．同时还将讨论渡船上安全策略的不同选择对问题求解的影响，关键词：商人渡河问题；数学模型；多步决策问题；智能算法1引言“商人渡河问题”是一个流传中外，经典的智力游戏问题，许多数学模型教材【1_3】上也都引用了这样一个趣味问题．在国外该问题也被称为传教士和野人问题(missionariesandcannibalSproblem，M—C问题)【4]．商人渡河问题看起来较简单，实则其蕴含的思想与方法是非常深刻的．所以它往往也作为数据结构与智能算法分壹千等学科中很重要的教学或实验案例被引用[5一引．对这类问题，就其数学建模思想来说，它属于多步决策问题．它的求解，尤其计算机编程实现是研究的一个方面．此外，当渡河问题中的商人数，随从数或者小船上每次渡河人数发生了变化，其一般性问题还是否一定有解，何时有解，最少的解题步数是什么?至今还没有明确的结论[1一引．对此，本文将主要从理论上探讨该类问题何时有解的一般性结论，同时还将探讨渡船上安全策略的不同选择对问题求解将产生的影响．2求解分析推广性的商人过河问题：有咒个商人，带有m个随从需要乘船渡河．渡河的小船每次最多只可以容纳h(22)个人．随从们密约，在河的任_岸，一旦随从的人数比商人多，就杀人越货，但是如何乘船渡河的决策权掌握在商人们手中．问商人们能否安全渡河?现将“商人渡河问题”记为w(几，m，^)，一般性的商人渡河问题是否有解，这不仅可以从算法结果得出，而且也有必要从理论上整体加以探讨．设z岛为第后次渡河后此岸的商人数，收稿日期：2021—10一15资助项目：得到国家级教学研究项目“科学思维、科学方法在高校数学课程教学创新中的应用与实践”(数学一4)和南京工业大学数学基础平台项目资助．万方数据140数学的实践与认识42卷妣为第七次渡河后此岸的随从数，则数组sk=陋七，讥]为第忌次渡河后此岸的当前状态．初始状态即为so—bo，可o]．而第七次渡河后彼岸的状态为z七一so—s七=(zo一。k，可。一可k)．又记“％，uk分别为第而次渡河时渡船上的商人与随从数，即数组毗=(uk，u％)为第七次渡河策略，则有状态转移方程sk=sk一1+(一1)”dk，％=172，状态转移方程中此岸的、彼岸的状态一定要符合“安全性”约定．并且当^>2时，小船上也可能存在安全性问题．对此有下面两种不同的理解．假设11与每次渡河时小船上的商人与随从数上限h大干2时，小船上同样要考虑安全性问题；假设2不论每次渡河时小船上的商人与随从数上限h是否大于2，皆认为小船上没有安全性问题(或认为两岸的安全性决定了船上的安全性，这样的假设也是可行的)；．以下先暂时只考虑在假设1(即同时要求考虑小船上的安全性问题)的条件下进行讨论．该类问题类同于组合数学中的命题，理论探讨较难开展，至今还没有这方面的明确的结论．为了表述清楚起见)再次强调使用记号f】，()和{)，即[忌1，惫2】，(南3，惫4)，【是l，是2】+(盎3，七4)和{是5，七6>分别来表示此岸的、彼岸的、当前总的状态，以及渡河的策略(即小船上渡河的商人、随从数)等．并且用单箭头符号一表示从此岸到彼岸，用双箭头符号兮表示从彼岸回到此岸．从此岸到彼岸，再从彼岸回到此岸的过程称为“一个回合”．。定理1渡河问题w(4，4，2)无解．证明当^=2时，允许的渡河策略的集合为D=({o，1)，{o，2)，{1，o)，，{1，1)，|[2，o>)，共有LD=5种不同的渡河策略．从初始时的总状态[4，4]+(o，o)(即初始时两岸的状态)出发，如果每次都采用渡河策略d，={o，2)去，用渡河策略d2={o，1)返回，经过若干回合则有【4，4]+(o，o)‘譬’【4，2]+(o，2)‘骘’[4，3】+(o，1)【4，3]+(o，1)‘骘’【4