n-m-k商人渡河问题解的存在性及算法实现

Existence of Solution and Algorithm Implementation for the n-m-k Businessmen-Crossing-River Problem

本文将商人渡河问题推广到最一般情况,即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.