传教士野人过河问题---Java版本
本文出处：http://blog.csdn.net/xizhibei
=============================
M个传教士和C个野人（Missionaries and Cannibals）过河，显然必须要M>=C，只有一艘载重为2的小船，野人会听从传教士的安排，并且野人和传教士都会划船，但是，在河的两岸不能出现野人比传教士多的情况，否则野人就会吃传教士。
好了，现在，编程解决这个问题，安排他们全部过河，并保证传教士的安全。
嗯，据说这是个经典的人工智能问题，显然，解决方法是搜索状态空间。于是各种方法就出来了，BFS、DFS还有大名鼎鼎的A*。
首先，规定下状态空间两岸以及船上的传教士还有野人的数量，船的朝向以及，父状态的Index。
private class State implements Comparable<State>{public static final int TO = 0;public static final int FROM = 1;public static final int START = 2;public int lm,lc;public int rm,rc;public int m_in_ship;public int c_in_ship;public int parent;public int direction;public State(int lm,int lc,int rm,int rc,int m_in_ship,int c_in_ship,int parent,int direction){this.lm = lm;this.lc = lc;this.rm = rm;this.rc = rc;this.m_in_ship = m_in_ship;this.c_in_ship = c_in_ship;this.parent = parent;this.direction = direction;}public State getNoParentState(){//显然，需要把父节点的idx去掉才能判断是否重复return new State(lm,lc,rm,rc,m_in_ship,c_in_ship,-1,direction);}public String toString(){if(direction == State.TO)return lm + "," + lc + " =" + m_in_ship + "," + c_in_ship + "=> "+ rm + "," + rc;else if(direction == State.FROM)return lm + "," + lc + " <=" + m_in_ship + "," + c_in_ship + "= "+ rm + "," + rc;elsereturn lm + "," + lc + " =" + m_in_ship + "," + c_in_ship + "= "+ rm + "," + rc;}@Overridepublic int compareTo(State s) {//A*实现的关键，状态的比较，用来启发搜索int sum1 = 2*lm + 2*lc + m_in_ship + c_in_ship;int sum2 = 2*s.lm + 2*s.lc + s.m_in_ship + s.c_in_ship;return sum1 - sum2;}}