## 04-11 Bridge Successors

• 0:00 - 0:04
Now, out of those many choices, I made a choice to say I'm going to represent
• 0:04 - 0:09
as a tuple of (here, there, t),
• 0:09 - 0:13
where "here" represents everything that's on this side,
• 0:13 - 0:16
"there" represents everything that's on that side,
• 0:16 - 0:20
and "t" is the total elapsed time since the start.
• 0:20 - 0:26
I'm going to represent here and there with frozen sets, because those are hashable.
• 0:26 - 0:33
So this collection here would be the frozen set consisting of {1, 2, 5, 10},
• 0:33 - 0:40
and I'm going to just use the string "light" to represent the flashlight.
• 0:40 - 0:44
There would be the empty frozen set.
• 0:44 - 0:48
Now, consider this state here representing the start state.
• 0:48 - 0:50
What are the successors of that state?
• 0:50 - 0:52
Well, any one of the people could go across.
• 0:52 - 0:54
They've got to bring the light with them.
• 0:54 - 0:58
In the successor state, the light will definitely be there, and it will not be here.
• 0:58 - 1:00
It can only be in one place.
• 1:00 - 1:03
At least one of the people will be over there
• 1:03 - 1:05
and possibly two of the people,
• 1:05 - 1:09
so all combinations of sending either one person or two people to the other side,
• 1:09 - 1:12
those will each be distinct successor states.
• 1:12 - 1:18
Let's see--we've got 4 x 3 is 12, but order doesn't matter, so there's 6 of those.
• 1:18 - 1:22
Then 4 more, so it looks like there should be 10 successor states.
• 1:22 - 1:25
What I want you to do is write for me the successor function.
• 1:25 - 1:29
We're calling it bsuccessors, because we already had a and we're on to b.
• 1:29 - 1:32
Or b could stand for "bridge."
• 1:32 - 1:39
Remember that a result of the successor function is the dictionary of state action pairs.
• 1:39 - 1:42
A state is this (here, there, t) tuple.
• 1:42 - 1:45
Here and there have to be frozen sets.
• 1:45 - 1:50
The frozen sets contained people--1, 2, 5, and 10--
• 1:50 - 1:55
and/or this light, indicated by the string "light."
• 1:55 - 1:58
Show me the function that will generate all the successors.
• 1:58 - 2:05
Here I've given you a hint of here's a way to break up the state into those three variables.
• 2:05 - 2:10
• 2:10 - 2:13
Oh, one more thing I forgot is what are the actions.
• 2:13 - 2:20
Well, let's say that an action will be represented by the character string arrow going to the right
• 2:20 - 2:23
if we're moving from here to there and an arrow going to the left
• 2:23 -
if we're moving from there to here.
Title:
04-11 Bridge Successors
Description:

dummy description

more » « less
Team:
Udacity
Project:
CS212 - Design of Computer Programs
Duration:
02:27