Hello
For the lecture of data structure and algorithm,
we continue the study of stack and queue
We introduce an application of queue today.
When solving the problem,
we provide with an example of the farmer crossing the river
农夫带着狼羊菜 The farmer takes wolf, sheep and vegetables.
From a side to another.
When he crosses the river by boat,
he can take only one passenger.
When he is not there,
golf and sheep, sheep and vegetable
can not stay together alone.
From the aspect of start side,
I list the ten reasonable
status of start side.
Then
the farmer takes a thing
or nothing
from a side to a nother
and from the connections between
these status.
In this solving process,
we start from the start node
of man, sheep, wolf and vegetable
to the end when they goes to the other side,
while the start node
is empty.
To find such reachable path.
In chapter 7 graph,
we introduce the shortest
Dijkstra algorithm
to solve this problem.
We change an aspect to think of the problem.
we can use a bit vector
to express man, sheep, wolf, vegetable.
whether they are at the start side or the other.
It is 0 at the start side,
and 1 at the other one.
So that
we goes from the initialized 0000
such a status
through some transference
to the status of 1111
such a goal.
For such a status transfer space
how do we
solve the problem.
In general, we have two methods.
The first is depth-first search.
like the Queen Problem.
When I put a queen in the first line,
I look at a position at the second line
to see whether I can put it there.
If so,
we continue to the third line.
If not,
I change to another position.
If at a line,
there is no position to put.
Then I go back to the last line.
to see if I can change the position.
If not,
we goes back level by level.
until the first line, maybe.
to change the position.
This process
is depth-first.
If we look at the status space,
it starts from a node
along a branch
and goes down.
until the end.
Then I change the position in the same level.
If I can not change at this level,
I go up back.
And find another status there.
This is a method of depth-first.
We can use stack to realize it.
Or use a stack.
Here, we
introduce a method of width-first search.
The width-first search
is that I put every status at the top
into a queue.
Then
we push a node from the front of the node.
For the next node
the probable transfer status
I set it.
and put it at the back of the queue.
I solve the problem
from top to down.
We come back to the problem of Farmer Crossing River.
To describe the problem
is to set up the status.
Then we know
our problem is from 0000 to 1111.
such a solving problem.
The description of our data
is very straight-forward.
I use a bit vector to express
all possible status.
the 0 and 1 in the vector
represents start side and another.
Then the four thing
has its fixed position.
The vector
has four bits.
The value
has 16 possibilities in total.
But some is illegal.
We get rid of such illegal status.
to find ten legal status.
We can save the bit vector
in an integer.
because the integer can do bit operation.
For example, the status of the farmer at the other side
and others at the start side
is
1000
Of course, this is illegal.
Because without him,
wolf and sheep, sheep and vegetable
has a conflict.
The target side is expressed as 1111.
After this
I can describe the whole solving process
the transfer of status.
Another important issue,
for such a bot vector
how do I judge a specific thing
is at this side or another.
We will do some bit operation.
For example, for the farmer,
he is in the highest bit.
We use 1000
with the bit vector of status
to do an And operation.
If the farmer is at the target side.
Its corresponding bit
will be 1.
the result of And operation
must not be zero
then returns true.
If the bit of farmer is 0,
which means he is at the start side.
Then the result of And operation
with 1000
because the 100's
first to third position is all 0
the result must also be 0.
So if the bit of farmer is also 0,
the result of And is entirely 0.
Then we can judge
that the farmer is at the start side.
It is the same as the other things.
We use such a feature of the corresponding bit
with the current status
to do an And operation.
Besides, we should also make sure
whether the status is safe.
If sheep and vegetable
are at the same side
and the farmer is not at this side,
this is not safe and returns false.
If sheep and wolf are at the same side
and the farmer is not at this side,
it also returns false.
Other status return true.
Let us clear up
the requirement of this algorithm.
We start with
the status of 0000
to the end status of 1111.
In the sequence of the solution,
there can not be duplicate status.
Because duplicate is meaningless.
After duplication,
the next segment
can have another round.
It's only useless operation.
If you can not control
duplication well,
it is probable that
the algorithm will fall into dead cycle.
The transfer process of the status
are all in the way the farmer takes a thing
from a side to another.
Or he goes alone.
We also use some auxiliary data structure
to help farmer realize the transport process.
The most important is queue.
The queue needs to save the space status
of current search.
We also need to define
the path that we have visited.
To define the path,
we mainly record
whether the status
has been visited.
If not,
we can go into this status.
Meantime, we can set the precursor of this status
as the previous one just now.
To record the path of the status,
the variable
is an array.
The array
is corresponding to the 16
possible status.
We set the initial value as -1.
The value of it,
is in the process of search
from the previous status
to the current one.
The precursor of it
is what we record
As for implementation of the algorithm,
we first define some variables.
And set the array for path
as -1.
That is, all such status
have not been visited.
Then we can set the start status as
0000
and push it into queue.
Meantime, we set the 0 position
corresponding to the start status
We set its precursor as 0.
It mainly differs from the -1 status
that it has not been visited.
Let us look at the main frame.
Now, the head of the queue
is the start node of the entire space.
That is, 0000.
Then we enter into a cycle.
When the queue is not empty
and the goal status has not appeared.
We pop a node
from the head of the queue.
Then we try to take one of these things
or nothing.
We let the variable mover
change from 1
We have a try of the choice below
which is
1 2 4 8
corresponding to the start variable 0001
move left by a bit
into 0010
by another bit
into 0100
by the last bit
into 1000
corresponding to sheep, vegetable and wolf man.
For the feature bit of these things,
the previous three is the farmer taking some things
the last 1000
is that the farmer takes nothing.
He rows the empty boat
from a side to another.
In each cycle,
we first make sure
whether the farmer and the thing he is going to take
are at the same side.
For example, the start status
0000
the farmer wants to take sheep
You see, the feature bits of farmer
and sheep
are equal
so he can take it.
Then
we go into another status.
we have an Or operation
of the feature bits of farmer
and the thing he takes.
And I get a new vector.
This vector
does an XOR operation
with the status ahead
the status just now is 0000
the XOR operation
bit by bit
is that the farmer and the thing he takes
change
from 0
to 1
If it is originally 1
it becomes 0
Another two things
will not change.
That is,
we change from an old status
into
a new one
Then we consider whether the new status
is safe.
And let us see whether the new status
its path
has been visited.
That is, whether this status
is in the path of
a solution
If not,
I can accept
this new status.
We record it into
a temporary array
of the path.
And its precursor
is set as the status just now.
And put the new status
into the queue.
To extend
for width-first search afterwards
The main framework is
that we continue to
pop the node
of the queue
and do corresponding operations
until the queue is empty
or the target status
appears
If this problem can get a solution
we take route[15]
such a precursor
and find its precursor one after one
until route0
Then we get an inverted sequence of a solution
if we reverse this sequence
it is a correct solution.
If until finished
the main algorithm framework just now
has not got a reasonable solution of route[15]
at this time
we can not solve this problem
then return failure.
Let us observe
the solving process of this algorithm.
In fact, from the start status
when we try to extend it
only to find
there is only one choice
the other two
is conflicting.
From the start status
to the next status
we choose sheep
that is, there are two bits
changed
the two left do not change.
then we change into the next status.
only the farmer change
others do not.
We from top to down
save such reasonabl status
into our queue layer by layer.
And wait for the extend of the next layer
At last,
we meet the solution status.
the process of solution complete.
At last, a little game is give to you.
on a dark night,
there is a family of five carrying a lamp
across a single log
The five
cross at different speeds.
And only two is allowed
to cross the log at the same time
to the other side.
and take the lamp back
to take people this side
the duration of the lamp
is pretty short
how do we design a scheme
for the five to cross the log.
Thank you.