农夫携物过河问题-数据结构与算法课程设计报告

《农夫携物过河问题-数据结构与算法课程设计报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、合肥学院计算机科学与技术系课程设计报告2009～2010学年第二学期课程数据结构与算法课程设计名称农夫携物过河问题学生姓名程梦云学号0804012045专业班级08计科(2)指导教师王昆仑张贯虹2010年5月题目：农夫携物过河问题内容：有一农夫要将自己的兔子、蔬菜和狐狸等3件物品运过河。但农夫过河时所用的船每次最多只能装其中的一件物品，而这3件物品之间又存在一定的制约关系：兔子不能单独和狐狸以及不能和蔬菜在一起，因为狐狸要吃兔子，兔子也能吃蔬菜。试构造出问题模式以编程实现这一问题的求解。一、问题分析和任务定义根据对象的状态分为过

2、河（1）和不过河（0），此对象集合就构成了一个状态空间。问题就是在这个状态空间内搜索一条从开始状态到结束状态的安全路径。显然，其初始状态为四对象都不过河，结束状态为四对象全部过河。这里利用图的广度优先算法思想处理，并采用队列存储，灵活运用二进制的特点完美解决问题。对于农夫，狐狸，兔子，蔬菜组成一个4位二进制代码，即4位二进制数分别代表了农夫、狐狸、白菜和兔子，状态空间为16，初始状态为（0000），目标为（1111）。解决问题的方法是，首先将初始状态（0000）入队(第一层)，再将由初始状态（0000）可达到的所有安全状态入队（

3、第二层），能由已有的安全状态到达的安全且不重复的所有状态入队（第三层），依次如此直到状态（1111）为止。对当前对象是否安全的判断，若当农夫与兔子不在一起时，狐狸与兔子或兔子与蔬菜在一起是不安全的，其他情况是安全的。二、概要设计和数据结构的选择求解这个问题的最简单的方法是一步一步进行试探，每一步都搜索所有可能的选择，对前一步合适的选择再考虑下一步的各种方案。用计算机实现上述求解的搜索过程可以采用两种不同的策略：一种是广度优先(breadth_first)搜索，另一种是深度优先(depth_first)。此处采用广度优先算法。广度

4、优先的含义就是在搜索过程中总是首先搜索下面一步的所有可能状态，然后再进一步考虑更后面的各种情况。要实现广度优先搜索，一般都采用队列作为辅助结构。把下一步所有可能达到的状态都列举出来，放在这个队列中，然后顺序取出来分别进行处理，处理过程中把再下一步的状态放在队列里……。由于队列的操作遵循先进先出的原则，在这个处理过程中，只有在前一步的所有情况都处理完后，才能开始后面一步各情况的处理。要模拟农夫过河问题，首先需要选择一个对问题中每个角色的位置进行描述的方法。一个很方便的办法是用四位二进制数顺序分别表示农夫、狼、白菜和羊的位置。例如用

5、0表示农夫或者某东西在河的南岸，1表示在河的北岸。因此整数5(其二进制表示为0101)表示农夫和白菜在河的南岸，而狼和羊在北岸。表1物品的所有位置状态农夫、狐狸、白菜、兔子Location农夫、狐狸、白菜、兔子Location00000100080001110019001021010100011310111101004110012010151101130110611101401117111115⑴数据结构的选择：本程序采用队列处理。typedefstructnode//顺序队列类型定义{intf,r;//定义头尾指针intdat

6、a[maxlen];}SeqQueue;⑵为了实现上述程序的功能，需要：①队列的创建、判空、入队、出队、取队首元素；②判断农夫、狐狸、白菜和兔子的位子，并以此来判断该状态是否安全；③按位子输出农夫、狐狸、；④主函数，一个广度优先的过程；各函数关系如下：mainCreateQenQueuesafeDFS_pathprintflocationclick图1各函数关系图三、详细设计和编码完成了上面的准备工作，现在的问题变成：从初始状态二进制0000(全部在河的南岸)出发，寻找一种全部由安全状态构成的状态序列，它以二进制1111(全部到

7、达河的北岸)为最终目标，并且在序列中的每一个状态都可以从前一状态通过农夫（可以带一样东西）划船过河的动作到达。并且要求在序列中不应该出现重复的状态。算法分析如图2。为了实现广度优先搜索，算法中需要使用了一个整数队列Q，它的每个元素表示一个可以安全到达的中间状态。另外还需要一个数据结构记录已被访问过的各个状态，以及已被发现的能够到达当前这个状态的路径。由于在这个问题的解决过程中需要列举的所有状态(二进制0000~1111)一共16种，所以可以构造一个包含16个元素的整数顺序表来满足以上的要求。用顺序表的第i个元素记录状态i是否已被

8、访问过，若已被访问过则在这个顺序表元素中记入前驱状态值，算法中把这个顺序表叫做visited。visited的每个分量初始化值均为-1，每当我们在队列中加入一个新状态时，就把顺序表中以该状态作下标的元素的值改为达到这个状态的路径上前一状态的下标值。visited