该课程设计报告涉及修道士与野人这一问题的探讨。

简介：
这是一个长期存在的难题。 考虑有 *n* 个修道士和 *n* 个野人共同前往河对岸的情况，他们只有一艘能够搭载 *c* 人的小船。为了确保修道士的安全，必须保证在任何时刻，修道士的数量都至少等于野人的数量，除非修道士的数量为零。如果双方都具备划船能力，请设计一个算法，以确定他们是否能够成功渡河，并且若可行，则提供最少来回次数的优化方案。具体要求如下：(1) 为了描述渡河过程中的各个状态，采用三元组 (x1, x2, x3)，其中 x1 代表起始岸上的修道士数量，x2 代表起始岸上的野人数量，x3 表示小船所处的位置（0 代表在目标岸边，1 代表在起始岸边）。例如 (2, 1, 1) 表示起始岸上有两名修道士和一名野人，小船停留在起始岸的一侧。为了便于处理，建议采用邻接表作为存储结构来构建各种状态之间的迁移图。(2) 运用广度优先搜索法来寻找一条首先搜索到的边数最少的通路。(3) 如果问题存在解（即能够成功渡河），则输出一个最优的方案。通过三元组来表示渡河过程中的状态并使用箭头明确指出这些状态之间的转换关系：从目标状态向中间状态再到初始状态。(4) 同时找出所有可能的解决方案。若问题无解（无法渡过河），则输出“渡河失败”的消息。