用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 List<Node> resultList = new ArrayList<Node>();
public List<Node> solveQuestion() {
Node n = new Node(peoNum,savageNum,0,0,0,new ArrayList<Integer>(),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()==0&&n.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 List<Node> getResultList() {
return resultList;
}
}
Node.java
import java.util.ArrayList;
import java.util.List;
public class Node {
private List<Integer> nodesCheckSum = new ArrayList<Integer>();
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 List<Integer> 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;
}
}
解题时可以把渡河的过程省略掉，也就是可以忽略河的存在。
为了用 Java 解这道题，我写了 3 个类：
河边（RiverSide）、河景（RiverScene）和解题者（MACPS，即 Missionaries And Cannibals Puzzle Solver）。
问题中的传教士、野人和船都是非常简单的物件，所以就简单地用单字符字符串“m”、“c” 和 “v”来代表。
其实那三个类都很简单；它们之间的关系也很简单：
1）每个河边都能有 0 或更多的 m 和 c，及最多 1 个 v。
2）每个河景里有两个河边。
3）解题者里有两个河景：初始河景和终极河景。
解题者的任务就是要搜索出能把初始河景及终极河景连起来的河景系列。
解题者的 getSolutionSteps（ ）以递归的方式作深度优先搜索。
其它两个“类”（Combinatorics 和 Copy）都是只提供一个方法的简单类。
代码里有文档。 有不明白的地方可以问。
你可以用类似 Jacobe （http://www.tiobe.com/jacobe.htm）的程序恢复代码原有的缩进。
import java.util.*;
import java.io.*;
/**
* Missionaries And Cannibals Puzzle Solver.
*
* Solution to the puzzle must not violate any of the following 2 rules:
* 1) Relative headcount: cannibals can't outnumber missionaries at any point.
* 2) Boat's loading: mustn't exceed the max.
*/
public class MACPS {
public class SolutionNotFoundException extends RuntimeException { }
static final Object MISSIONARY = "m", // Simple representation
CANNIBAL = "c", // of objects
BOAT = "v"; // in the puzzle.
private int boat_max_load,
boat_min_load = 1; // Shouldn't be any other value.
private RiverScene firstScene,
finalScene;
// Recursively searches for a solution using Depth-First Search strategy.
// Takes a Stack containing only the first scene (root of tree).
// Returns a collection of scenes connecting the first scene to the final.
// Throws SolutionNotFoundException for obvious reason.
// Deploys the following optimization strategy:
// Transfers as much as possible from source side,
// as little as possible from target side.
private Collection getSolutionSteps( Stack takenSteps ) {
RiverScene lastScene = ( RiverScene ) takenSteps.peek( );
if( lastScene.equals( finalScene ) ) return takenSteps;
RiverScene newStep = lastScene.deepCopy( );
// To allow transfer in both directions to share the same chunk of code.
int start = boat_max_load,
stop = boat_min_load - 1,
step = -1;
RiverSide from = newStep.lside,
to = newStep.rside;
if( to.hasBoat( ) ) {
start = boat_min_load;
stop = boat_max_load + 1;
step = 1;
from = newStep.rside;
to = newStep.lside;
}
for( int nPassenger = start; nPassenger != stop; nPassenger += step ) {
Collection menCombs = new HashSet( // HashSet eliminates duplicates.
Combinatorics.combinations( from.getMenList( ), nPassenger ) );
nextComb:
for( Iterator comb = menCombs.iterator( ); comb.hasNext( ); ) {
Collection menList = ( Collection ) comb.next( );
try {
from.transferMen( to, menList );
// If it's a taken step, undo and try next combination.
for( Iterator i = takenSteps.iterator( ); i.hasNext( ); )
if( i.next( ).equals( newStep ) ) {
to.transferMen( from, menList );
continue nextComb;
}
takenSteps.push( newStep );
return getSolutionSteps( takenSteps );
}
catch( SecurityException e ) {
// Transfer didn't take place. Just try next combination.
}
catch( SolutionNotFoundException e ) {
// New step led to no solution in leaves. Undo, then next.
takenSteps.pop( );
to.transferMen( from, menList );
}
}
}
// All possible steps led to no solution, so
throw new SolutionNotFoundException( );
}
// Do setup, then kick-starts getSolutionSteps( Stack takenSteps ).
public Collection
getSolutionSteps( int nMissionary, int nCannibal, int boatCapacity ) {
if( nMissionary < 0 || nCannibal < 0 || boatCapacity < 0 )
throw new IllegalArgumentException( "Negative argument value." );
RiverSide sourceSide = new RiverSide( nMissionary, nCannibal, true ),
targetSide = new RiverSide( 0, 0, false );
boat_max_load = boatCapacity;
firstScene = new RiverScene( sourceSide, targetSide );
finalScene = new RiverScene( targetSide, sourceSide );
if( firstScene.lside.fatal( ) ) // First scene can be valid but fatal.
throw new SolutionNotFoundException( );
Stack steps = new Stack( );
steps.push( firstScene );
return getSolutionSteps( steps );
}
public static void main( String[ ] args ) {
int nMissionary = 3,
nCannibal = 3,
boatCapacity = 2;
System.out.println(
"\nSolving the puzzle of Missionaries And Cannibals with\n" +
nMissionary + " missionaries and " + nCannibal + " cannibals " +
"and a boat that can take up to " + boatCapacity + " creatures.." );
try {
Collection steps = new MACPS( ).
getSolutionSteps( nMissionary, nCannibal, boatCapacity );
System.out.println( "\nSolution found:\n" );
for( Iterator step = steps.iterator( ); step.hasNext( ); )
System.out.println( step.next( ) + "\n" );
}
catch( SolutionNotFoundException e ) {
System.out.println( "\nNo solution found." );
}
}
}
/**
* Represents a riverside in the puzzle.
*/
class RiverSide implements Serializable {
private ArrayList men = new ArrayList( ),
boat = new ArrayList( );
public RiverSide( int nMissionary, int nCannibal, boolean withBoat ) {
men.addAll( Collections.nCopies( nMissionary, MACPS.MISSIONARY ) );
men.addAll( Collections.nCopies( nCannibal, MACPS.CANNIBAL ) );
Collections.sort( men );
if( withBoat ) boat.add( MACPS.BOAT );
}
public RiverSide deepCopy( ) {
return ( RiverSide ) Copy.deepCopy( this );
}
public Collection getMenList( ) {
return ( Collection ) Copy.deepCopy( men );
}
public boolean equals( Object otherSide ) {
RiverSide other = ( RiverSide ) otherSide;
Collections.sort( men );
Collections.sort( other.men );
return this.men.equals( other.men ) && this.boat.equals( other.boat );
}
public String toString( ) {
return "BOAT" + boat + "\t" + "MEN" + men;
}
public boolean hasBoat( ) {
return ! boat.isEmpty( );
}
// Checks for violation of Rule #1.
public boolean fatal( ) {
int mCount = 0, cCount = 0;
for( Iterator i = men.iterator( ); i.hasNext( ); ) {
Object val = i.next( );
if( val.equals( MACPS.MISSIONARY ) ) ++mCount;
if( val.equals( MACPS.CANNIBAL ) ) ++cCount;
}
return mCount > 0 && mCount < cCount;
}
// Throws SecurityException if the transfer of all men in menList
// from this to destination *will* result in violation of Rule #1.
// Else, executes the transfer.
public void transferMen( RiverSide destination, Collection menList ) {
for( Iterator i = menList.iterator( ); i.hasNext( ); )
destination.men.add( men.remove( men.indexOf( i.next( ) ) ) );
// A nice place to automate boat transfer.
_transferBoat( destination );
// Undo the transfer if it led to violation of Rule #1.
if( fatal( ) || destination.fatal( ) ) {
destination.transferMen( this, menList );
throw new SecurityException( );
}
}
// Tansfers boat from this to destination. Called only by transferMen( ).
private void _transferBoat( RiverSide destination ) {
destination.boat.add( boat.remove( 0 ) );
}
}
/**
* Combines two riversides. Serves mainly as a data object.
*/
class RiverScene implements Serializable {
RiverSide lside, rside; // Package access.
public RiverScene( RiverSide lside, RiverSide rside ) {
this.lside = lside.deepCopy( );
this.rside = rside.deepCopy( );
}
public RiverScene deepCopy( ) {
return ( RiverScene ) Copy.deepCopy( this );
}
public boolean equals( Object otherScene ) {
RiverScene other = ( RiverScene ) otherScene;
return lside.equals( other.lside ) && rside.equals( other.rside );
}
public String toString( ) {
return "Left Side:\t" + lside + "\n" + "Right Side:\t" + rside;
}
}
/**
* Provides a static method to generate combinations of items taken r at a time.
*/
class Combinatorics {
public static Collection combinations( Collection items, int r ) {
if( r == 0 ) // Return [ [ ] ]. Note that [ ] denotes a List.
return Collections.nCopies( 1, new ArrayList( ) );
List copy = new ArrayList( items ), // To enable subListing of items.
result = new ArrayList( );
for( int i = 0; i < copy.size( ); ++i ) {
Collection subCombs =
combinations( copy.subList( i + 1, copy.size( ) ), r - 1 );
for( Iterator iter = subCombs.iterator( ); iter.hasNext( ); ) {
// Assign [ [ items.get( i ) ] ] to subComb.
List subComb = new ArrayList( copy.subList( i, i + 1 ) );
subComb.addAll( ( List ) iter.next( ) );
result.add( subComb );
}
}
return result;
}
}
/**
* Provides a static method to perform deepcopy of object via serialization.
*/
class Copy {
public static Object deepCopy( Object o ) {
try {
ByteArrayOutputStream baos = new ByteArrayOutputStream( );
ObjectOutputStream oos = new ObjectOutputStream( baos );
oos.writeObject( o );
oos.close( );
ObjectInputStream ois =
new ObjectInputStream(
new ByteArrayInputStream( baos.toByteArray( ) ) );
return ois.readObject( );
}
catch ( Exception e ) {
throw new RuntimeException( e );
}
}
}
野人过河问题算法分析
野人过河问题属于人工智能学科中的一个经典问题，问题描述如下： 有三个牧师（也有的翻译为传教士）和三个野人过河，只有一条能装下两个人的船，在河的任何一方或者船上，如果野人的人数大于牧师的人数，那么牧师就会有危险. 你能不能找出一种安全的渡河方法呢？
一、算法分析
先来看看问题的初始状态和目标状态，假设和分为甲岸和乙岸：
初始状态：甲岸，3野人，3牧师；
乙岸，0野人，0牧师；
船停在甲岸，船上有0个人；
目标状态：甲岸，0野人，0牧师；
乙岸，3野人，3牧师；
船停在乙岸，船上有0个人；
整个问题就抽象成了怎样从初始状态经中间的一系列状态达到目标状态。问题状态的改变是通过划船渡河来引发的，所以合理的渡河操作就成了通常所说的算符，根据题目要求，可以得出以下5个算符（按照渡船方向的不同，也可以理解为10个算符）：
渡1野人、渡1牧师、渡1野人1牧师、渡2野人、渡2牧师
算符知道以后，剩下的核心问题就是搜索方法了，本文采用深度优先搜索，通过一个findnext(…)函数找出下一步可以进行的渡河操作中的最优操作，如果没有找到则返回其父节点，看看是否有其它兄弟节点可以扩展，然后用process(…)函数递规调用findnext(…)，一级一级的向后扩展。
搜索中采用的一些规则如下：
1、渡船优先规则：甲岸一次运走的人越多越好（即甲岸运多人优先），同时野人优先运走；
乙岸一次运走的人越少越好（即乙岸运少人优先），同时牧师优先运走；
2、不能重复上次渡船操作（通过链表中前一操作比较），避免进入死循环;
3、任何时候河两边的野人和牧师数均分别大于等于0且小于等于3；
4、由于只是找出最优解，所以当找到某一算符（当前最优先的）满足操作条件后，不再搜索其兄弟节点，而是直接载入链表。
5、若扩展某节点a的时候，没有找到合适的子节点，则从链表中返回节点a的父节点b，从上次已经选择了的算符之后的算符中找最优先的算符继续扩展b。
二、基本数据结构
仔细阅读问题，可以发现有些基本东西我们必须把握，例如：每时刻河两岸野人牧师各自的数目、船的状态、整个问题状态。所以我们定义如下几个数据结构：
typedef struct _riverside // 岸边状态类型
{
int wildman; // 野人数
int churchman; // 牧师数
}riverside;
typedef struct _boat // 船的状态类型
{
int wildman; // 野人数
int churchman; // 牧师数
}boat;
typedef struct _question // 整个问题状态
{
riverside riverside1; // 甲岸
riverside riverside2; // 乙岸
int side; // 船的位置, 甲岸为-1, 乙岸为1
boat boat; // 船的状态
_question* pprev; // 指向前一渡船操作
_question* pnext; // 指向后一渡船操作
}question;
用question来声明一个最基本的链表。
三、程序流程及具体设计
本文只找出了最优解，据我所知，本问题有三种解。如果真要找出这三种解，^_^，那就得加强对链表的操作了，比如说自己写一个动态链表类，顺便完成一些初始化工作，估计看起来会舒服些。
下面给出部分关键程序：
// 主函数
int main()
{
// 初始化
question* phead = new question;
phead->riverside1.wildman = 3;
phead->riverside1.churchman = 3;
phead->riverside2.wildman = 0;
phead->riverside2.churchman = 0;
phead->side = -1; // 船在甲岸
phead->pprev = null;
phead->pnext = null;
phead->boat.wildman = 0;
phead->boat.churchman = 0;
if (process(phead))
{
// ......... 遍历链表输出结果
}
cout<<"成功渡河。";
}
else
cout<<"到底怎样才能渡河呢? 郁闷!"<<endl;
// 回收内存空间
while (phead)
{
question* ptemp = phead->pnext;
delete phead;
phead=ptemp;
}
phead = null;
return 0;
}
// 渡船过程, 递规调用函数findnext(...)
bool process(question* pquest)
{
if (findnext(pquest))
{
question* pnew = new question;
pnew->riverside1.wildman = pquest->riverside1.wildman + pquest->boat.wildman*(pquest->side);
pnew->riverside1.churchman = pquest->riverside1.churchman + pquest->boat.churchman*(pquest->side);
pnew->riverside2.wildman = 3 - pnew->riverside1.wildman;
pnew->riverside2.churchman = 3 - pnew->riverside1.churchman;
pnew->side = (-1)*pquest->side;
pnew->pprev = pquest;
pnew->pnext = null;
pnew->boat.wildman = 0;
pnew->boat.churchman = 0;
pquest->pnext = pnew;
if (pnew->riverside2.wildman==3 && pnew->riverside2.churchman==3)
return true; // 完成
return process(pnew);
}
else
{
question* pprev = pquest->pprev;
if (pprev == null)
return false; // 无解
delete pquest;
pprev->pnext = null;
return process(pprev); // 返回其父节点重新再找
}
return true;
}
// 判断有否下一个渡河操作, 即根据比较算符找出可以接近目标节点的操作
// 算符共5个: 1野/ 1牧 / 1野1牧 / 2野 / 2牧
bool findnext(question* pquest)
{
// 基本规则
// 渡船的优先顺序: 甲岸运多人优先, 野人优先; 乙岸运少人优先, 牧师优先.
static boat boatstate[5]; // 5个算符
if (pquest->side == -1)
{
boatstate[0].wildman = 2;
boatstate[0].churchman = 0;
boatstate[1].wildman = 1;
boatstate[1].churchman = 1;
boatstate[2].wildman = 0;
boatstate[2].churchman = 2;
boatstate[3].wildman = 1;
boatstate[3].churchman = 0;
boatstate[4].wildman = 0;
boatstate[4].churchman = 1;
}
else
{
boatstate[0].wildman = 0;
boatstate[0].churchman = 1;
boatstate[1].wildman = 1;
boatstate[1].churchman = 0;
boatstate[2].wildman = 0;
boatstate[2].churchman = 2;
boatstate[3].wildman = 1;
boatstate[3].churchman = 1;
boatstate[4].wildman = 2;
boatstate[4].churchman = 0;
}
int i; // 用来控制算符
if (pquest->boat.wildman == 0 && pquest->boat.churchman == 0) // 初始状态, 第一次渡河时
i = 0; // 取算符1
else
{
for (i=0; i<5; i++) // 扩展同一节点时, 已经用过的算符不再用, 按优先级来
if (pquest->boat.wildman == boatstate[i].wildman && pquest->boat.churchman == boatstate[i].churchman)
break;
i++;
}
if (i < 5)
{
int j;
for (j=i; j<5; j++)
{
int nwildman1 = pquest->riverside1.wildman + boatstate[j].wildman * pquest->side;
int nchurchman1 = pquest->riverside1.churchman + boatstate[j].churchman * pquest->side;
int nwildman2 = 3 - nwildman1;
int nchurchman2 = 3 - nchurchman1;
// 判断本次操作的安全性, 即牧师数量>=野人或牧师数为0
if ((nwildman1 <= nchurchman1 || nchurchman1 == 0) &&
(nwildman2 <= nchurchman2 || nchurchman2 == 0) &&
nwildman1 >=0 && nchurchman1 >=0 && nwildman2 >=0 && nchurchman2 >= 0)
{
// 本操作是否重复上次操作,注意方向不同
if (pquest->pprev != null)
{
if (pquest->pprev->boat.wildman == boatstate[j].wildman &&
pquest->pprev->boat.churchman == boatstate[j].churchman)
continue;
}
break; // 该操作可行, 推出循环，只找出当前最优节点
}
}
if (j < 5)
{
pquest->boat.wildman = boatstate[j].wildman;
pquest->boat.churchman = boatstate[j].churchman;
return true;
}
}
return false;
}
思路：2野 2传 1传1野
有点麻烦
急！求野人过河问题用c语言实现！！~
本来没打算发出来。送你算了。
下面的程序称得上perfect,程序在dev-c++下编译通过.
#include
#include
#include
#define maxloop 100 /* 最大层数，对于不同的扩展方法自动调整取值 */
#define pristnum 3 /*初始化时设定有3个野人3个传教士，实际可以改动*/
#define slavenum 3
struct SPQ{ int sr,pr; /* 船运行一个来回后河右岸的野人、传教士的人数 */
int sl,pl; /* 船运行一个来回后河左岸的野人、传教士的人数 */
int ssr,spr; /* 回来（由左向右时）船上的人数 */
int sst,spt; /* 去时（由右向左时）船上的人数 */
int loop; /* 本结点所在的层数 */
struct SPQ *upnode ,*nextnode;/* 本结点的父结点和同层的下一个结点的地址 */
}spq;
int loopnum;/* 记录总的扩展次数 */
int openednum;/* 记录已扩展节点个数 */
int unopenednum;/* 记录待扩展节点个数 */
int resultnum;
struct SPQ *opened;
struct SPQ *oend;
struct SPQ *unopened;
struct SPQ *uend;
struct SPQ *result;
void initiate();
void releasemem();
void showresult();
void addtoopened(struct SPQ *ntx);
int search();
void goon();
int stretch(struct SPQ* ntx);
void recorder();
int main()
{
int flag; /* 标记扩展是否成功 */
for( ; ; )
{
initiate();
flag = search ();
if(flag == 1)
{
recorder();
releasemem();
showresult();
goon();
}
else
{
printf("无法找到符合条件的解");
releasemem();
goon();
}
}
system("pause");
return 0;
}
void initiate()
{
int x;
char choice;
uend = unopened = (struct SPQ*)malloc(sizeof(spq));
if(uend==NULL)
{
printf("
内存不够！
");
exit(0);
}
unopenednum=1;
openednum=0;
unopened -> upnode = unopened; /* 保存父结点的地址以成链表 */
unopened -> nextnode = unopened;
unopened -> sr = slavenum;
unopened -> pr = pristnum;
unopened -> sl = 0;
unopened -> pl = 0;
unopened -> sst = 0;
unopened -> spt = 0;
unopened -> ssr = 0;
unopened -> spr = 0;
unopened -> loop = 0;
printf("题目：设有n个传教士和m个野人来到河边，打算乘一只船从右岸到左岸去。
");
printf("该船的负载能力为两人。在任何时候，如果野人人数超过传教士人数，野人
");
printf("就会把传教士吃掉。他们怎样才能用这条船安全的把所有人都渡过河去?
");
printf("
默认的n、m值皆为3
");
for(;;)
{
printf("
是否修改？(Y/N)");
scanf("%s",&choice);
choice=toupper(choice);
if(choice=='Y')
{
printf("
请输入传教士人数");
for(;;)
{
scanf("%d",&x);
if(x>0)
{
unopened -> pr = x;
break;
}
else printf("
输入值应大于0！
请重新输入");
}
printf("
请输入野人人数");
for(;;)
{
scanf("%d",&x);
if(x>0)
{
unopened -> sr = x;
break;
}
else printf("
输入值应大于0！
请重新输入");
}
break;
}
if(choice=='N')break;
}
}
int search()
{
int flag;
struct SPQ *ntx; /* 提供将要扩展的结点的指针 */
for( ; ; )
{
ntx = unopened; /* 从待扩展链表中提取最前面的一个 */
if(ntx->loop == maxloop)
return 0;
addtoopened(ntx); /* 将ntx加入已扩展链表，并将这个节点从待扩展链表中去掉 */
flag = stretch(ntx); /* 对ntx进行扩展,返回-1,0,1 */
if(flag == 1)
return 1;
}
}
int stretch(struct SPQ *ntx)
{
int fsr , fpr ; /* 在右岸上的人数 */
int fsl , fpl ; /* 在左岸上的人数 */
int sst , spt ; /* 出发时在船上的人数 */
int ssr , spr ; /* 返回时船上的人数 */
struct SPQ *newnode;
for (sst = 0 ; sst <= 2 ; sst++) /* 讨论不同的可能性并判断是否符合条件 */
{
fsr = ntx -> sr;
fpr = ntx -> pr;
fsl = ntx -> sl;
fpl = ntx -> pl;
if ((sst <= fsr) && (( 2 - sst) <= fpr))/* 满足人数限制 */
{
spt = 2 - sst;
fsr = fsr - sst;
fpr = fpr - spt;
if((fpr == 0) && (fsr == 0))/* 搜索成功 */
{
newnode = (struct SPQ*) malloc (sizeof(spq));
if(newnode==NULL)
{
printf("
内存不够！
");
exit(0);
}
newnode -> upnode = ntx; /* 保存父结点的地址以成链表 */
newnode -> nextnode = NULL;
newnode -> sr = 0;
newnode -> pr = 0;
newnode -> sl = opened -> sr;
newnode -> pl = opened -> pr;
newnode -> sst = sst;
newnode -> spt = spt;
newnode -> ssr = 0;
newnode -> spr = 0;
newnode -> loop = ntx -> loop + 1;
oend -> nextnode = newnode;
oend = newnode;
openednum++;
return 1;
}
else if ((fpr - fsr) * fpr >= 0) /* 判断是否满足传教士人数必须大于或等于野人人数 */
{
fsl = fsl + sst;
fpl = fpl + spt;
for (ssr = 0 ; ssr <= 1 ; ssr++) /* 返回 */
{
int ffsl , ffpl;
if ((ssr <= fsl) && ((1 - ssr) <= fpl))
{
spr = 1 - ssr;
ffsl = fsl - ssr;
ffpl = fpl - spr;
if ((ffpl - ffsl) * ffpl >= 0)
{ /* 若符合条件则分配内存并付值 */
int ffsr , ffpr;
ffsr = fsr + ssr;
ffpr = fpr + spr;
newnode = (struct SPQ*) malloc (sizeof(spq));
if(newnode==NULL)
{
printf("
内存不够！
");
exit(0);
}
newnode -> upnode = ntx; /* 保存父结点的地址以成链表 */
newnode -> sr = ffsr;
newnode -> pr = ffpr;
newnode -> sl = ffsl;
newnode -> pl = ffpl;
newnode -> sst = sst;
newnode -> spt = spt;
newnode -> ssr = ssr;
newnode -> spr = spr;
newnode -> loop = ntx -> loop + 1;
uend -> nextnode = newnode;
uend = newnode;
unopenednum++;
}
}
}
}
}
}
return 0;
}
void addtoopened(struct SPQ *ntx)
{
unopened = unopened -> nextnode;
unopenednum--;
if (openednum == 0 )
oend = opened = ntx;
oend -> nextnode = ntx;
oend = ntx;
openednum++;
}
void recorder()
{
int i , loop;
struct SPQ *newnode;
struct SPQ *ntx;
loop = oend -> loop;
ntx = oend;
resultnum = 0;
for( i = 0 ; i <= loop ; i++ )
{
newnode = (struct SPQ*) malloc (sizeof(spq));
if(newnode==NULL)
{
printf("
内存不够！
");
exit(0);
}
newnode -> sr = ntx -> sr;
newnode -> pr = ntx -> pr;
newnode -> sl = ntx -> sl;
newnode -> pl = ntx -> pl;
newnode -> sst = ntx -> sst;
newnode -> spt = ntx -> spt;
newnode -> ssr = ntx -> ssr;
newnode -> spr = ntx -> spr;
newnode -> nextnode = NULL;
ntx = ntx -> upnode;
if(i == 0)
result = newnode;
newnode -> nextnode = result;
result = newnode;
resultnum++;
}
}
void releasemem()
{
int i;
struct SPQ* nodefree;
for ( i = 1 ; i < openednum ; i++ )
{
nodefree = opened;
opened = opened -> nextnode;
free(nodefree);
}
for ( i = 0 ; i < unopenednum ; i++ )
{
nodefree = unopened;
unopened = unopened -> nextnode;
free(nodefree);
}
}
void showresult()
{
int i;
int fsr , fpr ; /* 在右岸上的人数 */
int fsl , fpl ; /* 在左岸上的人数 */
struct SPQ* nodefree;
printf("%d个传教士",result -> pr);
printf("%d个野人",result -> sr);
printf("%d个传教士",result -> pl);
printf("%d个野人",result -> sl);
for ( i = 1 ; i < resultnum ; i++ )
{
nodefree = result;
result = result -> nextnode;
free(nodefree);
printf("
左岸人数 船上人数及方向 右岸人数
");
printf("第%d轮
",i);
fpl = result -> pl - result -> spt + result -> spr;
fpr = result -> pr - result -> spr;
fsl = result -> sl - result -> sst + result -> ssr;
fsr = result -> sr - result -> ssr;
printf("传教士%8d%8d spt,fpr);
printf("野 人%8d%8d sst,fsr);
printf("传教士%8d%8d->%8d
",result -> pl,result -> spr,result -> pr - result -> spr);
printf("野 人%8d%8d->%8d
",result -> sl,result -> ssr,result -> sr - result -> ssr);
}
printf("
全体传教士和野人全部到达对岸");
free(result);
}
void goon()
{
char choice;
for(;;)
{
printf("是否继续？(Y/N)
");
scanf ("%s" , &choice);
choice=toupper(choice);
if(choice=='Y')break;
if(choice=='N')exit(0);
}
}
野人过河问题算法分析
野人过河问题算法分析
野人过河问题属于人工智能学科中的一个经典问题，问题描述如下： 有三个牧师（也有的翻译为传教士）和三个野人过河，只有一条能装下两个人的船，在河的任何一方或者船上，如果野人的人数大于牧师的人数，那么牧师就会有危险. 你能不能找出一种安全的渡河方法呢？
一、算法分析
先来看看问题的初始状态和目标状态，假设和分为甲岸和乙岸：
初始状态：甲岸，3野人，3牧师；
乙岸，0野人，0牧师；
船停在甲岸，船上有0个人；
目标状态：甲岸，0野人，0牧师；
乙岸，3野人，3牧师；
船停在乙岸，船上有0个人；
整个问题就抽象成了怎样从初始状态经中间的一系列状态达到目标状态。问题状态的改变是通过划船渡河来引发的，所以合理的渡河操作就成了通常所说的算符，根据题目要求，可以得出以下5个算符（按照渡船方向的不同，也可以理解为10个算符）：
渡1野人、渡1牧师、渡1野人1牧师、渡2野人、渡2牧师
算符知道以后，剩下的核心问题就是搜索方法了，本文采用深度优先搜索，通过一个FindNext(…)函数找出下一步可以进行的渡河操作中的最优操作，如果没有找到则返回其父节点，看看是否有其它兄弟节点可以扩展，然后用Process(…)函数递规调用FindNext(…)，一级一级的向后扩展。
搜索中采用的一些规则如下：
1、渡船优先规则：甲岸一次运走的人越多越好（即甲岸运多人优先），同时野人优先运走；
乙岸一次运走的人越少越好（即乙岸运少人优先），同时牧师优先运走；
2、不能重复上次渡船操作（通过链表中前一操作比较），避免进入死循环;
3、任何时候河两边的野人和牧师数均分别大于等于0且小于等于3；
4、由于只是找出最优解，所以当找到某一算符（当前最优先的）满足操作条件后，不再搜索其兄弟节点，而是直接载入链表。
5、若扩展某节点a的时候，没有找到合适的子节点，则从链表中返回节点a的父节点b，从上次已经选择了的算符之后的算符中找最优先的算符继续扩展b。
二、基本数据结构
仔细阅读问题，可以发现有些基本东西我们必须把握，例如：每时刻河两岸野人牧师各自的数目、船的状态、整个问题状态。所以我们定义如下几个数据结构：
typedef struct _riverside // 岸边状态类型
{
int wildMan; // 野人数
int churchMan; // 牧师数
}RIVERSIDE;
typedef struct _boat // 船的状态类型
{
int wildMan; // 野人数
int churchMan; // 牧师数
}BOAT;
typedef struct _question // 整个问题状态
{
RIVERSIDE riverSide1; // 甲岸
RIVERSIDE riverSide2; // 乙岸
int side; // 船的位置, 甲岸为-1, 乙岸为1
BOAT boat; // 船的状态
_question* pPrev; // 指向前一渡船操作
_question* pNext; // 指向后一渡船操作
}QUESTION;
用QUESTION来声明一个最基本的链表。
三、程序流程及具体设计
本文只找出了最优解，据我所知，本问题有三种解。如果真要找出这三种解，^_^，那就得加强对链表的操作了，比如说自己写一个动态链表类，顺便完成一些初始化工作，估计看起来会舒服些。
下面给出部分关键程序：
// 主函数
int main()
{
// 初始化
QUESTION* pHead = new QUESTION;
pHead->riverSide1.wildMan = 3;
pHead->riverSide1.churchMan = 3;
pHead->riverSide2.wildMan = 0;
pHead->riverSide2.churchMan = 0;
pHead->side = -1; // 船在甲岸
pHead->pPrev = NULL;
pHead->pNext = NULL;
pHead->boat.wildMan = 0;
pHead->boat.churchMan = 0;
if (Process(pHead))
{
// ......... 遍历链表输出结果
}
cout<<"成功渡河。";
}
else
cout<<"到底怎样才能渡河呢? 郁闷!"<<endl;
// 回收内存空间
while (pHead)
{
QUESTION* pTemp = pHead->pNext;
delete pHead;
pHead=pTemp;
}
pHead = NULL;
return 0;
}
// 渡船过程, 递规调用函数FindNext(...)
BOOL Process(QUESTION* pQuest)
{
if (FindNext(pQuest))
{
QUESTION* pNew = new QUESTION;
pNew->riverSide1.wildMan = pQuest->riverSide1.wildMan + pQuest->boat.wildMan*(pQuest->side);
pNew->riverSide1.churchMan = pQuest->riverSide1.churchMan + pQuest->boat.churchMan*(pQuest->side);
pNew->riverSide2.wildMan = 3 - pNew->riverSide1.wildMan;
pNew->riverSide2.churchMan = 3 - pNew->riverSide1.churchMan;
pNew->side = (-1)*pQuest->side;
pNew->pPrev = pQuest;
pNew->pNext = NULL;
pNew->boat.wildMan = 0;
pNew->boat.churchMan = 0;
pQuest->pNext = pNew;
if (pNew->riverSide2.wildMan==3 && pNew->riverSide2.churchMan==3)
return TRUE; // 完成
return Process(pNew);
}
else
{
QUESTION* pPrev = pQuest->pPrev;
if (pPrev == NULL)
return FALSE; // 无解
delete pQuest;
pPrev->pNext = NULL;
return Process(pPrev); // 返回其父节点重新再找
}
return TRUE;
}
// 判断有否下一个渡河操作, 即根据比较算符找出可以接近目标节点的操作
// 算符共5个: 1野/ 1牧 / 1野1牧 / 2野 / 2牧
BOOL FindNext(QUESTION* pQuest)
{
// 基本规则
// 渡船的优先顺序: 甲岸运多人优先, 野人优先; 乙岸运少人优先, 牧师优先.
static BOAT boatState[5]; // 5个算符
if (pQuest->side == -1)
{
boatState[0].wildMan = 2;
boatState[0].churchMan = 0;
boatState[1].wildMan = 1;
boatState[1].churchMan = 1;
boatState[2].wildMan = 0;
boatState[2].churchMan = 2;
boatState[3].wildMan = 1;
boatState[3].churchMan = 0;
boatState[4].wildMan = 0;
boatState[4].churchMan = 1;
}
else
{
boatState[0].wildMan = 0;
boatState[0].churchMan = 1;
boatState[1].wildMan = 1;
boatState[1].churchMan = 0;
boatState[2].wildMan = 0;
boatState[2].churchMan = 2;
boatState[3].wildMan = 1;
boatState[3].churchMan = 1;
boatState[4].wildMan = 2;
boatState[4].churchMan = 0;
}
int i; // 用来控制算符
if (pQuest->boat.wildMan == 0 && pQuest->boat.churchMan == 0) // 初始状态, 第一次渡河时
i = 0; // 取算符1
else
{
for (i=0; i<5; i++) // 扩展同一节点时, 已经用过的算符不再用, 按优先级来
if (pQuest->boat.wildMan == boatState[i].wildMan && pQuest->boat.churchMan == boatState[i].churchMan)
break;
i++;
}
if (i < 5)
{
int j;
for (j=i; j<5; j++)
{
int nWildMan1 = pQuest->riverSide1.wildMan + boatState[j].wildMan * pQuest->side;
int nChurchMan1 = pQuest->riverSide1.churchMan + boatState[j].churchMan * pQuest->side;
int nWildMan2 = 3 - nWildMan1;
int nChurchMan2 = 3 - nChurchMan1;
// 判断本次操作的安全性, 即牧师数量>=野人或牧师数为0
if ((nWildMan1 <= nChurchMan1 || nChurchMan1 == 0) &&
(nWildMan2 <= nChurchMan2 || nChurchMan2 == 0) &&
nWildMan1 >=0 && nChurchMan1 >=0 && nWildMan2 >=0 && nChurchMan2 >= 0)
{
// 本操作是否重复上次操作,注意方向不同
if (pQuest->pPrev != NULL)
{
if (pQuest->pPrev->boat.wildMan == boatState[j].wildMan &&
pQuest->pPrev->boat.churchMan == boatState[j].churchMan)
continue;
}
break; // 该操作可行, 推出循环，只找出当前最优节点
}
}
if (j < 5)
{
pQuest->boat.wildMan = boatState[j].wildMan;
pQuest->boat.churchMan = boatState[j].churchMan;
return TRUE;
}
}
return FALSE;
}
用java实现野人传教士过河问题
答：n); for(Node node : resultList) { System.out.println("左岸传教士："+node.getLeftPeo()+"左岸野人： "+node.getLeftSavage()+" 右岸传教士： "+node.getRightPeo()+"右岸野人："+node.getRightSavage()+"船上传教士："+node.getOnBoatPeoNum()+"船上野人："+node.getOnBoatSa...
人工智能野人传教士过河
答：我用 Python 写了搜寻答案的程序。要知道其它组合有没有解，只要改一改 “mCOUNT, cCOUNT = 3, 3” 这一行然后运行就知道了。有空的话我会译成 Java 贴上来。'''Solve the Missionaries And Cannibals Puzzle by trying all legal moves.The puzzle imposes two constraints:1) Relative headcoun...
急求 人工智能 野人传教士过河问题,详解!!!
答：2个传教士去，1个野人与1个传教士回 2个传教士去，1个野人回 2个野人去，1个野人回 2个野人去，完成 不合法的状态和重复状态，我都没画出，你可以自己加一下，也可以结合图 说明一下
过河问题
答：野人过河问题属于人工智能学科中的一个经典问题，问题描述如下： 有三个牧师（也有的翻译为传教士）和三个野人过河，只有一条能装下两个人的船，在河的任何一方或者船上，如果野人的人数大于牧师的人数，那么牧师就会有危险. 你能不能找出一种安全的渡河方法呢？一、算法分析 先来看看问题的初始状态和...
传教士和野蛮人 又一个过河问题
答：第一次：1个传教士1个野蛮人坐船去右边，然后1个传教士坐船回左边 第二次：2个野蛮人坐船去右边，然后1野蛮人坐船回左边 第三次：2个传教士坐船去右，然后1个野蛮人1个传教士坐船回左 第四次：2个传教士坐船去右边，1个野蛮人坐船回左边（到这里为止，应该是左边3个野蛮人，右边3个传教士）第...
A*算法野人传教士问题,估价函数h(n)为什么等于m+n-2b?
答：即m+n-2；当b = 0 时，船在右岸，此时需要修道士或者野人从右岸划船到左岸，最少过去1人，因此状态转换后左岸最少剩余人数为m+n+1；综合两种情况，状态转变后左岸剩余人数大于等于m+n-2*b，最小值是m+n-2*b，因此h(n)设定为h(n) = m+n-2*b ...
传教士和野蛮人如何过河?
答：三名传教士和三个野蛮人同在一个小河渡口，渡口上只有一条可容两人的小船。问题的目标是要用这条小船把这六个人全部渡到对岸去，条件是在渡河的过程中，河两岸随时都保持传教士人数不少于野蛮人的人数，否则野蛮人会把处于少数的传教士吃掉。这六个人怎样才能安全渡过去？［答案：可以这样渡河 1.一名...
用状态空间表示表示问题的一般步骤
答：利用状态空间图求解的具体思路和步骤：（1）设定状态变量及确定值域；（2）确定状态组，分别列出初始状态集和目标状态集；（3）定义并确定操作集；（4）估计全部状态空间数，并尽可能列出全部状态空间或予以描述之；（5）当状态数量不是很大时，按问题的有序元组画出状态空间图，依照状态空间图搜索求解。
传教士与野人过河的数学问题
答：N个过不了吧（N>3），因为左右两边传教士的增长最多为2，由于传教士人数等于野人人数会导致某一时刻至少有一侧野人数大于传教士数。（当一侧传教士数为0时的情况舍去）
传教士和野人各三人过河,只有一条船,都会划船,一次只能载两人,野多于...
答：2个野人去，1个野人回 2个野人去，1个野人回 2个传教士去，1个野人与1个传教士回 2个传教士去，1个野人回 2个野人去，1个野人回 2个野人去，完成
