20CN网络安全小组论坛 - 编程破解 - 求解渡河问题，最好有源代码，谢谢大家！

论坛: 编程破解标题: 求解渡河问题，最好有源代码，谢谢大家！

作者: none [onizuka]

论坛用户

假如有n个正常人和n个精神病患者准备渡河，但是只有一条能容纳c人的小船，为了防止精神病患者侵犯正常人，要求无论在何处，正常人的人数不得少于精神病患者人数，除非正常人数为0，且假定两种人都会划船，试设计一个算法，确定它们能否渡过河去，如果可以，则给出一只小船来回次数最少的最佳方案!

[此贴被 none(onizuka) 在 09月27日21时17分编辑过]

地主发表时间: 04-09-25 17:59

回复: sniper167 [sniper167]

论坛用户

要分四种情况：
1。n和c都为偶：每次过去的正常和非正常人为c/2个，然后回来一个正常和不正常，直至送完
2。n和c都为奇：
3。n为偶，c为奇：
4。n为奇，n为偶：

其他的我就不写了。。。

B1层发表时间: 04-09-28 16:23

回复: kert_t8 [kert_t8]

论坛用户

Let me have a try:)

First, we should have a data structure so that we could store the actions and states.
let's suppose they are from A by Boat to C. So....
DEF. int A[2],B[2],C[2],w
number of common people is 1*n, stored in x[0]
number of silly is -1*n, in x[1]
w=1 means Boat is at A, w=2 means Boat is at C

So, we have constraints:
1,x[0]+x[1]>=0 UNLESS x[0]=0
2,abs(B[0])+abs(B[1])<c
3,x[0]>=0 && x[1]<=0

Initial state:
A[0]=n
A[1]=-n
B[0]=B[1]=C[0]=C[1]=0

Goal state:
C[0]=n
C[1]=-n
B[0]=B[1]=A[0]=A[1]=0

Action:
1. Precondition: w=1
A[0]->B[0], A[1]->B[1];B[0]->C[0], B[1]->C[1];w=0 (Constraints..1234)
2. Precondition: w=2
C[0]->B[0], C[1]->B[1];B[0]->A[0], B[1]->A[1];w=0 (Constraints..1234)

(NOTE: Action 1,2 in fact contains a lot of possible actions, we just split them into two main sets A1, A2)

Algorithm:
(In Thinking...)
Basical ideas as below:

list<-{A,B,C(state)};
while (list!=empty){ //not necessarily being null
s<-Head(list);
list<-Rest(list);
if (s is goal)
return;
else
while (Action!=empty ){ //Action is a set in which there are all the actions could apply on this state
act<-Head(Action);
Action<-Rest(Action);
newstate<-apply(act);
list<-prepend(newstate, list);
}
}
return SORRY

It's Depth-First algorithm, which could find the answer quickly if there is one, but may go on and on if there is no answer or there is a circle in state graph:)
Better algortihms are not understood yet, but I'm trying.

///////////////////////////////////////////////////////////////////////////////
Any mistake please be put up once you find............(Kan tie yao hui tie

)

(more contents should be put up in several days)
To be continued................

[此贴被月之御者(kert_t8) 在 10月03日03时40分编辑过]

B2层发表时间: 04-10-01 13:34

回复: balsai [balsai]

论坛用户

大家用C嘛

B3层发表时间: 04-10-01 14:04

回复: none [onizuka]

论坛用户

大家加油啊！Help me!

B4层发表时间: 04-10-02 16:05

回复: kert_t8 [kert_t8]

论坛用户

OK, let's go on with what we talked about.....

As we have already said, the biggest problem of the algorithm above is, we are not sure if he can find an answer. And all the problems because of the sentence ' list=prepend(newstate, list)'. we could see, if we always put a serial of new states at the head of the list, and pick the first one to choose what next action will be. So, if we change that into 'list=APPend(newstate, list)', OK, problem sloved.(This is the Breadth-First search)

The difference between the two algorithms is the first one is continue trying the First Action of NEXT step after he tried the first action of This step, but the latter one is try every possible actions in This step, and then, every actions in NEXT. It is important to make clear understanding on the difference, because we'll see later, this difference is a way which we could speed up our algorithm.

But, we find the new algorithm's running time is O(m^n)(where m is the number of choices and n is the number of actions which should be exectued). And if we conbine the two algorithm together, we'll found, the running time is still O(m^n). OK, let's first see the new algorithm...........
(We'll also do some more speed up, no revisiting states)

list<-{A,B,C(state)};
while (list!=empty){ //not necessarily being null
DO
s<-Head(list);
if (s==SpecialState)
State<-Pop(State);
Until (s!=SpecialState) //SpecialState is not a real state, but a mark to pop a state in State.
list<-Rest(list);
State<-s; //we save this state into a state list
if (s is goal)
return State;
else if (State.length<= BOUND){ //BOUND is a value we set to determin we must solve the problem in how many steps. That is also, how many levels we could search.
list<-prepend(SpecialState,list); // make a note that search in a new level begin
while (Action!=empty ){ //Action is a set in which there are all the actions could apply on this state
act<-Head(Action);
Action<-Rest(Action);
newstate<-apply(act);
if (newstate NOT IN State)
list<-prepend(newstate, list);
}
}
else //If when we reach the max steps we have setted, and there is still no solution
State<-Pop(State); //Last action we exectued is wrong, no more considering about that, and back to the last state, try next action.
}
return SORRY

OK, later, we'll try to give a program in Java to solve this problem...........

Note: This is still not the best algorithm, I'm still trying to learn...

///////////////////////////////////////////////////////////////////////////////
Any mistake please be put up once you find............(Kan tie yao hui tie

)

(more contents should be put up in several days)
To be continued................

B5层发表时间: 04-10-03 03:37

回复: kert_t8 [kert_t8]

论坛用户

Sorry about some notation bugs in the first composition. That's because I was still not used to write pseudo-code. But in the following algorithm, I'll try my best to write correct code.

Thank myself for first find these problems. And I'm sorry

I hope I could put on my first program on this problem ASAP. But I have to take class for futher learning and it take time to write the program. So, be patient

B6层发表时间: 04-10-03 03:53

回复: kert_t8 [kert_t8]

论坛用户

反复尝试了很久，但是就是做不出源程序来，然后我才发现，原来我对算法本身的理解就有问题。

我们最后讨论的那个算法实际上是不完整的。大家可以看到，程序的bound，也就是搜索的层数是不变的，那么也就决定了，如果渡河的步奏不可以在bound步内完成，那么程序就会认为这个问题误解，从而返回错误的答案。而如果程序在bound以内执行完的话，就跟backtrack搜索没有什么区别，也无从找到最短路经

for (int BOUND=1;;BOUND++){
list<-{A,B,C(state)};
while (list!=empty){ //not necessarily being null
DO
s<-Head(list);
if (s==SpecialState)
State<-Pop(State);
Until (s!=SpecialState) //SpecialState is not a real state, but a mark to pop a state in State.
list<-Rest(list);
State<-s; //we save this state into a state list
if (s is goal)
return State;
else if (State.length<= BOUND){ //BOUND is a value we set to determin we must solve the problem in how many steps. That is also, how many levels we could search.
list<-prepend(SpecialState,list); // make a note that search in a new level begin
while (Action!=empty ){ //Action is a set in which there are all the actions could apply on this state
act<-Head(Action);
Action<-Rest(Action);
newstate<-apply(act);
if (newstate NOT IN State)
list<-prepend(newstate, list);
}
}
else //If when we reach the max steps we have setted, and there is still no solution
State<-Pop(State); //Last action we exectued is wrong, no more considering about that, and back to the last state, try next action.
}
return SORRY
}

这样，程序多了一个大循环，使得程序搜索的层数在不断的变化，每一次都会向下多搜索1层，这样的话一旦找到一个解，那么我们可以确定这个解是最小解，因为比它小的所有可能都不是正确解。

当然，我现在对于这种搜索问题还有很多困扰，我仍然感觉对这个算法的精神没有完全掌握。老师说话太快了，根本没有给我反应的时间。所有的感觉都是在自学与完成作业的过程中找到的，包括我上面发现的算法错误，都是昨天在写作业的时候发现的。如果有人了解这个算法请帮我解释一边，我也学习学习

声明：由于在学《人工智能》，其中有很多算法都是和这种求解问题相关的，比如我们的作业就有华容道问题，还有命题逻辑的推理（我是指用程序解决）。还有魔方问题。都是求解的。我之所以选择这个问题发帖子是因为我想通过这样的方式可以
1。我可以复习老师所讲过的内容，并通过实际的编程让我有更多解决这种问题的经验（这样写作业可以快一点）
2。我也想把这些算法介绍给大家，因为我发现在国内我们很少系统地接受这种算法的介绍（至少我是如此），大部分的算法实在将数据结构的时候老师顺带讲的，而很多时候我们没有领会老师所讲的东西的实质。

很抱歉没有能够把源程序贴出来，但是我已经很努力的在做这件事了。希望下一次能够吧
对不起大家

B7层发表时间: 04-10-15 02:03

回复: gg [gg123]

论坛用户

外国佬你滚蛋！
还说学中国文化扬中华之雄威呢~~~~？？

B8层发表时间: 04-12-02 14:44

回复: hannyu [hannyu]

论坛用户

继续

P。S。楼上的该补补英语了

B9层发表时间: 04-12-02 19:44

回复: kert_t8 [kert_t8]

论坛用户

早就该贴出来了，但是前一段时间一直都上不来，结果这么长时间，把原文件也弄丢了。没办法，重新写了一个。（为了写这个程序，我还找TA把以前的作业要回来，因为包括作业在内的所有程序都弄丢了）

因为是新写的，在设计方面，我是指数据结构，有所不同，以前设计的正负数的结构并不好用，并且表示船所在位置的时候也不舒服，所以我做了一个State类，Aside表示在A岸的人数，Cside就是C岸。所有的数组，[0]表示正常人的个数，[1]是神经病的个数，都使用正数表示。Boat表示船在那一边，如果是-1就是C,1就是A.

//////// file: river.java

import java.util.*;

public class river {

public static void main(String args[]) {
int nInput;
int cInput;
do {
System.out.print("\n\nWe assume all the people are on the A side.\nLet's input the number n first:");
nInput = getter.getInt(System.in);
} while (nInput<1);
do {
System.out.print("\nAnd you must decide the max load of the boat:");
cInput = getter.getInt(System.in);
if (cInput<2)
System.out.println("Do you think such a small boat could fulfill our task, man?");
} while (cInput<2);
System.out.println();

int A[]=new int[2];
int C[]=new int[2];
A[0]=nInput;
A[1]=nInput;
C[0]=0;
C[1]=0;

State initState = new State(A,C,1,cInput);
State goalState = new State(C,A,-1,cInput);
BLoop: for (int Bound=1;;Bound++) {
System.out.println("Bound = "+Bound);
Vector stateList = new Vector();
Vector Solution = new Vector();
stateList.add(initState);
WLoop: while (stateList.size()>0) {
State nowState = new State();
do {
if (stateList.size()==0)
continue BLoop;
nowState = (State)(stateList.remove(stateList.size()-1));
if (nowState==null)
Solution.remove(Solution.size()-1);
} while (nowState==null);

if (nowState.stateEqual(goalState)) {
giveSolution(Solution);
}
else if(Solution.size()>=Bound) {
continue WLoop;
}
else {
Solution.add(nowState);
stateList.add(null);
for (int i=0;i<cInput;i++)
for (int j=0;j<cInput;j++) {
int B[]=new int[2];
B[0]=i;
B[1]=j;
State newState = null;
newState = nowState.nextState(B);
boolean flag=true;
if (newState!=null){
if(stateList.size()!=0)
for (int listIndex=0;listIndex<stateList.size();listIndex++) {
if (newState.stateEqual(((State)stateList.get(listIndex)))){
flag=false;
break;
}
}
if(stateList.size()!=0)
for (int listIndex=0;listIndex<Solution.size();listIndex++) {
if (newState.stateEqual((State)Solution.get(listIndex))) {
flag=false;
break;
}
}
}
else
flag=false;
if (flag==true){
stateList.add(newState);
}

}
}
}
}
}

public static void giveSolution(Vector Solution) {
System.out.println("OK, we've got the answer---------------------------------------------------");
for (int i=0;i<Solution.size();i++)
((State)Solution.get(i)).printState();
System.exit(0);
}

}
��

////// file: getter.java
import java.io.*;

class getter {

public static void main(String[] args) {

}

public static String getString(InputStream in){
String retString;
try{
InputStreamReader streamRead = new InputStreamReader(in);
BufferedReader stringReader= new BufferedReader(streamRead);
retString = stringReader.readLine();
}
catch(IOException e){
System.out.println("String error");
retString="ERROR";
}
return retString;
}

public static int getInt(InputStream in){
int retInt;
Integer holdInt;
try{
String intStr = getter.getString(in);
holdInt = Integer.valueOf(intStr);
retInt = holdInt.intValue();
}
catch(NumberFormatException e){
System.out.println("WARNING:not valid integer");
retInt = 0;
}
return retInt;
}
}
�

// file: State.java

public class State {
public int Aside[] = new int[2];
public int Cside[] = new int[2]; // [0] is number of normal people, [1] is number of sick people, both are positive
public int Boat; // 1 if boat is on A side, and -1 if boat is on C side;
private int numConstraint;

public State(int[] A, int[] C, int B, int Constraint) {
for(int i=0;i<A.length;i++) {
this.Aside[i]=A[i];
}
for(int i=0;i<C.length;i++) {
this.Cside[i]=C[i];
}
this.Boat=B;
this.numConstraint=Constraint;
}

public State() {

}

public State nextState(int inBoat[]) {
// check constraint
State nexSt = new State(this.Aside, this.Cside, this.Boat, this.numConstraint);
if (!actionValid(inBoat)) {
return null;
}
else
nexSt.applyAction(inBoat);
if (nexSt.stateValid()) {
return nexSt;
}
else {
return null;
}
}

public void applyAction(int inBoat[]) {
// always be A to C, and the number of people should be Boat*inBoat[];
for(int i=0;i<2;i++) {
Aside[i]=Aside[i]-Boat*inBoat[i];
Cside[i]=Cside[i]+Boat*inBoat[i];
}
Boat=Boat*(-1);
}

public boolean stateValid() {
int a=Aside[0]-Aside[1];
int c=Cside[0]-Cside[1];
if (a<0 || c<0)
return false;
if (Aside[0]<0 || Aside[1]<0 || Cside[0]<0 || Cside[1]<0)
return false;
return true;
}

private boolean actionValid(int inBoat[]) {
if (inBoat[0]<0 || inBoat[1]<0)
return false;
if (inBoat[0]-inBoat[1]<0)
return false;
if (inBoat[0]+inBoat[1]>numConstraint)
return false;
if (inBoat[0]+inBoat[1]<=0)
return false;
return true;
}

public void printState() {
System.out.println();
System.out.println("Normal\tSilly\t\tNormal\tSilly");
System.out.println(Aside[0]+"\t"+Aside[1]+"\t\t"+Cside[0]+"\t"+Cside[1]);
System.out.println("Boat State: "+Boat);
}

public boolean stateEqual(State compState) {
if (compState==null)
return false;
for (int i=0;i<2;i++) {
if (this.Aside[i]!=compState.Aside[i])
return false;
if (this.Cside[i]!=compState.Cside[i])
return false;
}
if (this.Boat!=compState.Boat)
return false;
return true;
}
}

本来想打包然后上传上来，无奈这里最近好象有些功能不能用，如果懒到粘贴复制一边都不想的话，就请你在下面跟贴，附上你的油箱地址，我给你寄过去好了

上面的贴，英文的，我会抽时间把他翻译过来，但是不是现在，因为现在要期末考试了，我还想多点时间复习。我知道用英文的不好，但是当时我也是没有办法。有想不通的还可以继续骂我

稍后我会把我们的一道作业题贴上来，是关于类似华容道问题的。有兴趣地可以做一做，我恰好这次作业的了满分，所以有什么问题可以跟我的作业比较，虽然编得也不好但是总算是有一个可以参照的嘛

类似的搜索问题，是所有棋类游戏人工智能的基础，我们班有好几个project都是以它为基础，做出很好的游戏来的，希望有更多人弄清楚它

在源程序里面，为了简化键盘输入，我使用了我们数据库project小组的源代码，getter.java内的所有代码不是我写的，原作者是harry，没有经得同意就擅自使用，希望Harry不要生气。

就到这里，上课去了....

B10层发表时间: 04-12-07 03:03

论坛: 编程破解