我需要 传教士和野人问题(clips程序） 详解

update((X,Y,0),Move,Statu1):- %船在左岸时

从策划到设计制作，每一步都追求做到细腻，制作可持续发展的企业网站。为客户提供成都网站建设、网站设计、网站策划、网页设计、国际域名空间、虚拟主机、网络营销、VI设计、 网站改版、漏洞修补等服务。为客户提供更好的一站式互联网解决方案,以客户的口碑塑造优易品牌,携手广大客户,共同发展进步。

(A,B)=X,

(C,D)=Y,

(E,F)=Move,

C1 is C+E,

D1 is D+F,

A1 is A-E,

B1 is B-F,

Statu1=((A1,B1),(C1,D1),1).

update((X,Y,1),Move,Statu1):- %船在右岸时

(A,B)=X,

(C,D)=Y,

(E,F)=Move,

C1 is C-E,

D1 is D-F,

A1 is A+E,

B1 is B+F,

Statu1=((A1,B1),(C1,D1),0).

?- update(((3,3),(0,0),0),(1,1),X).

X = (2,2),(1,1),1 ;

no

?- update(((0,0),(3,3),0),(1,1),X).

X = (-1,-1),(4,4),1 ;

no

?- update(((1,2),(2,3),1),(3,4),X).

X = (4,6),(-1,-1),0 ;

no

请参看参考资料，有点类似，语言不一样，但是万变不离其中，思想是一样的。

用java实现野人传教士过河问题

//CrossRiverQuestion.java

import java.util.ArrayList;

import java.util.List;

public class CrossRiverQuestion {

public static void main(String[] args) {

CrossRiverQuestion q = new CrossRiverQuestion(5, 4);

q.solveQuestion();

}

private int peoNum;

private int savageNum;

private ListNode resultList = new ArrayListNode();

public ListNode solveQuestion() {

Node n = new Node(peoNum,savageNum,0,0,0,new ArrayListInteger(),0,0);

boolean dfsResult = dfs(n);

if(dfsResult) {

resultList.add(0,n);

for(Node node : resultList) {

System.out.println("左岸传教士："+node.getLeftPeo()+"左岸野人： "+node.getLeftSavage()+" 右岸传教士： "+node.getRightPeo()+"右岸野人："+node.getRightSavage()+"船上传教士："+node.getOnBoatPeoNum()+"船上野人："+node.getOnBoatSavageNum());

}

return resultList;

}

return null;

}

public CrossRiverQuestion(int peoNum, int savageNum) {

super();

this.peoNum = peoNum;

this.savageNum = savageNum;

}

private boolean dfs(Node n) {

if(n.hasVisited()) return false;

n.addCheckSum();

if(n.getLeftPeo()==0n.getLeftSavage()==0) return true;

if(n.getLeftPeo()0||n.getRightPeo()0||n.getLeftSavage()0||n.getRightSavage()0) {

return false;

}

if(n.getLeftPeo()n.getLeftSavage()n.getLeftPeo()0) return false;

if(n.getRightPeo()n.getRightSavage()n.getRightPeo()0) return false;

if(n.getCURR_STATE()==n.getStateBoatLeft()) {

Node n1 = new Node(n.getLeftPeo()-1,n.getLeftSavage()-1,n.getRightPeo()+1,n.getRightSavage()+1,n.getStateBoatRight(),n.getNodesCheckSum(),1,1);

if(dfs(n1)) {

resultList.add(0,n1);

return true;

}

Node n4 = new Node(n.getLeftPeo()-2,n.getLeftSavage(),n.getRightPeo()+2,n.getRightSavage(),n.getStateBoatRight(),n.getNodesCheckSum(),2,0);

if(dfs(n4)) {

resultList.add(0,n4);

return true;

}

Node n5 = new Node(n.getLeftPeo(),n.getLeftSavage()-2,n.getRightPeo(),n.getRightSavage()+2,n.getStateBoatRight(),n.getNodesCheckSum(),0,2);

if(dfs(n5))  {

resultList.add(0,n5);

return true;

}

} 

else {

Node n6 = new Node(n.getLeftPeo(),n.getLeftSavage()+1,n.getRightPeo(),n.getRightSavage()-1,n.getStateBoatLeft(),n.getNodesCheckSum(),0,1);

if(dfs(n6)) {

resultList.add(0,n6);

return true;

}

Node n7 = new Node(n.getLeftPeo()+1,n.getLeftSavage(),n.getRightPeo()-1,n.getRightSavage(),n.getStateBoatLeft(),n.getNodesCheckSum(),1,0);

if(dfs(n7)) {

resultList.add(0,n7);

return true;

}

Node n1 = new Node(n.getLeftPeo()+1,n.getLeftSavage()+1,n.getRightPeo()-1,n.getRightSavage()-1,n.getStateBoatLeft(),n.getNodesCheckSum(),1,1);

if(dfs(n1)) {

resultList.add(0,n1);

return true;

}

Node n4 = new Node(n.getLeftPeo()+2,n.getLeftSavage(),n.getRightPeo()-2,n.getRightSavage(),n.getStateBoatLeft(),n.getNodesCheckSum(),2,0);

if(dfs(n4)) {

resultList.add(0,n4);

return true;

}

Node n5 = new Node(n.getLeftPeo(),n.getLeftSavage()+2,n.getRightPeo(),n.getRightSavage()-2,n.getStateBoatLeft(),n.getNodesCheckSum(),0,2);

if(dfs(n5))  {

resultList.add(0,n5);

return true;

}

}

return false;

}

public ListNode getResultList() {

return resultList;

}

}

Node.java

import java.util.ArrayList;

import java.util.List;

public class Node {

private ListInteger nodesCheckSum = new ArrayListInteger();

private int leftPeo;

private int rightPeo;

private int leftSavage;

private int rightSavage;

private int CURR_STATE = 0;

private int onBoatPeoNum = 0;

private int onBoatSavageNum = 0;

private final int STATE_BOAT_LEFT = 0;

private final int STATE_BOAT_RIGHT = 1;

public Node(int leftPeo, int leftSavage, int rightPeo, int rightSavage, int state, List checkSumList, int onBoatPeoNum, int onBoatSavageNum) {

this.CURR_STATE = state;

this.leftPeo = leftPeo;

this.leftSavage = leftSavage;

this.rightPeo = rightPeo;

this.rightSavage = rightSavage;

this.nodesCheckSum.addAll(checkSumList);

this.onBoatPeoNum = onBoatPeoNum;

this.onBoatSavageNum = onBoatSavageNum;

}

public int getLeftPeo() {

return leftPeo;

}

public void setLeftPeo(int leftPeo) {

this.leftPeo = leftPeo;

}

public int getRightPeo() {

return rightPeo;

}

public void setRightPeo(int rightPeo) {

this.rightPeo = rightPeo;

}

public int getLeftSavage() {

return leftSavage;

}

public void setLeftSavage(int leftSavage) {

this.leftSavage = leftSavage;

}

public int getRightSavage() {

return rightSavage;

}

public void setRightSavage(int rightSavage) {

this.rightSavage = rightSavage;

}

@Override

public String toString() {

return leftPeo+","+leftSavage+","+rightPeo+","+rightSavage+","+CURR_STATE;

}

public int getCURR_STATE() {

return CURR_STATE;

}

public void setCURR_STATE(int cURR_STATE) {

CURR_STATE = cURR_STATE;

}

public int getStateBoatLeft() {

return STATE_BOAT_LEFT;

}

public int getStateBoatRight() {

return STATE_BOAT_RIGHT;

}

public int calcCheckSum() {

return 1*getCURR_STATE()+10*getLeftPeo()+100*getLeftSavage()+1000*getRightPeo()+10000*getRightSavage();

}

public void addCheckSum() {

int checkSum = calcCheckSum();

nodesCheckSum.add(checkSum);

}

public boolean hasVisited() {

int sum = calcCheckSum();

for (Integer checkSum : nodesCheckSum) {

if(checkSum==sum) return true;

}

return false;

}

public ListInteger getNodesCheckSum() {

return nodesCheckSum;

}

public int getOnBoatPeoNum() {

return onBoatPeoNum;

}

public void setOnBoatPeoNum(int onBoatPeoNum) {

this.onBoatPeoNum = onBoatPeoNum;

}

public int getOnBoatSavageNum() {

return onBoatSavageNum;

}

public void setOnBoatSavageNum(int onBoatSavageNum) {

this.onBoatSavageNum = onBoatSavageNum;

}

}

人工智能用启发式搜索解决传教士-野人（M-C）问题！环境：matlab/Vc 要可运行程序 谢谢！

问题：

有3个传教士和3个野人要过河，只有一艘船，这艘船每次只能载2个人过河，且无论哪边野人的数量大于传教士的数量时，野人就会吃掉传教士。怎样让他们都安全过河？

C语言源代码：

#include stdio.h

#include string.h

#define STEP_MAX 20 //来回过河的次数

#define KIND_NUM 3 //每个种类的数量

#define BOAT_NUM 2 //船的载重量

typedef enum

{

BOAT_THIS,//船在本岸

BOAT_THAT,//船在对岸

} boat_t;

typedef enum

{

ROAD_GO,//过河

ROAD_COME,//回来

} road_t;

typedef struct

{

int ye;//对岸野人数量

int man;//对岸传教士数量

boat_t boat;//船是否在对岸

} state_t;//一种局面

typedef struct

{

int ye;//野人过河数量

int man;//传教士过河的数量

road_t road;//回来或过河

} step_t;//一个步骤

state_t states[STEP_MAX]={0};

step_t steps[STEP_MAX]={0};

//判断所有的野人和传教士是否都到了对岸

bool final(state_t s)

{

const state_t cs=

{

KIND_NUM,

KIND_NUM,

BOAT_THAT

};

if(memcmp(cs,s,sizeof(state_t))==0)

{

return true;

}

return false;

}

//是否会发生野人杀传教士

bool bad(state_t s)

{

if(((KIND_NUM-s.ye)(KIND_NUM-s.man) (KIND_NUM-s.man)0)

||(s.yes.man s.man0))

{

return true;

}

return false;

}

//第n种局面是否跟前面的相重复

bool repeat(state_t s[],int n)

{

int i;

for (i = 0; i n; i++)

{//已经有这种情况了

if (memcmp(states[i], states[n], sizeof(states[i])) == 0)

{

return true;

}

}

return false;

}

void output(step_t steps[STEP_MAX],int n)

{

char *kinds[KIND_NUM]={"野人","传教士"};

char *routine[2]={"过河.","回来."};

int i;

for (i = 0; i n; i++)

{

if((steps[i].ye * steps[i].man)0)

{

printf("%d个%s和%d个%s%s\n",steps[i].ye,kinds[0],

steps[i].man,kinds[1],routine[steps[i].road]);

}

else if(steps[i].ye0)

{

printf("%d个%s%s\n",steps[i].ye,kinds[0],

routine[steps[i].road]);

}

else if(steps[i].man0)

{

printf("%d个%s%s\n",steps[i].man,kinds[1],

routine[steps[i].road]);

}

}

printf("\n");

}

//搜索过河方案(n表示过河次数)

void search(int n)

{

int i,j;

if(nSTEP_MAX)

{//步数限制太少了

printf("Step Overflow!");

return;

}

if(final(states[n]))

{//都到对岸了

output(steps,n);

return;

}

if(bad(states[n]))

{//发生了野人杀传教士了

return;

}

if(repeat(states,n))

{//与前面的局面相重复了

return;

}

if(states[n].boat==BOAT_THIS)

{//船在本岸

for (i = 0; i = BOAT_NUM i=(KIND_NUM-states[n].ye); i++)

for (j = 0; j = BOAT_NUM-i j=(KIND_NUM-states[n].man); j++)

{

if(i==0 j==0)

{

continue;

}

steps[n].ye=i;

steps[n].man=j;

steps[n].road=ROAD_GO;

memcpy(states[n+1], states[n], sizeof(state_t));

states[n+1].ye+=i;

states[n+1].man+=j;

states[n+1].boat=BOAT_THAT;

search(n+1);

}

}

else

{

for (i = 0; i = BOAT_NUM i=states[n].ye; i++)

for (j = 0; j = BOAT_NUM-i j=states[n].man; j++)

{

if(i==0 j==0)

{

continue;

}

steps[n].ye=i;

steps[n].man=j;

steps[n].road=ROAD_COME;

memcpy(states[n+1], states[n], sizeof(state_t));

states[n+1].ye-=i;

states[n+1].man-=j;

states[n+1].boat=BOAT_THIS;

search(n+1);

}

}

}

int main()

{

search(0);

return 0;

}

人工智能野人传教士过河

;

三对三有解。

我用 Python 写了搜寻答案的程序。

要知道其它组合有没有解，只要改一改 “mCOUNT, cCOUNT = 3, 3” 这一行然后运行就知道了。

有空的话我会译成 Java 贴上来。

'''

Solve the Missionaries And Cannibals Puzzle by trying all legal moves.

The puzzle imposes two constraints:

1) Relative headcount: missionaries must be = cannibals at any point.

2) Boat capacity: max is two.

'''

def comb( items, r ):

'''Returns all combinations of elements in items taken r at a time.'''

if r == 0:

yield ( )   # Returns tuple to enable direct conversion to set.

else:

for i in xrange( len( items ) ):

for subComb in comb( items[ i + 1 : ], r - 1 ):

yield ( items[ i ], ) + subComb

# Simply represent the elements of the puzzle by characters.

MISSIONARY, CANNIBAL, BOAT = 'm', 'c', 'B'

mCOUNT, cCOUNT = 3, 3

# Constraint #2: boat capacity.

nMAXCROSSER = 2

nMINCROSSER = 1

class RiverSide:

'''Represents the state of a riverside.'''

def __init__( self, men = [ ], boat = [ ] ):

self.men = men

self.boat = boat

def __eq__( self, other ):

self.men.sort( ); other.men.sort( )

return self.men == other.men and self.boat == other.boat

def __repr__( self ):

return 'BOAT' + `self.boat`.ljust( 8 ) + 'MEN' + `self.men`

def _xferBoat( self, otherSide ):

'''To be called only by xferMen( ).'''

otherSide.boat.append( self.boat.pop( ) )

def xferMen( self, otherSide, menList ):

for man in menList:

otherSide.men.append( self.men.pop( self.men.index( man ) ) )

# Nice to automate boat xfer here.

self._xferBoat( otherSide )

# Constraint #1: relative headcount.

def fatal( self ):

'''Returns true iff the cannibals outnumbers missionaries.'''

mCount = self.men.count( MISSIONARY )

return mCount and mCount self.men.count( CANNIBAL )

class RiverScene:

'''Represents the state of a riverscene.'''

def __init__( self, sourceSide = RiverSide( ), targetSide = RiverSide( ) ):

self.source = sourceSide

self.target = targetSide

def __eq__( self, other ):

return self.source == other.source and self.target == other.target

def __repr__( self ):

return `self.source` + '\n' + `self.target`

def fatal( self ):

return self.source.fatal( ) or self.target.fatal( )

def solve( firstScene, finalScene ):

'''Returns a list of solution steps if solution's found; else returns None.'''

def solutionSteps( takenSteps ):

'''

The solution searching recursive workhorse function.

Takes a list containing the first scene and returns a list of

solution steps leading to the final scene if solution was found.

Optimizations done:

1) elimination of equivalent combinations of men to be moved

2) maximization of headcount to move from source

(minimization for the reverse direction)

'''

lastStep = takenSteps[ - 1 ]

if lastStep == finalScene: return takenSteps

from copy import deepcopy

newStep = deepcopy( lastStep )

# To enable moving of both direction to share the same chunk of code.

start, stop, step = nMAXCROSSER, nMINCROSSER - 1, -1

src, dst = newStep.source, newStep.target

if dst.boat:

start, stop, step = nMINCROSSER, nMAXCROSSER + 1, 1

src, dst = dst, src

for nCrosser in range( start, stop, step ):

for men in set( comb( src.men, nCrosser ) ):

src.xferMen( dst, men )

if not newStep.fatal( ) and newStep not in takenSteps:

takenSteps.append( newStep )

sol = solutionSteps( takenSteps )

if sol:

return sol

else:

takenSteps.pop( )

# Rewind before trying next move.

dst.xferMen( src, men )

takenSteps = [ firstScene ]

return solutionSteps( takenSteps )

# Setup.

men =  [ MISSIONARY ] * mCOUNT + [ CANNIBAL ] * cCOUNT

boat = [ BOAT ]

source = RiverSide( men, boat )

target = RiverSide( )

firstScene = RiverScene( source, target )

finalScene = RiverScene( target, source )

print '\nTrying to solve puzzle of', mCOUNT, 'missionaries and', cCOUNT, 'cannibals...\n'

solutionSteps = solve( firstScene, finalScene )

if solutionSteps:

print 'Solution found:\n\n'

for step in solutionSteps:

print step, '\n'

else:

print 'No solution found.'

c语言:我编的传教士与野人过河程序

程序过程是没问题的,只是在函数内声明的局部变量与全局变量同名,造成在函数内全局变量不起作用,

在函数

int

boatf(int

im,int

ic,int

ii)

中,由于形参局部变量与全局变量同名,实际在该函数中起作用的只是局部变量,再加上函数里没有把局部变量运算后的值赋给全局变量,所以函数运行结束后,全局变量的值与函数运行前的值一样.在整个程序运行过程中,main

函数中的im

,ic的值始终都是3,结果就是一种死循环状态.

答案补充

不过我不清楚你设计从

"右岸到左岸用boatr"

的函数作用是什么.

野人与传教士过河问题 求出所有能确保全部安全的过河的计划并给出正确Visual Prolog程序麻烦有知道的回答

先一传一野过河，然后传再返回载一野过来，然后由野返回载一传过来，再由野载一传来，最后再由野去载最后的一个野人，就OK.啦