目錄

• • • 一、問題描述
    • 二、算法思想
    • 三、如何實現
    • 四、流程圖
    • • 1. 主程序
      • 2. 遞歸函數 crossRiver
    • 五、源程序代碼
    • • 1. 主程序 DFS.m
      • 2. 過河函數 crossRiver.m
      • 3. 輸出解的函數 showSolution.m
    • 六、求解結果
    • 七、小結

更新于 2020.08.03

一、問題描述

??3 名商人各帶 1 名隨從過河(從西岸到東岸)，一只小船最多能容納 2 人。隨從們約定：在河的任意一岸，若隨從人數多于商人人數，就殺人越貨. 但商人們知道了他們的約定，并且掌握著過河大權，他們該采取怎樣的策略才能安全過河？

二、算法思想

??這個問題實際上是一個迷宮問題，為什么這樣說呢？請聽我慢慢道來.
??首先，我們將每次渡河前西岸的人員分布和船所在的位置統稱為一個"狀態"，用 $[u,v,1/0]$ 表示，其中 $u,v$ 表示商人、隨從在西岸的人數，末分量表示船的位置：1 表示船在西岸，0 表示船在東岸.將符合條件的狀態挑出來組成允許狀態集合.
??其次，船最多可容納兩個人. 將渡河方案用 $[u,v]$ 表示，其中 $u,v$ 分別表示上船的商人數和隨從數，并將其稱為決策變量，決策變量構成的集合稱為決策變量集合.

??共有 20 種允許狀態和 5 個決策變量.
??初始狀態為 $[3,3,1]$：3 名商人、3 名隨從在西岸，船停靠在西岸；
??終止狀態為 $[0,0,0]$：0 名商人、0 名隨從在西岸，船停靠在東岸，此時商人和隨從全部到達東岸，這樣就確定了"迷宮"的入口和出口.

??從一個狀態變換到另一個狀態是通過決策變量實現的，這里的決策變量也就相當于"迷宮"中的一段路.
??所以，我們的任務就是選擇可行的路徑，從"迷宮"的入口走到出口.

??現在你應該覺得這好像是個迷宮問題，但心中應當還存有懷疑，因為只有入口和出口的話，并不能稱得上是迷宮問題，那還有什么其他的特點呢？

??想想我們是怎樣解決迷宮問題的？從入口出發，沿某一方向前進，若能走通，則繼續往前走；如果不能走通或是有某一分叉可以抵達出口，則沿原路退回到剛剛的分叉點，換個方向繼續前進. 重復這個過程，直至探索出所有可能的通路.

??這個問題也是這樣的，從初始狀態開始，嘗試某種渡河方案，若能到達未經過的允許狀態，則采取該渡河方案；如果不能到達任何一種允許狀態或者是能夠抵達終止狀態，則原路返回至剛剛的狀態，嘗試其他的渡河方案. 重復這個過程，直到探索出所有的渡河方案.

??讀到這兒，你可能會感覺到，這真的就是一個迷宮問題. 好，既然你認同了，咱就繼續往下說.

三、如何實現

??怎樣利用程序來解決這類問題呢？棧+回溯.
??棧(什么是棧？你可以把它簡單地想象成桶裝薯片(只有一端開口)，你只能從上面的薯片依次往下吃才能吃到最后一個，而不能直接吃到最后一個)，具有"后進先出"的特性，所以我們用它來存儲經過(或已標記)的狀態。
??初始情況：起始狀態已被標記，放在棧中. 考慮某一當前狀態(已標記)，則回溯法的基本思想是：

若當前狀態是終止狀態，則輸出路徑，之后進行回溯，即返回上一層，去除當前狀態標記，當前狀態出棧，返回上一狀態，上一狀態繼續嘗試沒有試過的決策變量；

若當前狀態不是終止狀態，則依次嘗試決策變量：
(1). 若當前決策變量能使我到達某個未標記的允許狀態，則將在其上面做標記，而后移動到那個狀態(此時當前狀態已發生改變)，進行遞歸調用，在調用語句之后，消除那個狀態的標記，將其從棧中移出；
(2). 若當前決策變量不能使我到達未標記的允許狀態，則嘗試下一決策變量；
當前狀態下所有的決策變量(不論可不可行)都試過之后，進行回溯；

??正是這種回溯機制，保證了所有可行"路徑"均能被找到.

四、流程圖

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:mfor v = 0:nif ((u >= v && (m-u) >= (n-v)) || u == 0 || u == m) numS = numS + 1;State(numS,:) = [u,v]; endend end % 設定船的狀態 % [u,v,1] 表示船在西岸，[u,v,0] 表示船在東岸 State = [State, ones(numS,1);State, zeros(numS,1)]; numS = numS*2; % 狀態數翻倍 disp('允許狀態集合:'); State fprintf('共%d種允許狀態\n\n', numS);% 2.設定決策變量集合 % max: 船所能容納的最大人數 % [u,v]: u,v 分別表示船上商人和隨從人數 D = []; global numD; numD = 0; % 決策變量個數 for u = 0:mfor v = 0:nif ((u+v) >= 1 && (u+v) <= max)numD = numD + 1;D(numD,:) = [u,v];endend 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 == 0fprintf('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 留下訪問標記的狀態數目,初值為1if pos_currentS == pos_end % 終止情況showSolution(); else % 非終止情況for i = 1:numDpossibleS = 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; % 將其從標記點組成的集合中移出endend end end

3. 輸出解的函數 showSolution.m

function showSolution() % 全局變量 global State pos_passed k count; % State 允許狀態集合 % pos_passed 留下訪問標記的狀態編號 % k 留下訪問標記的狀態數目，初值為1 % count 解的個數，初值為0count = count + 1; fprintf('Solution %d...\n', count); fprintf('\t\t West East\n'); for i = 1:k % 輸出經過的狀態fprintf(' State%2d:(%d,%d)', i, State(pos_passed(i),1), State(pos_passed(i),2));if State(pos_passed(i),3) == 1 % 船在西岸fprintf('★_____'); % ★ 表示船else % State(pos_passed(i),3) == 0 % 船在東岸fprintf('_____★');endfprintf('(%d,%d)\n', 3 - State(pos_passed(i),1), 3 - State(pos_passed(i),2));% 輸出渡河方案if i ~= kif State(pos_passed(i),3) == 1fprintf(' Plan\t:--(%d,%d)->\n', State(pos_passed(i),1) - State(pos_passed(i+1),1), State(pos_passed(i),2) - State(pos_passed(i+1), 2));elsefprintf(' Plan\t:<-(%d,%d)--\n', State(pos_passed(i+1),1) - State(pos_passed(i),1), State(pos_passed(i+1),2) - State(pos_passed(i),2));endend end fprintf('\n'); end

六、求解結果

七、小結

這是一個經典的過河問題，本質就是在各允許狀態之間尋找符合要求的路徑，考慮到可能有多條路徑，需要使用棧保存經過的狀態，以便回溯. 幾點心得：

合適的數據結構——棧，對于此問題的處理起到了至關重要的作用；

對允許狀態進行編號，方便編程，同時增強了程序的通用性；

采用標記的方式記錄經過的狀態，與直接刪除經過的狀態相比，有著很大的優越性，一是保證了回溯的進行，二是避免了刪除操作；

類似的問題還有八皇后問題、人狗雞米過河問題以及其他版本的過河問題；

Plus: 如有錯誤、可以改進的地方、或任何想說的，請在評論區留言！

總結

以上是生活随笔為你收集整理的商人渡河问题(MATLAB版)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。