人鬼渡河MatlabGUI界面设计-副本

1、课课程程设设计计( (论论文文) )题题 目目人人鬼鬼渡渡河河问问题题姓姓 名名学学 号号指指 导导 老老 师师指指导导教教师师职职称称教教授授年年级级专专业业班班级级所所 在在 学学 院院理理学学院院2 20 01 14 4 年年 5 5 月月 2 25 5 日日II武汉工程大学课程设计 (论文)目目录录目录.I摘要.II前言.III1课题背景 .11.1背景 .11.2需求分析 .11.3 意义.11.4 文献综述 .22设计方案的解题思路 .32.1人鬼渡河的任务与规则要点 .32.2人鬼渡河的安全性考虑 .32.3 安全状态的描述 .42.4 安全条件形式化 .63 详细设计 .123

2、.1渡河策略的定义.123.2初始状态 的定义123.3 人鬼渡河的 操作.133.4 可视化的设计.144设计结果及分析 .184.1测试结果 .184.2 问题解决 .225总结.22致谢 .25参考文献 .26附录 程序代码 .27III武汉工程大学课程设计 (论文)摘摘要要本课题主要是运用 Matlab7.0 的强大功能来解决 多决策人鬼渡河 问题。本文较详细地介绍了这一程序的设计思想，功能结构以及可视化界面 的设计。本文还给出了对这一程序的测试情况以及对测试结果的分析。关键词关键词：person，ghost，MatlabIV武汉工程大学课程设计 (论文)前前言言本文详细介绍了 多决策

3、人鬼渡河 问题的设计与开发。 全文共5章。第1章介绍了 多决策人鬼渡河 问题的背景，以及它所要实现的基本功能。并根据这些用户需求，进行了必要的需求分析，从而确定了该程序应实现了一些基本功能。本章中，还简要地介绍了该程序开发的意义以及在整个开发过程中，我们所查阅并借用的一些参考文献的主要内容。第2章主要介绍了 多决策人鬼渡河 问题程序 中各功能模块的 总体框图，这是全文的核心部分。第3章是多决策人鬼渡河 问题程序的详细设计 ，我们给出了主要的编程思路。第4章是对所开发的 人鬼渡河 问题程序的运行测试。通过我们所设计的 最佳方案选择程序 ，检验程序是否达到了预定的设计要求 。第5章是对关于运用 多

4、决策解题思路 解决人鬼渡河 问题程序开发过程的总结。总结了本次 课程设计的意义，以及 测试中所发现的一些问题，有待进一步改进的地方。 重点还谈到了 我在本次 课程设计中的收获 与感想。全文的最后是致谢、参考文献和程序的全部源代码。XX2014-5-25 于武汉工程大学理学院1武汉工程大学课程设计 (论文)1 课课题题背背景景1.11.1背景背景人鬼渡河问题：有 3 个人带着 3 个鬼要从河的东岸坐船摆渡到西岸，船很小，容量为 2（或 2 人，或 2 鬼，或 1 人和 1 鬼）。无论是在河的东岸还是西岸，一旦鬼数多于人数，则人会被鬼丢到河中。试编程求出一种渡河方案。1.21.2需求分析需求分析根

5、据上面 给出的问题，我们可以 运用多决策解题思路 来解决。而且，我们必须通过程序来实现上面 人鬼渡河 问题的最佳方案选择。针对任务我们首先进行形式化的分析，试图建立一个个解决该题的数学模型。首先归纳人鬼渡河的规则，需从安全角度考虑：人身安全和船不能超载。1.31.3 意义意义关于多决策问题 的相关知识，是我们信息与计算科学专业必须了解的经典算法之一。 它在程序中的作用肯定是毋庸置疑，对于我们以后的工作有时也有着指导作用。采用 Matlab 与算法与数据结构 的思想，设计与开发 人鬼渡河 问题的算法程序，有助于我们了解对该门课程的掌握程度及自身的运用学习能力。2武汉工程大学课程设计 (论文)1.

6、41.4 文献综述文献综述文献1较详细地介绍了多决策人鬼渡河问题程序的设计与开发以及C+的一些基本知识，它对于我们了解C+知识，运用 C+进行算法与数据结构有非常直接的帮助。文献2介绍了 Matlab 程序设计的主要思想与方法，在解决多决策人鬼渡河问题程序时，我们参考该书中许多技巧、注意事项和可视化界面的设计等。3武汉工程大学课程设计 (论文)2 设设计计方方案案的的解解题题思思路路2.12.1人鬼渡河的任务与规则要点人鬼渡河的任务与规则要点（1） 目标是将东岸的 3 人 3 鬼通过一只小船转移到西岸，希望以尽可能少的摆渡次数完成任务。（2） 船须有 1 人或 1 鬼来划，船的容量有限，一次最

7、多只能坐不多于2人（或 2 鬼或 1 人 1 鬼）。（3） 无论是在河的东岸还是西岸，一旦鬼数多于人数，则人被鬼丢到河中。（4） 怎样渡河的大权掌握在人的手中。（5） 只求一种渡河方案。2.22.2人鬼渡河的安全性考虑人鬼渡河的安全性考虑定义变量： R表示东岸人数 G表示东岸鬼数 k表示船行次数，从东岸到西岸或从西岸到东岸各计1 次。显然，船从东到西， k 为奇数；船从西到东， k 为偶数。定义向量为第 k 次行船的摆渡策略：kd =（,）kdkukv其中为上船人数，为上船鬼数。kukv小船的容量为 2，因此令允许的摆渡策略集合为D:D= (u,v)| u=2， v=0；u=1， v=0；u=

8、1， v=1；u=0， v=1；u=0， v=2；4武汉工程大学课程设计 (论文)说说明明：不存在 u=0,v=0 的情况，因为没有划桨者。状态定义：摆渡过程中东岸的人数和鬼数视为一种状态，令表示第 kkS次摆渡前的状态 =（,）kSkukv经过一次摆渡，东岸的人数和鬼数发生变化，会从一种状态变为另一种状态，称之为状态转移。图 2-1 为状态转移图。 kS1kSk 为偶数 +kdk 为奇数 -kd图 2-1 状态转移图状态转移公式：= + * *1kSkSk) 1(kd安全渡河方案为多步决策问题，决策的目标是：选择一系列的摆渡方案决策D（k=1,2,n）,使状态kd SkS按照状态转移公式 =

9、 + * *1kSkSk) 1(kd由初始状态=（3,3）经有限步骤 n 到达1S =（0,0）1nS5武汉工程大学课程设计 (论文)2.32.3安全状态的描述安全状态的描述下面我们用一些图来形象地加以说明，先看图2-2，东岸状态图中的 10 个安全状态。从东岸状态图分析有 3 类点是安全的：第 1 类：3 个人在东岸未动，有 4 个点。第 2 类：3 个人已不在东岸，有 4 个点。第 3 类：在东岸人数和鬼数相等，只有两个点。（1,1）1 人 1 鬼；（2,2）2 人 2 鬼安全渡河要从第 1 类的 4 个点转到第 2 类的 4 个点，必须经过第 3 类的 2个点。存在不安全的 6 个状态，

10、无论在东岸还是西岸鬼数多于人数，人就惨了。东岸上的这 6 个状态画在图 2-2 中图 2-2 不安全和安全状态图 2-2 中，白点表示不安全状态，有6 个；黑点表示安全状态，有10 个。6武汉工程大学课程设计 (论文)2.42.4安全条件形式化安全条件形式化令 AQ=1 表示安全， AQ=0 表示不安全。下面我们将渡河问题的安全条件形式化，见图2-3. 将安全条件形式化AQ=（ R=3 第一类安全点| R=0 第二类安全点 第 3 类安全点（人数等于鬼数）图 2-3 形式化的安全条件为了便于理解，我们先从初始状态出发一步一步地走走看。有以下步骤：第 1 步：2 鬼上船西渡，东岸留 3 人 1

11、鬼（R=1）&(G=1)（R=2）&(G=2)7武汉工程大学课程设计 (论文)第 2 步：1 鬼返回，东岸留 3 人 2 鬼第 3 步：2 鬼上船西渡，东岸有 3 人第 4 步：2 鬼上船东渡，东岸有 3 人 1 鬼第 5 步：2 人上船西渡，东岸有 1 人 1 鬼8武汉工程大学课程设计 (论文)第 6 步：1 人 1 鬼上船东渡，东岸有 2 人 2 鬼第 7 步：2 人上船西渡，东岸有 2 鬼第 8 步：1 鬼上船东渡，东岸有 3 鬼9武汉工程大学课程设计 (论文)第 9 步：2 鬼上船西渡，东岸有 1 鬼第 10 步：1 鬼上船东渡，东岸有 2 鬼第 11 步:2 鬼上船西

12、渡，东岸空10武汉工程大学课程设计 (论文)安全渡河的关键点如图 2-4：图 2-4 安全渡河的关键点从起始状态一步一步移到目标状态，整个过程如图2-6 所示。1d2d从东往西从西往东1ndnd()0 , 0从西往东从东往西1S2S3S1nSnS1nS图 2-6 使用状态转移方程求解安全渡河问题的多步决策（3,3）摆渡决策用结构数组来描述，为编程方便无论是从东向西，还是从西向东，统一考虑一共有 6 个决策，从东岸摆渡到西岸有3 种可选决策（ 0，-2），（-1,-1），（-2,0），依次令其为决策号 1,2,3；从西岸摆渡到东岸也有 3种可选决策（ 0,1），（1,1），（1,0），依次依次令

13、其为决策号4,5,6.令 i 为决策号，渡河策略： 从东往西 从西往东决策号 i123456人 数 d10-1-2011鬼 数 d2-2-1011011武汉工程大学课程设计 (论文)3 详详细细设设计计3.13.1渡河策略的定义渡河策略的定义d1=0,-1,-2,0,1,1;%渡河策略d2=-2,-1,0,1,1,0;3.23.2初始状态的定义初始状态的定义u=3;v=3;%初始状态东岸有 3 人 3 鬼k=0;%初始状态号flag1=0;flag2=0;%东岸尚未达到 1 人 1 鬼或 2 人 2 鬼状态标志3.33.3人鬼渡河的操作人鬼渡河的操作while (u=0&v=0) k=

14、k+1; if rem(k,2)=0 a=4;%k 为偶数表示船东渡，策略号从4 开始 else a=1;%k 为奇数表示船东渡，策略号从1 开始12武汉工程大学课程设计 (论文) end for i=a:1:a+2%循环，试探采用哪个决策能安全走一步 mu=u+d1(i);%按第 i 号策略走一步东岸的人数 mv=v+d2(i);%按第 i 号策略走一步东岸的鬼数 if mu3|mv3|mu0|mv3|mv3|mu0|mv3|mv3|mu0|mv3|mv3|mu0|mv3|mv3|mu0|mv0|(mu=3&mv=3) continue;%取消越界和重复（回归起始状态） end33武

15、汉工程大学课程设计 (论文) if mu=3|mu=0|(mu=1&mv=1)|(mu=2&mv=2) AQ=1;%记录四种状态之一时，安全信息AQ 为 1 else AQ=0; end if flag1=1&flag2=1 CHF=1;%记录重复（达到过 1 人 1 鬼和 2 人 2 鬼的状态）时CHF 为 0 else CHF=0; end if mu=0|(AQ=1&CHF=0)%如果 3 人已到达西岸，或安全且不重复 u=mu;v=mv;%存东岸人数和鬼数 person(k)=u;ghost(k)=v;%存东岸人数和鬼数 if u=1&v=1 f

16、lag1=flag1+1;%给达到 1 人 1 鬼的状态加标志 end if u=2&v=2 flag2=flag2+1;%给达到 2 人 2 鬼的状态加标志 end break; end34武汉工程大学课程设计 (论文) end n=get(handles.listbox1,Value);%获取绘图符号 真值 Color=ox*p;%绘图选择颜色 axes(handles.axes1);%选定绘图坐标区域 axis(0,3,0,3) hold on grid on plot(person,ghost,Color(n) pause(0.5);end % - Executes on button press in pushbutton3.function pushbut