关于野人与传教士问题的心得
关于野人与传教士问题，自己费了很长时间想这个问题，本以为解出了答案，没想到是错的，我理解错了题意。所以，什么事情，都要有一个正确的目标，否则即使胜力了，也是失败的。
其实，这是一个关于图论的问题。
关于图论的个人理解：
图论会有一个初始状态，还有一个目标状态，初始状态就是一个问题或事物刚开始的状态，目标状态是我们想要达到的状态。它们可以用坐标来表示。
解题过程：
首先，我们要做的是明确问题的初始状态和目标状态。
本题的初始状态是（3，3，1），即在河的左边有3个野人，3个传教士，和一支船。目标状态是（0，0，0），即河的左边有0个野人，0个传教士，和0支船，换句话说，野人、人和船都到了河的右边。
其次，我们要明确从某一状态到下一状态有几种可能的值。
因为船最多自能坐两个人，所以本题中一共有五种状态：1.把本岸的一个传教士送到对岸；2.把本岸的一个野人送到对岸；3.把一个野人和一个传教士送到对岸；4.把两个传教士送到对岸；5.把两个野人送到对岸。
第三，找出不满足条件的状态。本题中即使一岸的野人数大于传教士的状态和数量为负的情况，将其从解中排出。
第四，选取适当的算法，本题中用深度优先搜索就可以。
第五，最好有状态的记录，避免死循环。
微信扫一扫，阅读/分享
