實(shí)驗(yàn)1__怎樣安全過河問題

1、實(shí)驗(yàn)1 怎樣安全過河問題,一、問題,二、實(shí)驗(yàn)?zāi)康?三、預(yù)備知識(shí),四、實(shí)驗(yàn)內(nèi)容與要求,五、思考問題,一、問題 3名商人各帶1名隨從乘船渡河，一只小船只能容納2人，由他們自己劃行。隨從們密約，在河的任一岸，一旦隨從人數(shù)比商人多，就殺商人。此密約被商人知道，如何乘船渡河的大權(quán)掌握在商人們手中，商人們?cè)鯓影才琶看纬舜桨?，才能安全渡河?二、實(shí)驗(yàn)?zāi)康?1、使學(xué)生進(jìn)一步鞏固和理解向量的定義、運(yùn)算規(guī)則、多步?jīng)Q策理論、狀態(tài)空間圖及其應(yīng)用。 2、增強(qiáng)編程知識(shí)和數(shù)學(xué)軟件的應(yīng)用,三、預(yù)備知識(shí) 1、向量定義及運(yùn)算，多步?jīng)Q策理論，狀態(tài)空間圖。 2、熟悉Mathematica、 Matlab等數(shù)學(xué)工具,四、實(shí)驗(yàn)內(nèi)容與要

2、求 建立起商人安全渡河的數(shù)學(xué)模型，并給出商人們?nèi)绾伟踩珊拥囊粋€(gè)或多個(gè)方案，使得渡河的次數(shù)盡量少,五、思考問題 在上述的約束條件下，若商人有4名時(shí)，問商人們是否能實(shí)現(xiàn)安全渡河？更一般地，若商人數(shù)是m，小船最多 只能坐n（1nm人，m和n有何關(guān)系時(shí)，商人們才能實(shí)現(xiàn)安全渡河,解題思路,2、狀態(tài)空間,1、多步?jīng)Q策,一、問題分析與建立模型 由于這個(gè)問題已經(jīng)理想化了，所以不必再作假設(shè)。這個(gè)問題可以看作一個(gè)多步?jīng)Q策的過程。設(shè)第k次渡河前此岸的商人數(shù)為XK，隨從數(shù)為YK，k=1,2,。XK，YK=0,1,2,3。將二維向量SK=( XK,YK)定義為狀態(tài)。安全渡河條件下的狀態(tài)集合稱為允許狀態(tài)集合，記為S，則

3、 S=(x,y)|x=0或3,y=0,1,2,3;x=y=1,2 (1) 又設(shè)第k次渡船上的商人數(shù)為UK，隨從數(shù)為VK，將二維向量DK=(UK,VK)定義為決策,則允許決策集合為: D=(u,v)|u+v=1,2 （2,因?yàn)閗為奇數(shù)時(shí)船從此岸駛向彼岸，k為偶數(shù)時(shí)船由彼岸駛回此岸，所以狀態(tài)SK隨著決策DK變化的規(guī)律即狀態(tài)轉(zhuǎn)移規(guī)律是： SK+1=SK+（1）KDK （3） 這樣，制定安全渡河方案歸結(jié)為如下的多步?jīng)Q策問題： 求決策DKD（k=1，2，n），使SKS按照轉(zhuǎn)移律（3），由初始狀態(tài)S1=（3，3）經(jīng)有限步（設(shè)為n）到達(dá)狀態(tài)Sn+1=（0，0,二、計(jì)算過程 下面通過Mathematica的程

4、序給出這個(gè)多步?jīng)Q策問題的一個(gè)解，同時(shí)滿足了渡河次數(shù)盡量少的條件。 a1=0,0;a2=0,1;a3=0,2;a4=0,3;a5=3,0; a6=3,1;a7=3,2;a8=3,3;a9=1,1;a10=2,2; (*以上兩行表示給出十個(gè)允許的狀態(tài).而1,0,1,2,1,3,2,0,2,1,2,3六種狀態(tài)是不可能出現(xiàn)的。*) d1=0,2;d2=2,0;d3=1,1;d4=0,1; d5=1,0; (*此行表示給出五個(gè)允許的狀態(tài)，而0,0,1,2,2,1,2,2是不可能出現(xiàn)的*,i=1;j=1;k=1;s0=s1=3,3;Print“此岸船上對(duì)岸”； DO DOsi+1=si+(-1)idj;

5、t=0; DOifsi+1=ak;t=1k,1,10; ift=0,Continue; （*以上三行是保證狀態(tài)屬于允許的狀態(tài)*） l=Modi+1,2;m=l;u=0; ifi+1=3, DOIfsi+1=sm,u=1,Break,m,l,i-1,2 ; ifu=0,ci+1=dj;Break （*以上五行是保證狀態(tài)不重復(fù)以滿足渡河的次數(shù)盡量少*） ,j,1,5; Ift=0,PrintNo Result;Break; bi+1=3,3si+1; Printsi,”,ci+1,”,bi+1; Ifsi+1=0,0,Break ,i,1,12,j,1,5; Ift=0,PrintNo Resul

6、t;Break; bi+1=3,3si+1; Printsi,”,ci+1,”,bi+1; Ifsi+1=0,0,Break ,i,1,12,程序運(yùn)算結(jié)果如下： 此岸 船上 對(duì)岸 3,3 0,2 0,2 3,1 0,1 0,1 3,2 0,2 0,3 3,0 0,1 0,2 3,1 2,0 2,2 1,1 1,1 1,1 2,2 2,0 3,1 0,2 0,1 3,0 0,3 0,2 3,2 0,1 0,1 3,1 0,2 0,2 3,3,三、結(jié)果分析 1 上述程序中五個(gè)允許的決策或十個(gè)允許的狀態(tài)順序進(jìn)行整時(shí)，可以得到不同的結(jié)果。例如把d1=0，2，d3=1，1調(diào)整成d1=1，1，d3=0，2

7、就會(huì)得到安全渡河的另一個(gè)方案。需要注意的是進(jìn)行調(diào)整時(shí)也可能得不到安全渡河的方案。 2該模型求解方法有多種，例如可以利用動(dòng)態(tài)規(guī)劃的方法來求解，也可以利用圖解的方法來求解。 3 這種適當(dāng)設(shè)置狀態(tài)和決策，并確定狀態(tài)轉(zhuǎn)移規(guī)律是有效地解決很廣泛的一類問題的建模方法。 4. 不易找到所有的解,可以得出經(jīng)過11步的渡河就能達(dá)到安全渡河的目標(biāo)及滿足渡河次數(shù)盡量少的條件。這11步的渡河方案就是上面程序運(yùn)行結(jié)果中船上下面的那一列。渡河的整個(gè)過程如下所示,設(shè)N和K分別表示商人數(shù)目和隨從數(shù)目，如下圖所示，圖中L和R表示左岸和右岸,B,有船 無船,ST. MC M+C2,1、三維向量表示，即 （ML，CL，BL），其中

8、 0ML，CL3 ，BL0,1 此時(shí)問題描述簡(jiǎn)化為 （3，3，1） （0，0，0） 狀態(tài)空間的總狀態(tài)數(shù)為442=32，根據(jù)約束條件的要求，可以看出只有20個(gè)合法狀態(tài)。再進(jìn)一步分析后,又發(fā)現(xiàn)有4個(gè)合法狀態(tài)是不可能達(dá)到的。因此實(shí)際的狀態(tài)空間僅由16個(gè)狀態(tài)構(gòu)成。下表列出分析結(jié)果： （0，0，1）達(dá)不到 （0，1，1） （0，2，1） （0，3，1） （1，0，1）不合法 （1，1，1） （1，2，1）不合法 （1，3，1）不合法 （2，0，1）不合法 （2，1，1）不合法 （2，2，1） （2，3，1）不合法 （3，0，1）達(dá)不到 （3，1，1） （3，2，1） （3，3，1） （0，0，0） （0

9、，1，0） （0，2，0） （0，3，0）達(dá)不到 （1，0，0）不合法 （1，1，0） （1，2，0）不合法 （1，3，0）不合法 （2，0，0）不合法 （2，1，0）不合法 （2，2，0） （2，3，0）不合法 （3，0，0） （3，1，0） （3，2，0） （3，3，0）達(dá)不到,2、規(guī)則集合：由擺渡操作組成。該問題主要有兩種操作：pmc操作（規(guī)定為從左岸劃向右岸）和qmc操作（從右岸劃向左岸）。每次擺渡操作，船上人數(shù)有五種組合，因而組成有10條規(guī)則的集合。 if（ML，CL，BL=1） then （ML-1，CL，BL-1） P10操作 if（ML，CL，BL=1） then （ML，CL

10、-1，BL-1） P01操作 if（ML，CL，BL=1） then （ML-1，CL-1，BL-1）P11操作 if（ML，CL，BL=1） then （ML-2，CL，BL-1） P20操作 if（ML，CL，BL=1） then （ML，CL-2，BL-1） P02操作 if（ML，CL，BL=0） then （ML+1，CL，BL+1） q10操作 if（ML，CL，BL=0） then （ML，CL+1，BL+1） q01操作 if（ML，CL，BL=0） then （ML+1，CL+1，BL+1）q11操作 if（ML，CL，BL=0） then （ML+2，CL，BL+1） q20操作 if（ML，CL，BL=0） then （ML，CL+2，BL+1） q02操作,3、狀態(tài)空間圖求解,3，3，1,2，2，0,3，1，0,3，2，0,3，2，1,3，0，0,3，1，1,1，1，0,2，2，1,0，2，0,0，3，1,0，1，0,3，3，1,0，0，0,3，3，1,0，1，1,4、結(jié)果分析 狀態(tài)空間圖是一個(gè)有向圖，其節(jié)點(diǎn)可表示問題的各種狀態(tài)，節(jié)點(diǎn)之間的弧線代表一些操作，它們可把一種狀態(tài)導(dǎo)向另一種狀態(tài)。這樣建立起來的狀態(tài)空間圖描述了問題所有可能出現(xiàn)