作　　者： ; ; ;

机构地区： 河南财政税务高等专科学校信息工程系

出　　处： 《工程数学学报》 2013年第4期561-568,共8页

摘　　要： 本文将商人渡河问题推广到最一般情况,即n-m-k商人渡河问题,建立了该问题的多步决策数学模型.首先,根据该数学模型得到一棵状态空间树,设计了采用递归和回溯方法遍历该状态空间树的算法步骤.其次,根据部分运行结果,分析了该问题的算法复杂度.最后,分析了该问题解的存在性,并给出了若干定理及其证明.本文已将商人渡河问题扩展成为广泛的经典例子,有利于解决实际生活中的问题. We extend the businessmen-crossing-river problem into the most general case, i.e. the n - m - k businessmen-crossing-river problem, and establish the multi-step-decision math- ematical model for this problem. Firstly, a state space tree corresponding to this mathematical model is created and an algorithm for traversing the state space tree by recursion and backtrack- ing methods is designed. Secondly, the analysis of algorithm complexity is evaluated based on experimental results. Finally, the existence of solution for this problem is analyzed, and some theorems and proofs are introduced. The obtained results are potentially beneficial to some real life problems.

关 键 词： 商人渡河问题 算法实现 解的存在性

领　　域： [理学] [理学]