修道士与野人问题课程设计报告

4星 · 超过85%的资源 需积分: 29 55 下载量 196 浏览量 更新于2023-03-16 4 收藏 304KB DOC 举报
这是一个古典问题。假设有n个修道士和n个野人准备渡河,但只有一条能容纳c人的小船,为了防止野人侵犯修道士,要求无论在何处,修道士的个数不得少于野人的人数(除非修道士个数为0)。如果两种人都会划船,试设计一个算法,确定他们能否渡过河去,若能,则给出一个小船来回次数最少的最佳方案。 要求: (1)用一个三元组(x1,x2,x3)表示渡河过程中各个状态。其中,x1表示起始岸上修道士个数,x2表示起始岸上野人个数,x3表示小船位置(0——在目的岸,1——在起始岸)。例如(2,1,1)表示起始岸上有两个修道士,一个野人,小船在起始岸一边。 采用邻接表做为存储结构,将各种状态之间的迁移图保存下来。 (2)采用广度搜索法,得到首先搜索到的边数最少的一条通路。 (3)输出数据 若问题有解(能渡过河去),则输出一个最佳方案。用三元组表示渡河过程中的状态,并用箭头指出这些状态之间的迁移: 目的状态←…中间状态←…初始状态。 若问题无解,则给出“渡河失败”的信息。 (4)求出所有的解。