AI 搜索以解决传教士和食人族问题
4.40/5 (24投票s)
2006年11月3日
5分钟阅读
198117
2799
使用 AI 搜索解决传教士和食人族问题。
引言
本文介绍了如何使用 AI 搜索技术解决一个逻辑问题。
那么，我们要解决的问题是什么？
问题的描述如下。河的一边有三个传教士和三个食人族。有一艘船可以用来将人从河的一边转移到另一边。
船上最多只能坐两个人，并且在任何一次转移过程中必须至少有一个人在船上。问题是要找到最短的转移序列，将所有六个人从一边转移到另一边，而在此过程中，任何一边河岸上的传教士人数都不能超过食人族人数。（这样做的目的是，如果发生这种情况，传教士就能通过“转化”食人族来腐化他们。）要令人满意地解决这个问题，您的程序必须明确识别出所有最优（即最短）的解决方案。
AI 搜索算法是如何工作的？
嗯，有几种不同的搜索方式可供选择，例如广度优先搜索、深度优先搜索或迭代加深搜索。这些不同的搜索方法各有不同的特性，例如是否能保证找到结果，以及进行搜索所需的时间和空间。
本文使用广度优先搜索，因为这种搜索方法保证能找到一个解决方案。
搜索通常涉及在单个搜索状态的搜索空间中寻找一个或多个解决方案。通常，搜索空间是一个列表或某种集合，其中包含要检查是否为解决方案状态的每个状态。
广度优先搜索算法
广度优先搜索依赖于上面提到的基本搜索原理。特别有趣的是，广度优先搜索实际是如何寻找解决方案状态的。
为了说明这一点，请考虑下图，其中每个椭圆形代表一个单独的状态。
从上图可以看出，存在许多状态，但搜索是如何为给定的解决方案选择要查看哪些状态的？
在使用广度优先搜索时，当前层的每个状态都会在移动到下一层状态之前进行扩展。在上图中，可以看到根状态被扩展以找到状态 A1、A2 和 A3。此级别没有更多状态，因此选择了 A1 并进行了扩展，从而产生了 A1.1 -> A1.3。但是，在查看 A1.1 -> A1.3 这些新状态之前，必须先扩展 A2 和 A3，所以接下来会扩展 A2 和 A3。如果当前级别没有更多状态可供扩展，则扩展下一级别的第一个节点，直到找到解决方案（或解决方案）。这就是广度优先搜索的基础。
那么这如何转化为算法？
下面的算法演示了广度优先搜索在寻找单个解决方案时应如何工作。
- 创建一个名为 SearchAgenda（例如）的变量，并将其设置为初始状态（在我们的示例中为 Root）。
- 直到找到目标状态（Solution）或 SearchAgenda 为空，执行以下操作：
- 从 SearchAgenda 中移除第一个元素，并将其命名为 CurrState。如果 SearchAgenda 为空，则退出。
- 对于规则匹配 CurrState 中描述的状态的每种方式，执行以下操作：
- 应用规则生成新的状态，这些称为后继状态（Successor states）。
- 如果新状态是目标状态（Solution），则退出并返回该状态。
- 否则，将新状态添加到 SearchAgenda 的末尾。
这是算法的基础。但是，任何 AI 搜索技术都需要考虑一些相当重要的因素。这些因素将在下面解释。
查找后继状态
这是任何搜索算法的基本组成部分，也是拥有成功的搜索算法的关键。对于传教士和食人族问题，我们可以考虑下图。
从上图可以看出，许多状态是无效的，因此已被修剪（丢弃）出搜索树。这意味着这些状态不会生成后继状态。
确定新状态是否为目标
对于传教士和食人族问题，这仅仅是将所有三个传教士和所有三个食人族转移到河的另一边。
使用代码
附带的演示项目实际上包含了一个 Visual Studio 2005 解决方案，其中包含以下三个类：
程序
是 CannMissApp 应用程序的主要入口点。基本上，这个类所做的就是调用 SolutionProvider 的 getSolutionStates 方法，然后打印解决方案（如果有的话）。
.....
.....
SolutionProvider S = new SolutionProvider();
ArrayList Solution = S.getSolutionStates(new State("Root", 3, 3, false,1),
new State("Goal", 0, 0, true,999999));
printSolutions(Solution);
....
....
//This method prints the Solutions returned
//by the SolutionProvider object.
//However, there may not actually be any solutions to print.
//
//Once a SolutionProvider is created this
//class asks it to provide all the
//solutions. If there are any solutions
//returned these are then printed
//
//param : Solution the Solutions returned
// by the SolutionProvider object.
private static void printSolutions(ArrayList Solution)
{
//Are there any solutions
if (Solution.Count == 0)
{
Console.WriteLine("\n\nNO SOLUTIONS HAVE BEEN FOUND\r\n");
}
else
{
int Solfound = 1;
//show the Solutions
for (int i = 0; i < Solution.Count; i++)
{
State s = (State)Solution[i];
Console.WriteLine("=====FOUND SOLUTION [" +
Solfound++ + "]=====\r\n");
Console.WriteLine("This solution was found at level [" +
s.getStateLevel() + "]\r\n");
s.Print();
Console.WriteLine("\r\n");
}
}
}
SolutionProvider
提供“食人族和传教士”搜索问题的解决方案。
using System;
using System.Collections.Generic;
using System.Collections;
using System.Text;
namespace MissCanApp
{
#region SolutionProvider CLASS
//SolutionProvider - Provides solutions
//to the "Cannibals and Missionaries"
//Search problem.
//
//HOW THE SEARCH IS PERFORMED
//
//This class uses a breadth 1st search
//to search for possible solutions.
//A ArrayList is used to store the agenda.
//The agenda consists of a list of State
//classes. The root State will be the 1st
//item in the agenda. When the root
//is taken from the agenda, it is compared
//to the goal state, if it is the goal
//state it will be stored within a
//SolutionsFound ArrayList. However the 1st node
//in the search agenda it not likely to
//be the goal so different successor
//states will be generated from the root
//and these will be added to the agenda.
//Each of these states will then be taken
//from the agenda and compared to the
//goal, if they are equal to the
//goal they will be stored within a
//SolutionsFound ArrayList. However if they
//are not the goal state, they too will
//be expanded to create successor states,
//which will then be added to the agenda.
//
//The solutions may be found at various
//levels within the search tree. This application
//should return the optimal solustions.
//To achieve this the 1st solution has its level
//within the search tree recorded. Then when new
//solutions are found they are compared
//to this level, if they are less than or the
//same they too are stored as valid optimal
//solutions. Only when the solutions found are
//found at a higher level does the search know
//that it has found all the optimal solutions.
//When this occurs the search is ended, and the
//optimal solutions returned.
class SolutionProvider
{
// Instance fields
private int CURRENT_ROOT_STATE = 0;
private ArrayList searchAgenda = new ArrayList();
//SolutionProvider Constructor
//Simply creates a new SolutionProvider object
public SolutionProvider()
{
}
//Creats a new State based on
//a parent state. The formal parameters
//supplied dictate what changes are
//to be applied to the parent
//state to form the new child state
//
//@param : StateName represents the new state name
//
//param : parent is the parent State
//that this State should be generated from.
//Ie the new State will be a child of this parameter
//
//param : nMiss number of Missionaries
//in the boat for the new state
//
//param : nCan number of Cannibals in the boat for the new state
private void addStateToAgenda(String StateName,State parent,
int nMiss, int nCan)
{
// BoatDirection holds either 1 or -1, depending on the side.
int BoatDirection = parent.Side ? 1 : -1;
//Get the name of the parent state and add append the new state
//suffix to it
String newStateName = parent.getStateName() + StateName;
//Create a new state based on the parent state parameter that was
//supplied when calling this method
State newState = new State(newStateName,
parent.nMiss + nMiss * BoatDirection,
parent.nCan + nCan * BoatDirection,
!parent.Side,
parent, parent.getStateLevel() + 1);
//Try and add the newly generated State to the search agenda
addStateToAgenda(newState);
}
//Tries to add the NewState parameter provided to the search agenda.
//If the state parameter provided is
//not a valid state, the state will not
//be added to the agenda. The State
//class deals with checking for a ValidState
//
//param : NewState the state to try and add it to the search agenda
private void addStateToAgenda(State newState)
{
// Dont allow invalid states to be added to search agenda
if (newState.InvalidState())
return;
//Valid state so add it to the agenda
searchAgenda.Add(newState);
}
//This is the main method that does most of the work. It carries out
//various tasks. These are described below
//
//The 1st thing that is done is the
//internal SolutionsFound collection is
//initialized and the StartState
//(From the formal parameter) is added to the
//Search Agenda
//
//Then a loop is enetered that loops through
//the entire agenda taking off
//the 0 element when 1st entering the loop.
//For readability I have defined
//the 0 elemenet to be an int called
//CURRENT_ROOT_STATE. This variable is
//a simply int that is set to 0 when
//the SolutionProvider class is constructed.
//
//When the CURRENT_ROOT_STATE element
//is removed from the Search Agenda it is
//cast to a State then compared to
//the GoalState (From the formal parameter).
//If it equals the goal state (Dealt
//with by the State class) and is the 1st
//solution found the level of the state
//is recorded, and the state is stored
//within the SolutionsFound collection.
//If this is not the 1st solution found
//the state level of this new solution
//is compared to the recorded state level
//of the 1st solution. If this solution
//is less than or equal to the recorded
//optimal level, then it too may be added
//to the SolutionsFound collection.
//However if it is not the goal state,
//which is will not be for the 1st State
//(ROOT) then new succeessor nodes will
//need to be created based upon this parent
//node. The generateSucessors method deals with this.
//
//param : StartState the StartState, with all Cannibals/Missionaries
//on one side of the river
//
//param : EndState the StartState, with all Cannibals/Missionaries
//on the opposite side of the river
//
//return : ArrayList that holds all the solutions found
public ArrayList getSolutionStates(State StartState, State EndState)
{
//initialise local fields
int optimalSolfoundAtLevel = 0;
bool allOptimalSolutionsFound = false;
bool foundFirstSolution = false;
//Initialise SolutionsFound collection
ArrayList Solutions = new ArrayList();
//Add StartState to the Search Agenda
addStateToAgenda(StartState);
//Loop through search agenda until
//we have found all the optimal solutions
while (searchAgenda.Count > 0 && !allOptimalSolutionsFound) {
//Get the current root state from the Search Agenda
State CurState = (State)searchAgenda[CURRENT_ROOT_STATE];
//Remove the current root state from the Search Agenda, is has been
//dealt with now
searchAgenda.RemoveAt(CURRENT_ROOT_STATE);
//Is the current root state the Goal State
if (CurState.Equals(EndState)) {
//Has the 1st solution been found
if (foundFirstSolution) {
//YES the 1st solution was found so lets
//compare this states level to the existing level
//from when the 1st solution was found
if (CurState.getStateLevel() <= optimalSolfoundAtLevel) {
//If it is, store the state in
//the SolutionsFound collection
Solutions.Add(CurState);
}
else {
//since the current state level is
//greater than the optimalSolfoundAtLevel
//this solution must be more costly,
//we must have already found all the optimal solutions.
//so need to break out of loop, so set break condition
allOptimalSolutionsFound =true;
}
}
else {
//At this point this must be the 1st solution
//found, so store it and record its level
//in the optimalSolfoundAtLevel, so that this
//can be used to compare against
//for the next solutions found.
//Also prevent this logic froming running
//again by setting the foundFirstSolution to true.
foundFirstSolution=true;
optimalSolfoundAtLevel = CurState.getStateLevel();
Solutions.Add(CurState);
}
}
else {
//The current root state is NOT Goal State, so create
//sucessor states based on it
generateSucessors(CurState);
}
}
return Solutions;
}
//This method simply calls the addStateToAgenda method
//passing in all required derivations of the CurState state
//to be new sucessor nodes
//
//param : CurState the current state
//to use to create sucessor nodes from
private void generateSucessors(State CurState) {
//if this method has been called the CurState, was NOT the goal,
//so need to create new sucessor
//states based on it. So try and create
//some new states.
int nCan, nMiss =0;
int stateName =1;
//loop through all possible combinations
for (int i = 0; i <= Program.boatsize; i++)
{
for (int j = 0; j <= Program.boatsize; j++)
{
//prune the search tree, getting rid of invalid states
if (i==0 && j ==0)
continue;
if (i + j > Program.boatsize)
break;
//good state found, so add to agenda
nMiss = i;
nCan = j;
addStateToAgenda("_" + stateName++, CurState, nMiss, nCan);
}
}
}
} //End of SolutionProvider class
#endregion
}
状态
是对 Search Agenda 中的一个节点（node）的表示。每个 State 都包含各种数据，有助于模拟特定的状态，例如传教士数量、食人族数量、船所在的一侧等。
using System;
using System.Collections.Generic;
using System.Text;
namespace MissCanApp
{
#region State CLASS
// State - Is a representation of a node
//with the Search Agenda. Each State
// holds various bits of data which help to model a specific state.
// These data elements are described below.
//
// Number of Missionaries within the current state
//
// Number of Cannibals within the current state
//
// Side that the boat is on. False is one side, True is the other side
//
// Name of the State. This will be expanded
//upon for each successor state
// so that a full StateName can be printed, to show the full search path
// that this state used to get to where it is now
//
// PrevState is the previous state, this is the parent state from which this
// state was created. This will be null for the ROOT state, as it does not
// have a previous state
// State Level is the level that this states in on in the search tree
class State
{
// Instance fields
public int nMiss, nCan;
public bool Side;
private int NumOfEachAtStart = 3;
private String Name;
private State PrevState;
private int stateLevel = 0;
//State Constructer (1), Use this for the root state
//Simply creates a new State with the name, number of Missionaries,
//number of Cannibals and side to match the values supplied by
//the formal parameters. In this case there will be no PrevState as this
//is the 1st state
//
//param : Name is the name for this State
//param : nMiss the number on Missionaries for this state
//param : nCan the number on Cannibals for this state
//param : Side the side of the river that the boat is now on
//param : stateLevel the level this state is on,
// 0=root / 1st layer, 1 = 2nd layer, 2 = 3rd layer
public State(String Name, int nMiss, int nCan, bool Side,
int stateLevel) : this(Name, nMiss, nCan,
Side, null, stateLevel)
{
//Call the overloaded constructor with the formal parameters
//provided, but make PrevState=null, as the 1st State does not
//have a PrevState to point to
//this(Name, nMiss, nCan, Side, null, stateLevel);
}
//State Constructer (2), Use this to
//create States based upon other States
//Simply creates a new State with the name, number of Missionaries,
//number of Cannibals,side and PrevState to match the values supplied by
//the formal parameters. In this case PrevState will be a pointer to this
//nodes parent node
//
//param : Name is the name for this State
//
//param : nMiss the number on Missionaries for this state
//
//param : nCan the number on Cannibals for this state
//
//param : Side the side of the river that the boat is now on
//
//param : PrevState a pointer to this State's PrevState (parent)
//
//param stateLevel the level this state is on,
// 0=root / 1st layer, 1 = 2nd layer, 2 = 3rd layer
public State(String Name, int nMiss, int nCan, bool Side,
State PrevState, int stateLevel)
{
//Assign parameters to local instance fields
this.Name = Name;
this.nMiss = nMiss;
this.nCan = nCan;
this.Side = Side;
this.PrevState = PrevState;
this.stateLevel = stateLevel;
}
//Simply returns this States stateLevel
//
//return : int representing this States stateLevel
public int getStateLevel()
{
return this.stateLevel;
}
//Simply returns this States name
//
//return : String representing this States name
public String getStateName()
{
return this.Name;
}
//Prints a full search path of how this state came to be at the
//goal state. Makes use of the PrevState to recursively call
//the Print method until there is no PrevState. This way each
//State only prints its own data
public void Print()
{
//Check that there is a PrevState, Root node will not have one, so
//that is when all states from Goal - to start have been printed
if (PrevState != null) {
//Use recursion to allow Previous
//state to print its own data paths
PrevState.Print();
}
//Use the conditional operator to figure out what side we are on
String WhatSide = Side ? " BOAT RIGHT->" : "<-BOAT LEFT ";
//Print the current state.
Console.WriteLine(nMiss + "M/" + nCan + "C " + WhatSide + " " +
(NumOfEachAtStart - nMiss) + "M/" +
(NumOfEachAtStart - nCan) + "C");
}
//Simply returns true is 2 states are the same
//
//param : StateToCheck is the State to check against
//
//return : True if the number of Missionaries,
//number of Cannibals and
//Side are the same for this State
//and the StateToCheck against. Otherwise
//false is returned
public bool Equals(State StateToCheck)
{
return (nMiss == StateToCheck.nMiss &&
nCan == StateToCheck.nCan &&
Side == StateToCheck.Side);
}
//Simply returns true if this State is a valid state
//This method makes use of the command line argument that
//specfies whether there should be more
//Cannibals than Missionaries,
//OR whether there should be more
//Missionaries than Cannibals. Either
//way it uses this global flag to work
//out if the state is valid for the
//given choice that the user made
//when running this application.
//
//return : True only if the number
//of PersonType1 does not outnumber
//the PersonType2 in this state.
//The allocation of whom PersonType1 and
//PersonType2 are, is governed by
//the command line argument to this
//application.
public bool InvalidState()
{
int PersonType1 = 0;
int PersonType2 = 0;
//Check to see if the user requested
//that there be more Cannibals than
//Missionaries. If this is the case set
//PersonType variables for this
//situation
if (Program.CanOutnumberMiss)
{
PersonType1 = nCan;
PersonType2 = nMiss;
}
//Otherwise set the siutation to be that
//there be more Missionaries than
//Cannibals
else
{
PersonType1 = nMiss;
PersonType2 = nCan;
}
// Check for < 0, which could actually
// happen unless it is checked for here
if (nMiss < 0 || nCan < 0 ||
nMiss > NumOfEachAtStart ||
nCan > NumOfEachAtStart)
return true;
//Do PersonType2 outnumbers
//PersonType1(only worry when there is at least
//one PersonType1) one Side1
if (PersonType1 < PersonType2 && PersonType1 > 0)
return true;
//Do PersonType2 outnumbers PersonType1
//(only worry when there is at least
//one PersonType1) one Side2
if ( (NumOfEachAtStart - PersonType1 <
NumOfEachAtStart - PersonType2) &&
(NumOfEachAtStart - PersonType1 > 0))
return true;
//At this point the State must be valid
return false;
}
} //End of State class
#endregion
}
结果
运行时，应用程序将打印找到的所有有效解决方案。它会找到不止一个。
结果应类似于以下内容：
关注点
希望这篇文章能引起一些人的兴趣。
历史
- v1.0 - 2006 年 11 月 3 日。