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

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 mathematical 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 backtracking 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.