精选优质文档-倾情为你奉上6修道士与野人问题这是一个古典问题。假设有n个修道士和n个野人准备渡河，但只有一条能容纳c人的小船，为了防止野人侵犯修道士，要求无论在何处，修道士的个数不得少于野人的人数（除非修道士个数为0）。如果两种人都会划船，试设计一个算法，确定他们能否渡过河去，若能，则给出一个小船来回次数最少的最佳方案。要求：（1）用一个三元组（x1,x2,x3）表示渡河过程中各个状态。其中，x1表示起始岸上修道士个数，x2表示起始岸上野人个数，x3表示小船位置（0在目的岸，1在起始岸）。例如（2,1,1）表示起始岸上有两个修道士，一个野人，小船在起始岸一边。采用邻接表做为存储结构，将各种状态之间的迁移图保存下来。（2）采用广度搜索法，得到首先搜索到的边数最少的一条通路。（3）输出数据若问题有解（能渡过河去），则输出一个最佳方案。用三元组表示渡河过程中的状态，并用箭头指出这些状态之间的迁移：目的状态中间状态初始状态。 若问题无解，则给出“渡河失败”的信息。 （4）求出所有的解。1需求分析
