【人工智能】传教士和野人问题（M
摘要本题需要解决的是一般情况下的传教士和野人问题（M-C问题）。通过对问题的一般化，我们用一个三元组定义了问题的状态空间，并根据约束条件制定了一系列的操作规则，最后通过两个启发式函数，来优化搜索过程，并通过讨论，探究两个函数是否能够求解到最优解。
导言有N个传教士和N个野人来到河边渡河，河岸有一条船，每次至多可供k人乘渡。问传教士为了安全起见，应如何规划摆渡方案，使得任何时刻，河两岸以及船上的野人数目总是不超过传教士的数目(否则不安全，传教士有可能被野人吃掉)。即求解传教士和野人从左岸全部摆渡到右岸的过程中，任何时刻满足M(传教士数)≥C(野人数)和M+C≤k的摆渡方案。
实验过程状态空间我们用一个三元组(m，c，b)来表示河岸上的状态，其中m、c分别代表某一岸上传教士与野人的数目，b=1表示船在这一岸，b=0则表示船不在。约束条件是:两岸上M≥C,船上M+C≤2。由于传教士与野人的总数目是一常数，所以只要表示出河的某一岸上的情况就可以了，为方便起见，我们选择传教士与野人开始所在的岸为所要表示的岸，并称其为左岸，另一岸称为右岸。显然仅用描述左岸的三元组就足以表示出整个情况了。综上，我们的状态空间可表示为：(ML，CL，BL)，其中0≤ML，CL≤N，BL∈{0,1}。状态空间的总状态数为(N+1)×(N+1)×2，问题的初始状态是(N，N，1)，目标状态是(0，0，0)。
操作规则该问题主要有两种操作：从左岸划向右岸和从右岸划向左岸，以及每次摆渡的传教士和野人个数。我们可以使用一个2元组（BM，BC）来表示每次摆渡的传教士和野人个数，我们用i代表每次过河的总人数，i=1~k，则每次有BM个传教士和BC=i-BM个野人过河，其中BM=0~i，而且当BM!=0时需要满足BM>=BC。则从左到右的操作为：（ML-BM，CL-BC，B=1），从右到左的操作为：（ML+BM，CL+BC，B=0）。例如当N=3，K=2时，满足条件的（BM，BC）有：（0,1）、（0,2）、（0,3）、（1,0）、（1,1）、（2,0）、（2,1）、（2,2）、（3,0）、（3,1）、（3,2）、（3,3）。由于从左到右与从右到左是对称的，所以此时一共有24种操作。
搜索策略为了避免重复，我们将搜索过的状态记录下来，之后避开搜索这个状态。我们把满足条件的状态称为安全状态，首先要定义出安全状态，通过对问题的分析，不难得出只有满足以下条件之一的状态才是安全的(以左岸为例)：1）传教士与野人的数目相等；2）传教士都在左岸；3）传教士都不在左岸。我们只对安全的状态进行深度优先搜索，直至找到一个合法的解。由于每一次摆渡都有多种操作可以选择，因此我们定义以下启发式函数：F1(x)=ML+CLF2(x)=ML+CL–2B其中F1(x)满足A算法条件的，F2(x)满足A*算法条件。在每次的摆渡中，优先选择F(x)大的操作进行搜索。结果分析1.摆渡方案结果示例
样例1:请输入N：3请输入k：2找到的解为:0个传教士和2个野人从左岸乘船至右岸左岸有3个传教士和1个野人右岸有0个传教士和2个野人0个传教士和1个野人从右岸乘船至左岸左岸有3个传教士和2个野人右岸有0个传教士和1个野人0个传教士和2个野人从左岸乘船至右岸左岸有3个传教士和0个野人右岸有0个传教士和3个野人0个传教士和1个野人从右岸乘船至左岸左岸有3个传教士和1个野人右岸有0个传教士和2个野人2个传教士和0个野人从左岸乘船至右岸左岸有1个传教士和1个野人右岸有2个传教士和2个野人1个传教士和1个野人从右岸乘船至左岸左岸有2个传教士和2个野人右岸有1个传教士和1个野人2个传教士和0个野人从左岸乘船至右岸左岸有0个传教士和2个野人右岸有3个传教士和1个野人0个传教士和1个野人从右岸乘船至左岸左岸有0个传教士和3个野人右岸有3个传教士和0个野人0个传教士和2个野人从左岸乘船至右岸左岸有0个传教士和1个野人右岸有3个传教士和2个野人0个传教士和1个野人从右岸乘船至左岸左岸有0个传教士和2个野人右岸有3个传教士和1个野人0个传教士和2个野人从左岸乘船至右岸左岸有0个传教士和0个野人右岸有3个传教士和3个野人样例2：请输入N：5请输入k：3找到的解为:0个传教士和2个野人从左岸乘船至右岸左岸有5个传教士和3个野人右岸有0个传教士和2个野人0个传教士和1个野人从右岸乘船至左岸左岸有5个传教士和4个野人右岸有0个传教士和1个野人0个传教士和2个野人从左岸乘船至右岸左岸有传教士与野人过河问题 人工智能实验算法
问题描述有N个传教士和N个野人来到河边渡河，河岸有一条船，每次至多可供k人乘渡。问：传教士为了安全起见，应如何规划摆渡方案，使得任何时刻，河两岸以及船上的野人数目总是不超过传教士的数目(否则不安全，传教士有可能被野人吃掉)。即求解传教士和野人从左岸全部摆渡到右岸的过程中，任何时刻满足M(传教土数)≥C野人数)和M+C≤k的摆渡方案。
写在前面传教士与野人过河问题是人工智能里面非常经典的算法题，曾经是2012年360公司的面试题，因此网上有各种各样的解决思路和代码设计，但是我发现网上的算法思路非常好，代码设计的尽管多种多样，但都不满足我今天这个要做的这个项目需求，大部分都是规定好了3个传教士和3个野人，船上最多只能做2人，或者是先按照3人举例，举例完就没了。这样的限制是不符合今天这种需求的，因为今天的问题描述中并没有说明会有几个传教士和野人，只能保证传教士和野人一般多，也没有说明一条船最多做几个人，因此网上大部分代码案例不合题。再有一种就是允许我们输入有多少人和船最多坐多少人，但是他没有找出所有的方案。所以今天就自己动手做一下这个算法。
算法思路这个算法很经典，网上有很多的解题思路，我也看了很多，有一个感觉讲的非常不错的推荐一下，就是CSDN-魏宇轩 前辈的博文，讲解的非常棒，思路很清晰，而且他还使用C语言写了出来，但是我运行出了写问题一直没有搞通，于是自己用C# 写了一个，其中算法设计思路是按照魏宇轩 前辈的思路走的。
算法分析参考各3人渡河，船最多载2人的算法思路。最终项目人数可以自定义。
初始状态：河左岸有3个野人河3个传教士；河右岸有0个野人和0个传教士；船停在左岸，船上有0个人。目标状态：河左岸有0个野人和0个传教士；河右岸有3个野人和3个传教士；船停在右岸，船上有0个人。将整个问题抽象成怎样从初始状态经一系列的中间状态从而达到目标状态，状态的改变是通过划船渡河来引发的。根据要求，共得出以下5中可能的渡河方案：（1）渡2传教士（2）渡2野人（3）渡1野人1传教士（4）渡1传教士（5）渡1野人本程序使用类来定义状态结点，使用集合存储状态结点，使用递归的思想来寻找目标状态。
程序详细执行流程如下首先，包含状态（首次为初始状态）的结构体结点（已存入结构体数组）传入处理函数，然后判断该传入结点状态是否为目标状态。
是则遍历打印结构体数组，打印完成之后，返回递归调用处，顺序执行之后代码（此步骤关系到是否能找到所有过河路径）；
否则继续判断是否该传入结点已存在于结构体数组当中，如存在，不再往下执行，返回递归调用处，顺序执行之后代码；
若不存在，则继续判断该传入状态的人数是否合理（是否出现人物数量小于0的情况等），若不合理，返回递归调用处，顺序执行之后代码；
若合理，则继续判断传教士和野人人数限制条件，即在传教士人数不为0的情况下，野人人数是否大于传教士人数，若大于则出现吃人的情况，也就是说该传入状态也不合理，则返回递归调用处，顺序执行之后代码；
若不满足大于条件，则说明该状态是路径转态，也就是合理的，那么进行五种渡河方案的依次变换，首先为第一种渡河方案，两个传教士过河（注意：此处的5中渡河方案没有固定顺序，也可以是其他渡河方案），那么对该传入状态的左岸和右岸的传教士人数和野人人数进行增减（若为左岸到右岸，则左岸人数减，右岸人数加，此处有一个小技巧见本段末尾）。
增减完成并改变船的状态（使用正负一表示，正一为左岸，负一为右岸）以后就产生了一个新的状态，将该状态存入结构体数组，之后此处又递归调用处理函数，将新产生的转态结点传入，再次进行上述条件限制判断。
若在该判断途中被返回至递归调用处，说明该状态不合理，则此时将已经存入结构体数组的状态结点移出结构体数组，然后程序顺序执行，进行下一个渡河方案的处理，也就是说，此时的处理是对上一个传入结点的操作（因为刚传入的已经移出了）；
若在判断途中未被返回至递归调用处，也就是说，传入的结点合理了，那么又开始从第一种渡河方案开始对该传入状态进行操作。
按照上述过程循环执行，直到出现目标状态，回到本段开头，遍历结构体数组，打印渡河路径结点信息。
完成以后，返回递归调用处，顺序执行之后代码，此后的操作是在寻找其他渡河路径。
原理为：由于该处理函数末尾存在return语句（关键），所以在找到目标状态并返回之后，目标转态结点同样会被移出结构体数组，然后在其上一个结点开始顺序往下执行操作之后的一种渡河方案，查看是否在该结点处，还有其他渡河方案可以达到目标状态，若有则同样按上述方法执行（打印输出），若执行完后面的所有渡河方案，发现都没有能够达到目标状态的结点，则会执行末尾的返回语句，返回之后，该状态结点也会被移除（关键），那么此时操作的状态结点就是上上个结点状态，对其进行其后的渡河方案操作。按照此法，不断往后退，直到所有结点都被移除，此时说明已经完成所有渡河路径的搜索（深度）。至此，本程序的执行过程叙述完毕。
小技巧：从左岸到右岸，和从右岸到左岸的状态变化是不一样的，前者左岸的人数减，右岸的人数加；后者左岸的人数加，右岸的人数减。我们不应单独再写程序来处理，而是应该使用船的转态带入计算来处理，注意，此技巧在于船的转态使用正负一来表示，而不应该是1和0，以及其他表示方法。为什么这么说？因为任何数乘以一，其本身都不会改变（有我也不会承认）。而正负号在此起到关键作用，我们使用正负一去乘以五种渡河方案的改变数值，从而得到的就是我们变换的正确结果，不论左岸右岸，都是正确合理的。
项目关键代码主要用来判断这条方案是否可行。
//是否重复操作for(inti=0;i