商⼈渡河问题（MATLAB 版）
⽬录
更新于 2020.08.03
⼀、问题描述
  3 名商⼈各带 1 名随从过河(从西岸到东岸)，⼀只⼩船最多能容纳 2 ⼈。随从们约定：在河的任意⼀岸，若随从⼈数多于商⼈⼈数，就杀⼈越货. 但商⼈们知道了他们的约定，并且掌握着过河⼤权，他们该采取怎样的策略才能安全过河？
⼆、算法思想
  这个问题实际上是⼀个迷宫问题，为什么这样说呢？请听我慢慢道来.
  ⾸先，我们将每次渡河前西岸的⼈员分布和船所在的位置统称为⼀个"状态"，⽤  表⽰，其中  表⽰商⼈、随从在西岸的⼈数，末分量表⽰船的位置：1 表⽰船在西岸，0 表⽰船在东岸.将符合条件的状态挑出来组成允许状态集合.
  其次，船最多可容纳两个⼈. 将渡河⽅案⽤  表⽰，其中  分别表⽰上船的商⼈数和随从数，并将其称为决策变量，决策变量构成的集合称为决策变量集合.
  共有 20 种允许状态和 5 个决策变量.
  初始状态为 ：3 名商⼈、3 名随从在西岸，船停靠在西岸；
  终⽌状态为 ：0 名商⼈、0 名随从在西岸，船停靠在东岸，此时商⼈和随从全部到达东岸，这样就确定了"迷宫"的⼊⼝和出⼝.  从⼀个状态变换到另⼀个状态是通过决策变量实现的，这⾥的决策变量也就相当于"迷宫"中的⼀段路.
  所以，我们的任务就是选择可⾏的路径，从"迷宫"的⼊⼝⾛到出⼝.
  现在你应该觉得这好像是个迷宫问题，但⼼中应当还存有怀疑，因为只有⼊⼝和出⼝的话，并不能称得上是迷宫问题，那还有什么其他的特点呢？
  想想我们是怎样解决迷宫问题的？从⼊⼝出发，沿某⼀⽅向前进，若能⾛通，则继续往前⾛；如果不能⾛通或是有某⼀分叉可以抵达出⼝，则沿原路退回到刚刚的分叉点，换个⽅向继续前进. 重复这个过程，直⾄探索出所有可能的通路.
  这个问题也是这样的，从初始状态开始，尝试某种渡河⽅案，若能到达未经过的允许状态，则采取该渡河⽅案；如果不能到达任何⼀种允许状态或者是能够抵达终⽌状态，则原路返回⾄刚刚的状态，尝试其他的渡河⽅案. 重复这个过程，直到探索出所有的渡河⽅案.  读到这⼉，你可能会感觉到，这真的就是⼀个迷宫问题. 好，既然你认同了，咱就继续往下说.
三、如何实现
  怎样利⽤程序来解决这类问题呢？栈+回溯.
  栈(什么是栈？你可以把它简单地想象成桶装薯⽚(只有⼀端开⼝)，你只能从上⾯的薯⽚依次往下吃才能吃到最后⼀个，⽽不能直接吃到最后⼀个)，具有"后进先出"的特性，所以我们⽤它来存储经过(或已标记)的状态。
  初始情况：起始状态已被标记，放在栈中. 考虑某⼀当前状态(已标记)，则回溯法的基本思想是：
1. 若当前状态是终⽌状态，则输出路径，之后进⾏回溯，即返回上⼀层，去除当前状态标记，当前状态出栈，返回上⼀状态，上⼀状态继续尝试没有试过的决策变量；
2. 若当前状态不是终⽌状态，则依次尝试决策变量：
(1). 若当前决策变量能使我到达某个未标记的允许状态，则将在其上⾯做标记，⽽后移动到那个状态(此时当前状态已发⽣改变)，进⾏递归调⽤，在调⽤语句之后，消除那个状态的标记，将其从栈中移出；
(2). 若当前决策变量不能使我到达未标记的允许状态，则尝试下⼀决策变量；
当前状态下所有的决策变量(不论可不可⾏)都试过之后，进⾏回溯；
[u ,v ,1/0]u ,v [u ,v ]u ,v [3,3,1][0,0,0]
  正是这种回溯机制，保证了所有可⾏"路径"均能被到.
四、流程图
1. 主程序
2. 递归函数 crossRiver
五、源程序代码
1. 主程序 DFS.m
clear;clc;
%商⼈过河问题
%global⽤于声明全局变量
global State D SS;
% State 允许状态集合
% D    决策变量集合
% SS    状态标记集合
m =3;%商⼈数
n =3;%随从数
max=2;%船所能容纳的最⼤⼈数
%1.设置允许状态集合{[u,v,1/0]}
% u,v 分别表⽰商⼈、随从在西岸的⼈数
%末分量：1表⽰船在西岸，0表⽰船在东岸
State =[];
numS =0;%允许状态的数⽬
%设定符合要求的⼈员状态
%任意⼀岸，商⼈数不⼩于随从数
%或者，某⼀岸商⼈数为0
for u =0:m
for v =0:n
if((u >= v &&(m-u)>=(n-v))|| u ==0|| u == m)
numS = numS +1;
State(numS,:)=[u,v];
end
end
end
%设定船的状态
%[u,v,1]表⽰船在西岸，[u,v,0]表⽰船在东岸
State =[State, ones(numS,1);State, zeros(numS,1)]; numS = numS*2;%状态数翻倍
disp('允许状态集合:');
fprintf作用
State
fprintf('共%d种允许状态\n\n', numS);
%2.设定决策变量集合
%max：船所能容纳的最⼤⼈数
%[u,v]: u,v 分别表⽰船上商⼈和随从⼈数
D =[];
global numD;
numD =0;%决策变量个数
for u =0:m
for v =0:n
if((u+v)>=1&&(u+v)<=max)
numD = numD +1;
D(numD,:)=[u,v];
end
end
end
disp('决策变量集合:');
D
fprintf('共%d个决策变量\n\n',numD);
%3.设置状态访问标记集合
%对状态进⾏编号:1~ numS
% SS(i)==1，表⽰ i 号状态已访问;
% SS(i)==0，表⽰ i 号状态未访问;
SS = zeros(numS,1);
global pos_end;
global pos_passed k count;
% pos_end    终⽌状态编号
% pos_passed 留下访问标记的状态编号
% k          留下访问标记的状态数⽬
% count      解的个数
%初始状态(3,3,1)，编号:
pos_begin = find(ismember(State,[3,3,1],'rows')==1); %终⽌状态(0,0,0)，编号:
pos_end = find(ismember(State,[0,0,0],'rows')==1);
%4.对参数进⾏初始化
count =0;
SS(pos_begin)=1;%在初始位置留下访问标记pos_passed(1)= pos_begin;%留下访问标记的状态编号k =1;
%5.调⽤递归函数
crossRiver(pos_begin);
if count ==0
fprintf('No solution.\n');
end
2. 过河函数 crossRiver.m
function crossRiver(pos_currentS)
% pos_currentS 当前状态编号
%全局变量
global State D numD SS;
% State 允许状态集合
% numD  决策变量数⽬
% D    决策变量集合
% SS    状态标记集合
global pos_passed pos_end;
% pos_passed 留下访问标记的状态编号
% pos_end    终⽌状态编号
global k;
% k          留下访问标记的状态数⽬，初值为1
if pos_currentS == pos_end %终⽌情况
showSolution();
else%⾮终⽌情况
for i =1:numD
possibleS = zeros(1,3);%事先为可能的状态分配空间
possibleS(1,1:2)= State(pos_currentS,1:2)+((-1)^(State(pos_currentS,3)))*D(i,:);
%船从西岸到东岸，西岸⼈数减少；从东岸到西岸，西岸⼈数增加.
possibleS(1,3)=1- State(pos_currentS,3);
%船的状态也随之改变
%按⾏判断可能的状态是否属于允许状态集合
sign = ismember(State, possibleS,'rows');
%如果可能的状态属于允许状态集合且未被标记，则进⾏访问
%这样做可以避免回到经过的状态，否则程序将陷⼊死循环
if sum(sign)==1
[pos_next,~]= find(sign ==1);% pos_next：可能状态的编号
if SS(pos_next)==0%若未被标记
SS(pos_next)=1;%则进⾏标记
k = k +1;
pos_passed(k)= pos_next;%将其添加到标记点组成的集合中
crossRiver(pos_next);%调⽤⾃⾝，进⾏递归
SS(pos_next)=0;%消除标记
k = k -1;%将其从标记点组成的集合中移出
end
end
end
end
3. 输出解的函数 showSolution.m

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。