High score kneeling for crossing the river program algorithm!

CSDNBlog | My Home Page | Contact Author | Aggregation | Log in 5 articles:: 0 favorites:: 0 comments:: 0 citation notices.

essay

C++/Visual C++(RSS)

Algorithm design (RSS)

Game development (RSS)

collect

photo album

Save in the file

June 2004 (4)

April 2004 (1)

Algorithm analysis of savage crossing the river problem

Algorithm analysis of savage crossing the river problem

Savage crossing the river is a classic problem in artificial intelligence. The problem is described as follows: there are three priests (some translated as missionaries) and three savages crossing the river, and only one boat can take two people. On both sides of the river or on the boat, if the number of savages is greater than the number of priests, then the priests are in danger. Can you find a way to cross the river safely?

First, the algorithm analysis

Let's take a look at the initial state and the target state of the problem. Suppose sum is divided into Bank A and Bank B:

Initial state: Jiaan, 3 savage, 3 priest;

B shore, 0 savage, 0 priest;

The ship stopped at shore A, with 0 people on board;

Target status: An, 0 savage, 0 priest;

B shore, 3 savages, 3 priests;

The ship stopped at bank B, with 0 people on board.

The whole problem is abstracted as how to reach the target state from the initial state through a series of intermediate States. The change of the problem state is caused by rowing across the river, so the reasonable crossing operation becomes an operator. According to the requirements of the topic, the following five operators can be obtained (according to the ferry direction, it can also be understood as 10 operator):

Du 1 Savage, Du 1 Pastor, Du 1 Savage 1 Pastor, Du 2 Savage and Du 2 Pastor.

After the operator is known, the remaining core problem is the search method. In this paper, depth-first search is used to find out the best operation of the next river crossing operation through FindNext(…) function. If it is not found, it will return to its parent node to see if there are any other sibling nodes to expand, and then recursively call FindNext(…) with the Process(…) function to expand backward layer by layer.

Some rules used in the search are as follows:

1. Ferry priority rule: The more people transported on shore A at a time, the better (that is, the more people transported on shore A), and the savage gives priority to transport;

The fewer people transported on the second shore at a time, the better (that is, the fewer people transported on the second shore, the better), and the priest gives priority to transportation;

2. The last ferry operation cannot be repeated (compared with the previous operation in the linked list) to avoid entering an infinite loop;

3. At any time, the number of savages and priests on both sides of the river is greater than or equal to 0 and less than or equal to 3 respectively;

4. Because only the optimal solution is found, when an operator (with the highest priority at present) meets the operation conditions, its sibling nodes are not searched, but directly loaded into the linked list.

5. If no suitable child node is found when expanding node A, the parent node B of node A is returned from the linked list, and the operator with the highest priority is found from the operators selected last time to continue expanding B. ..

Second, the basic data structure

Reading the question carefully, we can find some basic things that must be grasped, such as the number of savage priests on both sides of the river at each moment, the state of the ship and the state of the whole question. Therefore, we define the following data structure:

Typedef struct _ riverside//shorestate type

{

Int wildMan// number of savages

Between priests; //Number of priests

} Riverside;

Typedef struct _boat // The status type of the ship.

{

Int wildMan// number of savages

Between priests; //Number of priests

} ship;

Typedef struct _question // whole question status

{

Riverside1; //Jiaan

Riverside riverside 2; //B bank

Int end; //The position of the ship is bank A-1 and bank B-1.

Zhouzhou; //the state of the ship

_ question * pPrev// points to the last ferry operation.

_ question * pNext// Point to the next ferry operation.

} problem;

Use QUESTION to declare a basic linked list.

Third, the program flow and specific design

This paper only seeks the optimal solution. As far as I know, there are three solutions to this problem. If you really want to understand these three solutions, you have to strengthen the operation of linked list, such as writing a dynamic linked list class yourself and completing some initialization work by the way, which is estimated to be more convenient.

Here are some key steps:

//main function

int main()

{

//initialization

QUESTION* pHead = new question;

pHead-& gt； river side 1 . wild man = 3；

pHead-& gt； river side 1 . churchman = 3；

pHead-& gt； river side 2 . wild man = 0；

pHead-& gt； river side 2 . church man = 0；

pHead-& gt； side =- 1； //the ship is on shore a.

pHead-& gt； pPrev = NULL

pHead-& gt； pNext = NULL

pHead-& gt； boat . wild man = 0；

pHead-& gt； boat . churchman = 0；

If (process (pHead))

{

//... traverse the linked list and output the results.

}

Cout & lt& lt "Crossing the river successfully." ;

}

other

Cout & lt& lt "How do we cross the river? Depressed! " & lt& ltendl

//Reclaim memory space

while (pHead)

{

QUESTION * pTemp = pHead-& gt； pNext

Delete pHead

pHead = pTemp

}

pHead = NULL

Returns 0;

}

//Ferry process, recursively call the function FindNext (...)

Boolean process (problem * problem)

{

if (FindNext(pQuest))

{

QUESTION* pNew = new question;

pNew-& gt； river side 1 . wild man = p quest-& gt； river side 1 . wild man+pQuest-& gt； boat . wild man *(p quest-& gt； Side);

pNew-& gt； river side 1 . churchman = p quest-& gt； river side 1 . churchman+pQuest-& gt； boat . churchman *(p quest-& gt； Side);

pNew-& gt； Riverside 2. wildman = 3-pnew-> river side 1 . wild man；

pNew-& gt； Riverside 2. Churchill = 3-pnew-> river side 1 . churchman；

pNew-& gt； side =(- 1)* p quest-& gt； Side;

pNew-& gt； pPrev = pQuest

pNew-& gt； pNext = NULL

pNew-& gt； boat . wild man = 0；

pNew-& gt； boat . churchman = 0；

pQuest-& gt； pNext = pNew

if(pNew-& gt； Riverside 2. wildman = = 3 & pnew-> Riverside 2. Priest ==3)

Return TRUE// Done

Return process (pnew);

}

other

{

quest * PP rev = p quest-& gt； pPrev

if (pPrev == NULL)

Returns FALSE// no solution.

Delete pQuest

pPrev-& gt； pNext = NULL

Return process (pprev); //Return to its parent node and try again.

}

Return TRUE

}

//Judge whether there is the next crossover operation, that is, find out the operation that can be close to the target node according to the comparison operator.

//operator ***5: 1 wild/1 grazing/1 wild 1 grazing /2 wild /2 grazing.

BOOL FindNext (question * question)

{

//Basic rules

//Ferry priority: First, there are many people on the shore, and savages are preferred; B shore transportation with fewer people is preferred, and priests are preferred.

Static ship boat state [5]; // 5 operators

if(pQuest-& gt； side == - 1)

{

Ship state [0]. wild man = 2；

Ship state [0]. churchMan = 0；

boatState[ 1]。 wild man = 1；

boatState[ 1]。 churchMan = 1；

Ship state [2]. wild man = 0；

Ship state [2]. churchMan = 2；

Ship state [3]. wild man = 1；

Ship state [3]. churchMan = 0；

Ship state [4]. wild man = 0；

Ship state [4]. churchMan = 1；

}

other

{

Ship state [0]. wild man = 0；

Ship state [0]. churchMan = 1；

boatState[ 1]。 wild man = 1；

boatState[ 1]。 churchMan = 0；

Ship state [2]. wild man = 0；

Ship state [2]. churchMan = 2；

Ship state [3]. wild man = 1；

Ship state [3]. churchMan = 1；

Ship state [4]. wild man = 2；

Ship state [4]. churchMan = 0；

}

int I； //Used to control operators

if(pQuest-& gt； boat.wildMan = = 0 & amp& amppQuest-& gt； Boat. Churchill = = 0)// Initial state, when crossing the river for the first time.

I = 0； //operator 1

other

{

for(I = 0； I<5; I++) // When extending the same node, the operator that has been used is no longer used, and it is used first.

if(pQuest-& gt； boat.wildMan == boatState[i]。 Wildman & amp& amppQuest-& gt；; boat.churchMan == boatState[i]。 Priest)

Break;

i++；

}

If (I<5)

{

int j；

for(j = I； j & lt5; j++)

{

int nwildman 1 = p quest-& gt； river side 1 . wild man+boat state[j]。 wild man * pQuest-& gt； Side;

int nchurchman 1 = p quest->； Riverside 1. Church member+Boat State [j]. churchMan * pQuest-& gt； Side;

int nwildman 2 = 3-nwildman 1；

int nchurchman 2 = 3-nchurchman 1；

//Judge the safety of this operation, that is, the number of priests > = the number of savages or priests is 0.

if((nwildman 1 & lt； = nchurchman 1 | | nchurchman 1 = = 0)& amp； & amp

(nWildMan2 & lt= nchurchman 2 | | nchurchman 2 = = 0)& amp； & amp

nwildman 1 & gt； = 0 & amp& ampnchurchman 1 & gt； = 0 & amp& ampnWildMan2 & gt= 0 & amp& ampnChurchMan2 >= 0)

{

//Whether this operation repeats the last operation, pay attention to the different directions.

if(pQuest-& gt； pPrev！ = empty)

{

if(pQuest-& gt； pPrev-& gt； boat.wildMan == boatState[j]。 Wildman & &

pQuest-& gt； pPrev-& gt； boat.churchMan == boatState[j]。 Priest)

Continue;

}

Break; //This operation is feasible, and the cycle is deduced, and only the current optimal node is found.

}

}

if(j & lt； 5)

{

pQuest-& gt； boat.wildMan = boatState[j]。 Wildman;

pQuest-& gt； boat.churchMan = boatState[j]。 Priests;

Return TRUE

}

}

Returns FALSE

}

Trackback: /TrackBack.aspx？ PostId=2 1630

[Click here to collect this article] published on April 7th, 2004 at 2: 18.

No comment.

comment

Name:

Please enter your name.

Website:

Verification Code

comment

Please enter a comment.

Remember me?

-

Website introduction-advertising service-website map-help information-contact information-English-problem report

CSDN Beijing An Baili Meidamei Digital Technology Co., Ltd. Copyright Beijing ICP Zheng Zi No.020026 CSDN

2000-04, CSDN.NET, all rights reserved.

-

Copyright? Paddy 102 by. text