“巧渡河”问题 ·问题：人、狼、羊、菜用一条只能同时载两位的小船渡河，“狼羊”、 “羊菜”不能在无人在场时共处，当然只有人能架船。 ·图模型：顶点表示“原岸的状态”，两点之间有边当且仅当一次合理 的渡河“操作”能够实现该状态的转变。 ·起始状态是“人狼羊菜”，结束状态是“空”。 ·问题的解：找到一条从起始状态到结束状态的尽可能短的通路。“巧渡河”问题 • 问题：人、狼、羊、菜用一条只能同时载两位的小船渡河，“狼羊”、 “羊菜”不能在无人在场时共处，当然只有人能架船。 • 图模型：顶点表示“原岸的状态”，两点之间有边当且仅当一次合理 的渡河“操作”能够实现该状态的转变。 • 起始状态是“人狼羊菜”，结束状态是“空”。 • 问题的解：找到一条从起始状态到结束状态的尽可能短的通路