农夫过河问题 一. 问题描述 设一个农夫过河带着一条狼、一只羊和一棵白菜，身处河的南岸。现在他要把这些西全部运到北岸,现在问题是他面前只有一条小船，船小到只能容下他和一件物品，另外只有农夫能撑船。当农夫在场的时候,这三样东西相安无事.一旦农夫不在,狼会吃羊,羊会吃白菜。根据原题的描述我们知道，单独留下白菜和羊，或单独留下狼和羊在某一岸的状态是不安全的。白菜和狼相处没事,把它看作个重要关系的,通过位置分布的代码来判断状态是否安全。然后设计一个方案, 模拟农夫能安全地将这三样东西带过河。 二．基本要求 以队列解决农夫过河问题，用广度优先搜索实现求解的过程。用这个方法来搜索过程中总是首先搜索下面一步的所有可能状态，然后再进一步考虑更后面的各种情况。要实现广度优先搜索，一般都采用队列作为辅助结构。把下一步所有可能达到的状态都列举出来，放在这个队列中，然后顺 序 取 出来分别 进行 处理 ，处理 过程中把再下一步的状态放在队列里 。由 于 队列的操 作遵 循 先进先出的原则 ，在这个处理 过程中，只有在前一步的所有情况都处理 完 后，才 能开 始后面一步各情况的处理 。为了 实现广度优先搜索，算 法中需 要使 用了 一个整 数队列 moveTo，它的每 个元 素 表 示 一个可以安全到达的中间 状态。另外还 需 要一个数 据结构记 录 已 被 访 问过的各个状态，以及 已 被 发 现的能够 到达当前这个状态的路 径 。由 于 在这个问题的解决过程中需 要列举的所有状态(二进制 0000 ~ 1111)一共 16 种，所以可以构造 一个包 含 16 个元 素 的整 数 顺 序 表 来满 足 以上 的要求。 三．测 试 数 据 要模拟农夫过河问题，首先需 要选 择 一个对 问题中每 个角 色 的位置进行 描述的方法。一个很 方便 的办 法是用四 位二进制 数 顺 序 分别 表 示 农夫、狼、白菜和羊 的位置。例如用0 表示农夫或者某东西在河的南岸，1 表示在河的北岸。因此整数5(其二进制表示为0101) 表示农夫和白菜在河的南岸，而狼和羊在北岸。确定每个角色位置的函数,用整数location 表示上述四位二进制描述的状态，用下面的四个函数从上述状态中得到每个角色所在位置的代码。函数返回值为真表示所考察的人或物在河的北岸，否则在南岸。从初始状态二进制0000(全部在河的南岸) 出发，寻找一种全部由安全状态构成的状态序列，它以二进制1...
VIP
