作者 欧阳君沛
200506050044
简介搜索
1.广度优先搜索
每次将集合中的元素经过一些改动，分层生成当前状态的子状态（通常还删除父情况），添加到集合（队列）中，以实现遍历或搜索等目的的算法。
Pseudocode (用队列)
1 procedure(state)
2 for each possible next state from this one
3 enqueue next state
4 search()
5 enqueue initial state
6 while not empty(queue)
7 state->get state from queue
8 process(state)
2.深度优先搜索
深度优先搜索属于图算法的一种,英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次.
举例说明之:下图是一个无向图,如果我们从A点发起深度优先搜索(以下的访问次序并不是唯一的,第二个点既可以是B也可以是C,D),则我们可能得到如下 的一个访问过程:A->B->E(没有路了!回溯到A)->C->F->H->G->D(没有路,最终回溯到 A,A也没有未访问的相邻节点,本次搜索结束).
B--E
/
A-C--F
\ >H
D--G
简要说明深度优先搜索的特点:每次深度优先搜索的结果必然是图的一个连通分量.深度优先搜索可以从多点发起.如果将每个节点在深度优先搜索过程中的"结束 时间"排序(具体做法是创建一个list,然后在每个节点的相邻节点都已被访问的情况下,将该节点加入list结尾,然后逆转整个链表),则我们可以得到 所谓的"拓扑排序",即topological sort.
3. 启发式搜索
启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无畏的搜索路径，提 到了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。我们先看看估价是如何表示的。
启发中的估价是用估价函数表示的，如：
f(n) = g(n) + h(n)
其中f(n) 是节点n的估价函数，g(n)实在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。在这里主要是h(n)体现了搜 索的启发信息，因为g(n)是已知的。如果说详细点，g(n)代表了搜索的广度的优先趋势。但是当h(n) >> g(n)时，可以省略g(n)，而提高效率。
传教士与食人魔的故事
1.题目描叙：
Three missionaries and three cannibals come to a river. A rowboat that seats two is available. If the cannibals ever outnumber the missionaries on either bank of the river, the missionaries will be eaten.
How shall they cross the river?
2.分析题意
首先我们来设计状态表示。如何表示一个状态？有2个岸，3个传教士和3个食人魔。
那么怎么样的一个表示能过完全说明一个状态呢？(左岸传教士人数，左岸食人魔人数， 船的位置)就可以了（当然也可以有其他的状态表示，这里这种简洁明了）
当然后面我们会说到扩展题目到一般性。怎么能满足于6个人呢，呵呵。
3.代码实战
写程序之前先考虑下下列问题：
1．内存考虑。由于现在内存很大了，没必要吝啬到每个2进制位，就大方点，int类型吧。当然在做大数据的BFS实现时，内存仍然是很紧的。如有必要可以改成2进制位。也就是把一个int类型当成32个二进制来使用。
2. 栈空间考虑。如果做DFS，内存不用担心了，可是搜索方式不好（比如纯深搜），对于大数据而言很容易爆栈。（所谓爆栈即超出栈的大小），所以，要尽量减少DFS的局部变量使用，或者，用高级方法来搜（比如迭代深搜，爆栈的可能性就大大降低了）。
4.解答源代码一览
java.lang.Object
oyjpart.AI.MissCannSolver
public class MissCannSolver
extends java.lang.Object
本程序用于解决传教士与食人魔问题。
在原有逻辑问题的基础上，本程序将其泛化为任意数目传教士,任意数目食人魔,任意数目载人数问题。 本程序以多种算法为解决方案对问题分别进行求解，相互比较和分析了各种算法，成功解决了任意数目传教士和任意数目食人魔问题。
1. 深度优先搜索
2. 广度优先搜索
3. 迭代深度优先搜索
4. 启发式搜索
本程序原为人工智能【有信息的搜索】一章作业提交，后上传到网上，供广大网友参考。详情请见有信息的搜索
版本：
1.0
作者：
欧阳君沛
|
方法摘要
|
|
boolean
|
checkValid(int leftMiss, int leftCann, int boatAt)
检查一个状态是否合法
|
|
boolean
|
checkValidEmpty(int leftMiss, int leftCann, int boatAt)
检查一个状态是否合法并且不为空(-1)
|
|
boolean
|
checkValidSmaller(int leftMiss, int leftCann, int boatAt, int cost)
检查一个状态是否合法并且小于一个状态值
|
|
boolean
|
DFS(int leftMiss, int leftCann, int boatAt, int depth)
深搜求解
|
|
long
|
initiation()
读入数据，做一些初始化工作 并返回当前系统时间
|
|
boolean
|
ItDFS(int maxLen, int leftMiss, int leftCann, int boatAt, int depth)
深搜求解
|
|
static void
|
main(java.lang.String[] args)
主程序入口
|
|
void
|
OutputAnswer(int depth)
输出解
|
|
void
|
solveInBFS()
Basic 广度优先搜索方案
|
|
void
|
solveInDFS()
Basic 深度优先搜索方案
|
|
void
|
solveInItDFS()
Iterative 迭代深度优先搜索方案
|
|
void
|
solvePuzzle()
求解并输出求解结果 可以使用多种搜索算法来求解问题
|
|
从类 java.lang.Object 继承的方法
|
|
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
|
MissCannSolver
public MissCannSolver()
main
public static void main(java.lang.String[] args)
主程序入口
参数：
args - main参数
solvePuzzle
public void solvePuzzle()
求解并输出求解结果 可以使用多种搜索算法来求解问题
initiation
public long initiation()
读入数据，做一些初始化工作 并返回当前系统时间
solveInDFS
public void solveInDFS()
Basic 深度优先搜索方案
DFS
public boolean DFS(int leftMiss,
int leftCann,
int boatAt,
int depth)
深搜求解
参数：
depth - 深搜层数
返回：
是否找到解
solveInItDFS
public void solveInItDFS()
Iterative 迭代深度优先搜索方案
ItDFS
public boolean ItDFS(int maxLen,
int leftMiss,
int leftCann,
int boatAt,
int depth)
深搜求解
参数：
depth - 深搜层数
maxLen - 最大深搜层数
返回：
是否找到解
solveInBFS
public void solveInBFS()
Basic 广度优先搜索方案
checkValid
public boolean checkValid(int leftMiss,
int leftCann,
int boatAt)
检查一个状态是否合法
checkValidEmpty
public boolean checkValidEmpty(int leftMiss,
int leftCann,
int boatAt)
检查一个状态是否合法并且不为空(-1)
checkValidSmaller
public boolean checkValidSmaller(int leftMiss,
int leftCann,
int boatAt,
int cost)
检查一个状态是否合法并且小于一个状态值
OutputAnswer
public void OutputAnswer(int depth)
输出解
参数：
depth - 解的长度
5. Basic 深度优先搜索方案
先看看我们求解程序的主框架：
/**
* 求解并输出求解结果 可以使用多种搜索算法来求解问题
*/
public void solvePuzzle() {
// 初始化
Scanner cin = new Scanner(System.in);
// 读入传教士和食人魔数目
System.out.println("请输入传教士人数 食人魔的人数 船载容量:");
numOfMiss = cin.nextInt();
numOfCann = cin.nextInt();
capacity = cin.nextInt();
try {
solveInDFS();
solveInItDFS();
solveInBFS();
solveInAStar();
} catch (java.lang.StackOverflowError e) {
// 实际上Error我也处理不了
System.out.println("堆栈溢出，数据过大");
e.printStackTrace();
} catch (OutOfMemoryError e) {
System.out.println("内存溢出，数据过大");
e.printStackTrace();
} catch (Exception e) {
System.out.println("程序运行出现异常, 请检查程序");
e.printStackTrace();
}
}
首先看看基本DFS的过程。
在所有算法的执行之前，都会先执行initiation，做一些初始化的工作。
/**
* Basic 深度优先搜索方案
*/
public void solveInDFS() {
System.out.println("现在使用Basic 深度优先搜索方案:");
long begin = initiation();
boolean answer = DFS(numOfMiss, numOfCann, 0, 0);
if (!answer) {
System.out.println("不存在解!");
}
System.out.println("Time elapsed: "
+ (System.currentTimeMillis() - begin) + " minisecs.\n");
}
在initiation中对DP数组初始化为-1
dp数组在本程序中的作用实际上是多样的。在DFS中，他仅仅作为一个判重的标记，以避免DFS进入无限的深层。
在BFS中，由于对于本题，每一次状态转移的代价都是1，因此也是仅仅作为一个判重的标记，使活节点表中的节点
没有重复。在启发式搜索中，dp数组作为一个状态的当前最小值使用，来尽可能的减少活节点表中的节点数。
/**
* 读入数据，做一些初始化工作 并返回当前系统时间
*/
public long initiation() {
dp = new int[numOfMiss + 1][numOfCann + 1][2];
for (int i = 0; i < numOfMiss + 1; ++i) {
for (int j = 0; j < numOfCann + 1; ++j) {
dp[i][j][0] = dp[i][j][1] = -1;
}
}
return System.currentTimeMillis();
}
下面是深度优先搜索求解的代码
/**
* 深搜求解
* @param depth
* 深搜层数
* @return 是否找到解
*/
public boolean DFS(int leftMiss, int leftCann, int boatAt, int depth) {
dp[leftMiss][leftCann][boatAt] = depth;
if (leftMiss == 0 && leftCann == 0) {
OutputAnswer(depth);
return true;
}
int i, j;
if (boatAt == 0) {
for (i = 0; i <= leftMiss && i <= capacity; ++i) {
for (j = 0; j <= leftCann && i + j <= capacity; ++j) {
if (i + j != 0) {
if (checkValidEmpty(leftMiss - i, leftCann - j,
1 - boatAt)) {
steps[depth] = new Transport(i, j, boatAt);
if (DFS(leftMiss - i, leftCann - j, 1 - boatAt,
depth + 1))
return true;
}
}
}
}
} else {
int rightMiss = numOfMiss - leftMiss;
int rightCann = numOfCann - leftCann;
for (i = 0; i <= rightMiss && i <= capacity; ++i) {
for (j = 0; j <= rightCann && i + j <= capacity; ++j) {
if (i + j != 0) {
if (checkValidEmpty(leftMiss + i, leftCann + j,
1 - boatAt)) {
steps[depth] = new Transport(i, j, boatAt);
if (DFS(leftMiss + i, leftCann + j, 1 - boatAt,
depth + 1))
return true;
}
}
}
}
}
return false;
}
从上面的代码可以看到，DFS就是沿着解空间的深层次走，没有解的时候回溯就可以了
关于输出解的过程主要有下列代码搞定：
/**
* 这是一个辅助类，用于记录每一次行进的情况, 主要用于输出解
*/
public class Transport {
/** 船行进前所在的位置 */
private int boatAt;
/**
* 行进时船上载的人 a为传教士数目 b为食人魔数目
*/
private int a, b;
public Transport(int a, int b, int boatAt) {
super();
this.boatAt = boatAt;
this.a = a;
this.b = b;
}
public String toString() {
String s = "";
if (boatAt == 0) {
s += "----->>> ";
} else {
s += "<<<----- ";
}
s += "载人 : [";
if (a != 0)
s += " 传教士" + a + "人 ";
if (b != 0)
s += " 食人魔" + b + "人 ";
s += " ]";
return s;
}
}
/**
* 输出解
* @param depth
* 解的长度
*/
public void OutputAnswer(int depth) {
System.out.println("已经找到解!");
System.out.println("一共需要" + depth + "步:");
for (int i = 0; i < depth; ++i) {
System.out.println(steps[i].toString());
}
}
6. 迭代深度优先搜索
迭代深度优先搜索其实就是限制最大深度，再做DFS。
这样做的好处在于，解决了DFS的局限性（容易陷入深层），而有时候题目的解却浮在表层。
虽然BFS可以很好的解决解比较浅的问题，可是有些问题，状态空间太大，内存无法满足状态
需要，这个时候只好采用迭代加深DFS。当然迭代加深DFS也是有很多缺点的，由于每一次迭代深度
都会重新对状态空间做DFS，因此解比较深的时间耗费可能很大…
/**
* Iterative 迭代深度优先搜索方案
*/
public void solveInItDFS() {
System.out.println("现在使用Iterative 迭代深度优先搜索方案:");
long begin = initiation();
int i;
for (i = 5; i <= maxLen; ++i) {
if (ItDFS(i, numOfMiss, numOfCann, 0, 0))
break;
initiation();
}
if (i == maxLen + 1)
System.out.println("不存在解!");
System.out.println("Time elapsed: "
+ (System.currentTimeMillis() - begin) + " minisecs.\n");
}
/**
* 深搜求解
* @param depth
* 深搜层数
* @param maxLen
* 最大深搜层数
* @return 是否找到解
*/
public boolean ItDFS(int maxLen, int leftMiss, int leftCann, int boatAt,
int depth) {
if (depth == maxLen) {
return false;
}
dp[leftMiss][leftCann][boatAt] = depth;
if (leftMiss == 0 && leftCann == 0) {
OutputAnswer(depth);
return true;
}
int i, j;
if (boatAt == 0) {
for (i = 0; i <= leftMiss && i <= capacity; ++i) {
for (j = 0; j <= leftCann && i + j <= capacity; ++j) {
if (i + j != 0) {
if (checkValidSmaller(leftMiss - i, leftCann - j,
1 - boatAt, depth + 1)) {
steps[depth] = new Transport(i, j, boatAt);
if (ItDFS(maxLen, leftMiss - i, leftCann - j,
1 - boatAt, depth + 1))
return true;
}
}
}
}
} else {
int rightMiss = numOfMiss - leftMiss;
int rightCann = numOfCann - leftCann;
for (i = 0; i <= rightMiss && i <= capacity; ++i) {
for (j = 0; j <= rightCann && i + j <= capacity; ++j) {
if (i + j != 0) {
if (checkValidSmaller(leftMiss + i, leftCann + j,
1 - boatAt, depth + 1)) {
steps[depth] = new Transport(i, j, boatAt);
if (ItDFS(maxLen, leftMiss + i, leftCann + j,
1 - boatAt, depth + 1))
return true;
}
}
}
}
}
return false;
}
7. 广度优先搜索
广度优先搜索其实很简单，就是对状态空间一层一层的搜。为了实现这个过程，可以借助队列的FIFO（First In First Out）性质。
然后要说的是如果构造最优解了。构造最优解比较好的方法是记录一个状态的前驱节点。在队列中也就是记录前驱节点的下标就可以了。由于LinkedList对内部结构封装的太紧密，我无法看到内部的节点，只好自己用ArrayList实现了队列结构。
/**
* Basic 广度优先搜索方案
*/
public void solveInBFS() {
System.out.println("现在使用Basic 广度优先搜索方案");
long begin = initiation();
List<Status> queue = new ArrayList<Status>();
queue.add(new Status(numOfMiss, numOfCann, 0, -1));
int front = 0, tail = 1;
boolean solution = false;
while (front < tail) {
Status now = queue.get(front++);
int leftMiss = now.leftMiss;
int leftCann = now.leftCann;
int boatAt = now.boatAt;
if (now.leftCann == 0 && now.leftMiss == 0) {
int idx = front - 1;
List<Status> optimalRoute = new ArrayList<Status>();
while (idx != -1) {
optimalRoute.add(queue.get(idx));
idx = queue.get(idx).father;
}
Collections.reverse(optimalRoute);
Status[] op = new Status[optimalRoute.size()];
optimalRoute.toArray(op);
for (int i = 0; i < op.length - 1; ++i) {
if (op[i].boatAt == 0) {
steps[i] = new Transport(op[i].leftMiss
- op[i + 1].leftMiss, op[i].leftCann
- op[i + 1].leftCann, op[i].boatAt);
}
}
OutputAnswer(op.length - 1);
solution = true;
break;
}
int i, j;
if (boatAt == 0) {
for (i = 0; i <= leftMiss && i <= capacity; ++i) {
for (j = 0; j <= leftCann && i + j <= capacity; ++j) {
if (i + j != 0) {
if (checkValidEmpty(leftMiss - i, leftCann - j,
1 - boatAt)) {
queue.add(new Status(leftMiss - i,
leftCann - j, 1 - boatAt, front - 1));
tail++;
dp[leftMiss - i][leftCann - j][1 - boatAt] = 1;
}
}
}
}
} else {
int rightMiss = numOfMiss - leftMiss;
int rightCann = numOfCann - leftCann;
for (i = 0; i <= rightMiss && i <= capacity; ++i) {
for (j = 0; j <= rightCann && i + j <= capacity; ++j) {
if (i + j != 0) {
if (checkValidEmpty(leftMiss + i, leftCann + j,
1 - boatAt)) {
queue.add(new Status(leftMiss + i,
leftCann + j, 1 - boatAt, front - 1));
tail++;
dp[leftMiss + i][leftCann + j][1 - boatAt] = 1;
}
}
}
}
}
}
if (!solution)
System.out.println("不存在解!");
queue.clear();
System.out.println("Time elapsed: "
+ (System.currentTimeMillis() - begin) + " minisecs.\n");
}
8.启发式搜索
启发式搜索可以在BFS上面添加一些东西来实现。
首先就是要有启发函数F(x). F(x)是对某节点未来需要的路径的一个估价。利用已有代价+估计代价的和作为优先级，对活节点表中的节点进行排序。
这个排序的过程真的需要排序吗？我们用优先级队列就可以了。插入的过程是o(nlogn)的。优先级队列是怎么实现的呢？嘿嘿，其实很简单，就是用堆来实现的。
我的启发式函数是(numOfMiss + numOfCann + boatAt - 1) / (capacity - 1);
/**
* 启发式搜索方案
*/
private void solveInAStar() {
System.out.println("现在使用启发式搜索方案");
Transport[][][] pre = new Transport[numOfMiss + 1][numOfCann + 1][2];
long begin = initiation();
Queue<Status> queue = new PriorityQueue<Status>();
queue.add(new Status(numOfMiss, numOfCann, 0, -1, 0 + calF(numOfMiss,
numOfCann, 0)));
pre[numOfMiss][numOfCann][0] = new Transport(-1, -1, -1);
dp[numOfMiss][numOfCann][0] = 0;
boolean solution = false;
while (!queue.isEmpty()) {
Status now = queue.remove();
int leftMiss = now.leftMiss;
int leftCann = now.leftCann;
int boatAt = now.boatAt;
// System.out.printf("%d %d %d %d\n", leftMiss, leftCann, boatAt,
// now.cost);
if (leftCann == 0 && leftMiss == 0) {
int idx = 0;
while (true) {
Transport t = pre[leftMiss][leftCann][boatAt];
if (t.a == -1)
break;
steps[idx++] = t;
if (t.boatAt == 0) {
leftMiss += t.a;
leftCann += t.b;
} else {
leftMiss -= t.a;
leftCann -= t.b;
}
boatAt = 1 - boatAt;
}
for (int i = 0, j = idx - 1; i < j; ++i, --j) {
Transport tmp = steps[i];
steps[i] = steps[j];
steps[j] = tmp;
}
OutputAnswer(idx);
solution = true;
break;
}
int i, j;
if (boatAt == 0) {
for (i = 0; i <= leftMiss && i <= capacity; ++i) {
for (j = 0; j <= leftCann && i + j <= capacity; ++j) {
if (i + j != 0) {
if (checkValidSmaller(leftMiss - i, leftCann - j,
1 - boatAt, now.cost + 1)) {
queue.add(new Status(leftMiss - i,
leftCann - j, 1 - boatAt, -1, now.cost
+ 1
+ calF(leftMiss - i, leftCann
- j, 1 - boatAt)));
dp[leftMiss - i][leftCann - j][1 - boatAt] = now.cost + 1;
pre[leftMiss - i][leftCann - j][1 - boatAt] = new Transport(
i, j, boatAt);
}
}
}
}
} else {
int rightMiss = numOfMiss - leftMiss;
int rightCann = numOfCann - leftCann;
for (i = 0; i <= rightMiss && i <= capacity; ++i) {
for (j = 0; j <= rightCann && i + j <= capacity; ++j) {
if (i + j != 0) {
if (checkValidSmaller(leftMiss + i, leftCann + j,
1 - boatAt, now.cost + 1)) {
queue.add(new Status(leftMiss + i,
leftCann + j, 1 - boatAt, -1, now.cost
+ 1
+ calF(leftMiss + i, leftCann
+ j, 1 - boatAt)));
dp[leftMiss + i][leftCann + j][1 - boatAt] = now.cost + 1;
pre[leftMiss + i][leftCann + j][1 - boatAt] = new Transport(
i, j, boatAt);
}
}
}
}
}
}
if (!solution)
System.out.println("不存在解!");
queue.clear();
System.out.println("Time elapsed: "
+ (System.currentTimeMillis() - begin) + " minisecs.\n");
}
private int calF(int numOfMiss, int numOfCann, int boatAt) {
return (numOfMiss + numOfCann + boatAt - 1) / (capacity - 1);
}
9．结果分析
a) 一般结果
请输入传教士人数 食人魔的人数 船载容量:
3 3 3
现在使用Basic 深度优先搜索方案:
已经找到解!
一共需要11步:
----->>> 载人 : [ 食人魔2人 ]
<<<----- 载人 : [ 食人魔1人 ]
----->>> 载人 : [ 食人魔2人 ]
<<<----- 载人 : [ 食人魔1人 ]
----->>> 载人 : [ 传教士2人 ]
<<<----- 载人 : [ 传教士1人 食人魔1人 ]
----->>> 载人 : [ 传教士2人 ]
<<<----- 载人 : [ 食人魔1人 ]
----->>> 载人 : [ 食人魔2人 ]
<<<----- 载人 : [ 食人魔1人 ]
----->>> 载人 : [ 食人魔2人 ]
Time elapsed: 0 minisecs.
现在使用Iterative 迭代深度优先搜索方案:
已经找到解!
一共需要5步:
----->>> 载人 : [ 食人魔2人 ]
<<<----- 载人 : [ 食人魔1人 ]
----->>> 载人 : [ 传教士3人 ]
<<<----- 载人 : [ 食人魔1人 ]
----->>> 载人 : [ 食人魔3人 ]
Time elapsed: 0 minisecs.
现在使用Basic 广度优先搜索方案
已经找到解!
一共需要5步:
----->>> 载人 : [ 食人魔2人 ]
<<<----- 载人 : [ 食人魔1人 ]
----->>> 载人 : [ 传教士3人 ]
<<<----- 载人 : [ 食人魔1人 ]
----->>> 载人 : [ 食人魔3人 ]
Time elapsed: 16 minisecs.
现在使用启发式搜索方案
已经找到解!
一共需要5步:
----->>> 载人 : [ 食人魔3人 ]
<<<----- 载人 : [ 食人魔1人 ]
----->>> 载人 : [ 传教士3人 ]
<<<----- 载人 : [ 传教士1人 ]
----->>> 载人 : [ 传教士1人 食人魔1人 ]
Time elapsed: 0 minisecs.
Copyright (C) 2008 Ouyang Junpei, All Rights Reserved.
b)大数据测试（没有贴出方案，太长）
请输入传教士人数 食人魔的人数 船载容量:
100 100 5
现在使用Basic 深度优先搜索方案:
已经找到解!
一共需要205步:
Time elapsed: 32 minisecs.
现在使用Iterative 迭代深度优先搜索方案:
已经找到解!
一共需要193步:
Time elapsed: 1015 minisecs.
现在使用Basic 广度优先搜索方案
已经找到解!
一共需要193步:
Time elapsed: 16 minisecs.
现在使用启发式搜索方案
已经找到解!
一共需要193步:
Time elapsed: 31 minisecs.
Copyright (C) 2008 Ouyang Junpei, All Rights Reserved.
上面完全体现了解比较深层的时候迭代加深吃亏的情形。
c) 单纯DFS的适用情况
请输入传教士人数 食人魔的人数 船载容量:
10 10 5
现在使用Basic 深度优先搜索方案:
Time elapsed: 0 minisecs.
请输入传教士人数 食人魔的人数 船载容量:
100 100 50
现在使用Basic 深度优先搜索方案:
Time elapsed: 0 minisecs.
请输入传教士人数 食人魔的人数 船载容量:
1000 1000 500
现在使用Basic 深度优先搜索方案:
Time elapsed: 812 minisecs.
请输入传教士人数 食人魔的人数 船载容量:
10000 10000 5000
现在使用Basic 深度优先搜索方案:
内存溢出，数据过大
java.lang.OutOfMemoryError: Java heap space
at oyjpart.AI.MissCannSolver.initiation(MissCannSolver.java:173)
请输入传教士人数 食人魔的人数 船载容量:
1000 999 3
现在使用Basic 深度优先搜索方案:
堆栈溢出，数据过大
java.lang.StackOverflowError
at oyjpart.AI.MissCannSolver.DFS(MissCannSolver.java:239)
10000 * 10000 * 500的数据两对于DFS来说够呛，内存都爆了，同时我们看到解比较深层的时候DFS也面临爆栈的危险。
DFS的使用情况看来和船载容量非常有关联，这个决定了分支的多少
d)迭代深搜的情况
请输入传教士人数 食人魔的人数 船载容量:
10 10 5
现在使用Iterative 迭代深度优先搜索方案:
Time elapsed: 0 minisecs.
请输入传教士人数 食人魔的人数 船载容量:
100 100 50
现在使用Iterative 迭代深度优先搜索方案:
Time elapsed: 109 minisecs.
请输入传教士人数 食人魔的人数 船载容量:
1000 1000 500
现在使用Iterative 迭代深度优先搜索方案:
等待时间太长，我关闭了程序
请输入传教士人数 食人魔的人数 船载容量:
10000 10000 5000
现在使用Iterative 迭代深度优先搜索方案:
等待时间太长，我关闭了程序
请输入传教士人数 食人魔的人数 船载容量:
1000 999 3
现在使用Iterative 迭代深度优先搜索方案:
等待时间太长，我关闭了程序
果然，迭代深搜在解比较深的情况下，完全是无能为力啊。
但是，迭代深搜跟DFS比起来，是可以找到最优解的。下面我们看个例子
请输入传教士人数 食人魔的人数 船载容量:
11 2 5
现在使用Basic 深度优先搜索方案:
已经找到解!
一共需要41步:
----->>> 载人 : [ 食人魔2人 ]
<<<----- 载人 : [ 食人魔1人 ]
----->>> 载人 : [ 传教士1人 ]
<<<----- 载人 : [ 食人魔1人 ]
----->>> 载人 : [ 传教士1人 食人魔1人 ]
<<<----- 载人 : [ 食人魔1人 ]
----->>> 载人 : [ 食人魔2人 ]
<<<----- 载人 : [ 食人魔1人 ]
----->>> 载人 : [ 传教士1人 ]
<<<----- 载人 : [ 食人魔1人 ]
----->>> 载人 : [ 食人魔2人 ]
<<<----- 载人 : [ 食人魔1人 ]
----->>> 载人 : [ 传教士1人 ]
<<<----- 载人 : [ 食人魔1人 ]
----->>> 载人 : [ 食人魔2人 ]
<<<----- 载人 : [ 食人魔1人 ]
----->>> 载人 : [ 传教士1人 ]
<<<----- 载人 : [ 食人魔1人 ]
----->>> 载人 : [ 食人魔2人 ]
<<<----- 载人 : [ 食人魔1人 ]
----->>> 载人 : [ 传教士1人 ]
<<<----- 载人 : [ 食人魔1人 ]
----->>> 载人 : [ 食人魔2人 ]
<<<----- 载人 : [ 食人魔1人 ]
----->>> 载人 : [ 传教士1人 ]
<<<----- 载人 : [ 食人魔1人 ]
----->>> 载人 : [ 食人魔2人 ]
<<<----- 载人 : [ 食人魔1人 ]
----->>> 载人 : [ 传教士1人 ]
<<<----- 载人 : [ 食人魔1人 ]
----->>> 载人 : [ 食人魔2人 ]
<<<----- 载人 : [ 食人魔1人 ]
----->>> 载人 : [ 传教士1人 ]
<<<----- 载人 : [ 食人魔1人 ]
----->>> 载人 : [ 食人魔2人 ]
<<<----- 载人 : [ 食人魔1人 ]
----->>> 载人 : [ 传教士1人 食人魔1人 ]
<<<----- 载人 : [ 食人魔1人 ]
----->>> 载人 : [ 传教士1人 ]
<<<----- 载人 : [ 食人魔1人 ]
----->>> 载人 : [ 食人魔2人 ]
Time elapsed: 0 minisecs.
现在使用Iterative 迭代深度优先搜索方案:
已经找到解!
一共需要5步:
----->>> 载人 : [ 传教士3人 食人魔2人 ]
<<<----- 载人 : [ 食人魔1人 ]
----->>> 载人 : [ 传教士4人 食人魔1人 ]
<<<----- 载人 : [ 食人魔1人 ]
----->>> 载人 : [ 传教士4人 食人魔1人 ]
Time elapsed: 15 minisecs.
e) BFS的情况
请输入传教士人数 食人魔的人数 船载容量:
10 10 5
现在使用Basic 广度优先搜索方案
Time elapsed: 0 minisecs.
请输入传教士人数 食人魔的人数 船载容量:
100 100 50
现在使用Basic 广度优先搜索方案
Time elapsed: 31 minisecs.
请输入传教士人数 食人魔的人数 船载容量:
1000 1000 500
现在使用Basic 广度优先搜索方案
Time elapsed: 9250 minisecs.
效果还可以，不过数据两再大的话，内存要爆掉
f) 启发式搜索的情况
请输入传教士人数 食人魔的人数 船载容量:
10 10 5
现在使用启发式搜索方案
Time elapsed: 16 minisecs.
请输入传教士人数 食人魔的人数 船载容量:
100 100 50
现在使用启发式搜索方案
Time elapsed: 16 minisecs.
请输入传教士人数 食人魔的人数 船载容量:
500 500 250
现在使用启发式搜索方案
Time elapsed: 1110 minisecs.
请输入传教士人数 食人魔的人数 船载容量:
1000 1000 100
现在使用启发式搜索方案
Time elapsed: 375 minisecs.
启发式搜索在大部分情况下效果令人满意
G)综合比较
请输入传教士人数 食人魔的人数 船载容量:
20 20 7
现在使用Basic 深度优先搜索方案:
Time elapsed: 0 minisecs.
现在使用Iterative 迭代深度优先搜索方案:
Time elapsed: 0 minisecs.
现在使用Basic 广度优先搜索方案
Time elapsed: 0 minisecs.
现在使用启发式搜索方案
Time elapsed: 0 minisecs.
大家都很快！
请输入传教士人数 食人魔的人数 船载容量:
100 345 34
现在使用Basic 深度优先搜索方案:
不存在解!
Time elapsed: 0 minisecs.
现在使用Iterative 迭代深度优先搜索方案:
不存在解!
Time elapsed: 5391 minisecs.
现在使用Basic 广度优先搜索方案
不存在解!
Time elapsed: 0 minisecs.
现在使用启发式搜索方案
不存在解!
Time elapsed: 0 minisecs.
我限制了Iterative的最大深度为300层，看吧，很吃力的搜索。
请输入传教士人数 食人魔的人数 船载容量:
200 150 4
现在使用Basic 深度优先搜索方案:
堆栈溢出，数据过大
请输入传教士人数 食人魔的人数 船载容量:
200 150 4
现在使用Basic 广度优先搜索方案
Time elapsed: 31 minisecs.
现在使用启发式搜索方案
Time elapsed: 31 minisecs.
现在使用Iterative 迭代深度优先搜索方案:
等待时间太长，我关闭了程序
BFS和A*搜索表现都非常出色！
请输入传教士人数 食人魔的人数 船载容量:
500 500 39
现在使用Basic 深度优先搜索方案:
Time elapsed: 16 minisecs.
现在使用Basic 广度优先搜索方案
Time elapsed: 46 minisecs.
现在使用启发式搜索方案
Time elapsed: 47 minisecs.
现在使用Iterative 迭代深度优先搜索方案:
等待时间太长，我关闭了程序
大数据也能很快出解！
10.总结
深度优先搜索和广度优先搜索是最基本的搜索方式，前者的优点是空间小，后者的优点是能找到最优解。
迭代深度优先搜索其实就是限制最大深度，再做DFS。
这样做的好处在于，解决了DFS的局限性（容易陷入深层），而有时候题目的解却浮在表层。
虽然BFS可以很好的解决解比较浅的问题，可是有些问题，状态空间太大，内存无法满足状态
需要，这个时候只好采用迭代加深DFS。当然迭代加深DFS也是有很多缺点的，由于每一次迭代深度
都会重新对状态空间做DFS，因此解比较深的时间耗费可能很大…
启发式搜索如果启发函数设计的好的话，能够较快的找到解。但是如果启发函数一般的化，反而会因为优先队列
的速度消耗而使搜索效率降低。本题对于任意船只的启发函数设计的不够好，为了满足可行性，
很难找到贴近实际代价的函数。
Souce：
/**//*
* Copyright (C) 2008 Ouyang Junpei, All Rights Reserved.
*/
package oyjpart.AI;
import java.util.*;
/** *//**
* <p>
* 本程序用于解决传教士与食人魔问题。
* </p>
* <p>
* 在原有逻辑问题的基础上，本程序将其泛化为任意数目传教士,任意数目食人魔,任意数目载人数问题。
* 本程序以多种算法为解决方案对问题分别进行求解，相互比较和分析了各种算法，成功解决了任意数目传教士和任意数目食人魔问题。
* <ol>
* <li>深度优先搜索</li>
* <li>广度优先搜索</li>
* <li>迭代深度优先搜索</li>
* <li>启发式搜索</li>
* </ol>
* <p>
* <p>
* 本程序原为人工智能【有信息的搜索】一章作业提交，后上传到网上，供广大网友参考。 详情请见<a
* href="http://www.cppblog.com/sicheng">有信息的搜索</a>
* </p>
* @author 欧阳君沛
* @version 1.0
*/
public class MissCannSolver 
{
/** *//** 传教士数目 */
private int numOfMiss;
/** *//** 食人魔数目 */
private int numOfCann;
/** *//** 船载容量 */
private int capacity;
/** *//** 行进的过程的记录数组 */
private Transport[] steps = new Transport[10000];
/** *//** DFS判重和动态规划用 */
int[][][] dp;
/** *//** 迭代深搜中的最大深度限制 */
private int maxLen = 300;
/** *//**
* 这是一个辅助类，用于记录每一次行进的情况, 主要用于输出解
*/
public class Transport {
/** *//** 船行进前所在的位置 */
private int boatAt;
/** *//**
* 行进时船上载的人 a为传教士数目 b为食人魔数目
*/
private int a, b;
public Transport(int a, int b, int boatAt) {
super();
this.boatAt = boatAt;
this.a = a;
this.b = b;
}
public String toString() {
String s = "";
if (boatAt == 0) {
s += "----->>> ";
} else {
s += "<<<----- ";
}
s += "载人 : [";
if (a != 0)
s += " 传教士" + a + "人 ";
if (b != 0)
s += " 食人魔" + b + "人 ";
s += " ]";
return s;
}
}
/** *//**
* 用于状态的记录的辅助类
*/
public class Status implements Comparable {
/** *//** 当前船所在的位置 0：左岸 1：右岸 */
private int boatAt;
/** *//** 用于区别不同代价的相同状态 */
private int cost;
/** *//** 用于基本广搜,启发式搜索 */
private int father;
/** *//** 左岸的传教士数目和左岸的食人魔数目 */
private int leftMiss, leftCann;
public Status(int leftMiss, int leftCann, int boatAt, int father) {
super();
this.boatAt = boatAt;
this.leftMiss = leftMiss;
this.leftCann = leftCann;
this.father = father;
}
public Status(int leftMiss, int leftCann, int boatAt, int father,
int cost) {
super();
this.boatAt = boatAt;
this.cost = cost;
this.father = father;
this.leftMiss = leftMiss;
this.leftCann = leftCann;
}
public int compareTo(Object arg0) {
Status b = (Status) arg0;
return this.cost - b.cost;
}
}
/** *//**
* 主程序入口
* @param args
* main参数
*/
public static void main(String[] args) {
new MissCannSolver().solvePuzzle();
System.out
.println("\nCopyright (C) 2008 Ouyang Junpei, All Rights Reserved.\n");
}
/** *//**
* 求解并输出求解结果 可以使用多种搜索算法来求解问题
*/
public void solvePuzzle() {
// 初始化
Scanner cin = new Scanner(System.in);
// 读入传教士和食人魔数目
System.out.println("请输入传教士人数 食人魔的人数 船载容量:");
numOfMiss = cin.nextInt();
numOfCann = cin.nextInt();
capacity = cin.nextInt();
try {
solveInDFS();
solveInBFS();
solveInAStar();
solveInItDFS();
} catch (java.lang.StackOverflowError e) {
// 实际上Error我也处理不了
System.out.println("堆栈溢出，数据过大");
e.printStackTrace();
} catch (OutOfMemoryError e) {
System.out.println("内存溢出，数据过大");
e.printStackTrace();
} catch (Exception e) {
System.out.println("程序运行出现异常, 请检查程序");
e.printStackTrace();
}
}
/** *//**
* 读入数据，做一些初始化工作 并返回当前系统时间
*/
public long initiation() {
dp = new int[numOfMiss + 1][numOfCann + 1][2];
for (int i = 0; i < numOfMiss + 1; ++i) {
for (int j = 0; j < numOfCann + 1; ++j) {
dp[i][j][0] = dp[i][j][1] = -1;
}
}
return System.currentTimeMillis();
}
/** *//**
* Basic 深度优先搜索方案
*/
public void solveInDFS() {
System.out.println("现在使用Basic 深度优先搜索方案:");
long begin = initiation();
boolean answer = DFS(numOfMiss, numOfCann, 0, 0);
if (!answer) {
System.out.println("不存在解!");
}
System.out.println("Time elapsed: "
+ (System.currentTimeMillis() - begin) + " minisecs.\n");
}
/** *//**
* 深搜求解
* @param depth
* 深搜层数
* @return 是否找到解
*/
public boolean DFS(int leftMiss, int leftCann, int boatAt, int depth) {
dp[leftMiss][leftCann][boatAt] = depth;
if (leftMiss == 0 && leftCann == 0) {
OutputAnswer(depth);
return true;
}
int i, j;
if (boatAt == 0) {
for (i = 0; i <= leftMiss && i <= capacity; ++i) {
for (j = 0; j <= leftCann && i + j <= capacity; ++j) {
if (i + j != 0) {
if (checkValidEmpty(leftMiss - i, leftCann - j,
1 - boatAt)) {
steps[depth] = new Transport(i, j, boatAt);
if (DFS(leftMiss - i, leftCann - j, 1 - boatAt,
depth + 1))
return true;
}
}
}
}
} else {
int rightMiss = numOfMiss - leftMiss;
int rightCann = numOfCann - leftCann;
for (i = 0; i <= rightMiss && i <= capacity; ++i) {
for (j = 0; j <= rightCann && i + j <= capacity; ++j) {
if (i + j != 0) {
if (checkValidEmpty(leftMiss + i, leftCann + j,
1 - boatAt)) {
steps[depth] = new Transport(i, j, boatAt);
if (DFS(leftMiss + i, leftCann + j, 1 - boatAt,
depth + 1))
return true;
}
}
}
}
}
return false;
}
/** *//**
* Iterative 迭代深度优先搜索方案
*/
public void solveInItDFS() {
System.out.println("现在使用Iterative 迭代深度优先搜索方案:");
long begin = initiation();
int i;
for (i = 5; i <= maxLen; ++i) {
if (ItDFS(i, numOfMiss, numOfCann, 0, 0))
break;
initiation();
}
if (i == maxLen + 1)
System.out.println("不存在解!");
System.out.println("Time elapsed: "
+ (System.currentTimeMillis() - begin) + " minisecs.\n");
}
/** *//**
* 深搜求解
* @param depth
* 深搜层数
* @param maxLen
* 最大深搜层数
* @return 是否找到解
*/
public boolean ItDFS(int maxLen, int leftMiss, int leftCann, int boatAt,
int depth) {
if (depth == maxLen) {
return false;
}
dp[leftMiss][leftCann][boatAt] = depth;
if (leftMiss == 0 && leftCann == 0) {
OutputAnswer(depth);
return true;
}
int i, j;
if (boatAt == 0) {
for (i = 0; i <= leftMiss && i <= capacity; ++i) {
for (j = 0; j <= leftCann && i + j <= capacity; ++j) {
if (i + j != 0) {
if (checkValidSmaller(leftMiss - i, leftCann - j,
1 - boatAt, depth + 1)) {
steps[depth] = new Transport(i, j, boatAt);
if (ItDFS(maxLen, leftMiss - i, leftCann - j,
1 - boatAt, depth + 1))
return true;
}
}
}
}
} else {
int rightMiss = numOfMiss - leftMiss;
int rightCann = numOfCann - leftCann;
for (i = 0; i <= rightMiss && i <= capacity; ++i) {
for (j = 0; j <= rightCann && i + j <= capacity; ++j) {
if (i + j != 0) {
if (checkValidSmaller(leftMiss + i, leftCann + j,
1 - boatAt, depth + 1)) {
steps[depth] = new Transport(i, j, boatAt);
if (ItDFS(maxLen, leftMiss + i, leftCann + j,
1 - boatAt, depth + 1))
return true;
}
}
}
}
}
return false;
}
/** *//**
* Basic 广度优先搜索方案
*/
public void solveInBFS() {
System.out.println("现在使用Basic 广度优先搜索方案");
long begin = initiation();
List<Status> queue = new ArrayList<Status>();
queue.add(new Status(numOfMiss, numOfCann, 0, -1));
int front = 0, tail = 1;
boolean solution = false;
while (front < tail) {
Status now = queue.get(front++);
int leftMiss = now.leftMiss;
int leftCann = now.leftCann;
int boatAt = now.boatAt;
if (now.leftCann == 0 && now.leftMiss == 0) {
int idx = front - 1;
List<Status> optimalRoute = new ArrayList<Status>();
while (idx != -1) {
optimalRoute.add(queue.get(idx));
idx = queue.get(idx).father;
}
Collections.reverse(optimalRoute);
Status[] op = new Status[optimalRoute.size()];
optimalRoute.toArray(op);
for (int i = 0; i < op.length - 1; ++i) {
if (op[i].boatAt == 0) {
steps[i] = new Transport(op[i].leftMiss
- op[i + 1].leftMiss, op[i].leftCann
- op[i + 1].leftCann, op[i].boatAt);
}
}
OutputAnswer(op.length - 1);
solution = true;
break;
}
int i, j;
if (boatAt == 0) {
for (i = 0; i <= leftMiss && i <= capacity; ++i) {
for (j = 0; j <= leftCann && i + j <= capacity; ++j) {
if (i + j != 0) {
if (checkValidEmpty(leftMiss - i, leftCann - j,
1 - boatAt)) {
queue.add(new Status(leftMiss - i,
leftCann - j, 1 - boatAt, front - 1));
tail++;
dp[leftMiss - i][leftCann - j][1 - boatAt] = 1;
}
}
}
}
} else {
int rightMiss = numOfMiss - leftMiss;
int rightCann = numOfCann - leftCann;
for (i = 0; i <= rightMiss && i <= capacity; ++i) {
for (j = 0; j <= rightCann && i + j <= capacity; ++j) {
if (i + j != 0) {
if (checkValidEmpty(leftMiss + i, leftCann + j,
1 - boatAt)) {
queue.add(new Status(leftMiss + i,
leftCann + j, 1 - boatAt, front - 1));
tail++;
dp[leftMiss + i][leftCann + j][1 - boatAt] = 1;
}
}
}
}
}
}
if (!solution)
System.out.println("不存在解!");
queue.clear();
System.out.println("Time elapsed: "
+ (System.currentTimeMillis() - begin) + " minisecs.\n");
}
/** *//**
* 启发式搜索方案
*/
private void solveInAStar() {
System.out.println("现在使用启发式搜索方案");
Transport[][][] pre = new Transport[numOfMiss + 1][numOfCann + 1][2];
long begin = initiation();
Queue<Status> queue = new PriorityQueue<Status>();
queue.add(new Status(numOfMiss, numOfCann, 0, -1, 0 + calF(numOfMiss,
numOfCann, 0)));
pre[numOfMiss][numOfCann][0] = new Transport(-1, -1, -1);
dp[numOfMiss][numOfCann][0] = 0;
boolean solution = false;
while (!queue.isEmpty()) {
Status now = queue.remove();
int leftMiss = now.leftMiss;
int leftCann = now.leftCann;
int boatAt = now.boatAt;
// System.out.printf("%d %d %d %d\n", leftMiss, leftCann, boatAt,
// now.cost);
if (leftCann == 0 && leftMiss == 0) {
int idx = 0;
while (true) {
Transport t = pre[leftMiss][leftCann][boatAt];
if (t.a == -1)
break;
steps[idx++] = t;
if (t.boatAt == 0) {
leftMiss += t.a;
leftCann += t.b;
} else {
leftMiss -= t.a;
leftCann -= t.b;
}
boatAt = 1 - boatAt;
}
for (int i = 0, j = idx - 1; i < j; ++i, --j) {
Transport tmp = steps[i];
steps[i] = steps[j];
steps[j] = tmp;
}
OutputAnswer(idx);
solution = true;
break;
}
int i, j;
if (boatAt == 0) {
for (i = 0; i <= leftMiss && i <= capacity; ++i) {
for (j = 0; j <= leftCann && i + j <= capacity; ++j) {
if (i + j != 0) {
if (checkValidSmaller(leftMiss - i, leftCann - j,
1 - boatAt, now.cost + 1)) {
queue.add(new Status(leftMiss - i,
leftCann - j, 1 - boatAt, -1, now.cost
+ 1
+ calF(leftMiss - i, leftCann
- j, 1 - boatAt)));
dp[leftMiss - i][leftCann - j][1 - boatAt] = now.cost + 1;
pre[leftMiss - i][leftCann - j][1 - boatAt] = new Transport(
i, j, boatAt);
}
}
}
}
} else {
int rightMiss = numOfMiss - leftMiss;
int rightCann = numOfCann - leftCann;
for (i = 0; i <= rightMiss && i <= capacity; ++i) {
for (j = 0; j <= rightCann && i + j <= capacity; ++j) {
if (i + j != 0) {
if (checkValidSmaller(leftMiss + i, leftCann + j,
1 - boatAt, now.cost + 1)) {
queue.add(new Status(leftMiss + i,
leftCann + j, 1 - boatAt, -1, now.cost
+ 1
+ calF(leftMiss + i, leftCann
+ j, 1 - boatAt)));
dp[leftMiss + i][leftCann + j][1 - boatAt] = now.cost + 1;
pre[leftMiss + i][leftCann + j][1 - boatAt] = new Transport(
i, j, boatAt);
}
}
}
}
}
}
if (!solution)
System.out.println("不存在解!");
queue.clear();
System.out.println("Time elapsed: "
+ (System.currentTimeMillis() - begin) + " minisecs.\n");
}
private int calF(int numOfMiss, int numOfCann, int boatAt) {
return (numOfMiss + numOfCann + boatAt - 1) / (capacity - 1);
}
/** *//**
* 检查一个状态是否合法
*/
public boolean checkValid(int leftMiss, int leftCann, int boatAt) {
int rightMiss = numOfMiss - leftMiss;
int rightCann = numOfCann - leftCann;
if (leftMiss < leftCann && leftMiss != 0)
return false;
if (rightMiss < rightCann && rightMiss != 0)
return false;
return true;
}
/** *//**
* 检查一个状态是否合法并且不为空(-1)
*/
public boolean checkValidEmpty(int leftMiss, int leftCann, int boatAt) {
int rightMiss = numOfMiss - leftMiss;
int rightCann = numOfCann - leftCann;
if (leftMiss < leftCann && leftMiss != 0)
return false;
if (rightMiss < rightCann && rightMiss != 0)
return false;
return (dp[leftMiss][leftCann][boatAt] == -1);
}
/** *//**
* 检查一个状态是否合法并且小于一个状态值
*/
public boolean checkValidSmaller(int leftMiss, int leftCann, int boatAt,
int cost) {
int rightMiss = numOfMiss - leftMiss;
int rightCann = numOfCann - leftCann;
if (leftMiss < leftCann && leftMiss != 0)
return false;
if (rightMiss < rightCann && rightMiss != 0)
return false;
return (dp[leftMiss][leftCann][boatAt] == -1 || dp[leftMiss][leftCann][boatAt] > cost);
}
/** *//**
* 输出解
* @param depth
* 解的长度
*/
public void OutputAnswer(int depth) {
System.out.println("已经找到解!");
System.out.println("一共需要" + depth + "步:");
for (int i = 0; i < depth; ++i) {
System.out.println(steps[i].toString());
}
}
}