2
$\begingroup$

I am doing a artificial intelligence course as part of my computer science degree.

I am stuck on a question about searching. The question is a version of the Bridge and torch problem.

Five people need to walk from this side to the other side of a bridge at night. The bridge is not in a very good condition and will hold at most 3 people at a time. They discover that they only have one torch. This means that after one,two,or three people have crossed the bridge, somebody (one, two, or three people) will have to come back with the torch so that the next persons can cross safely. Each of the five people (Anna, Brett, Charles, David, and Ernest) take a different time to cross the bridge. Whenever 3 people cross they can only go as fast as the slowest person in the group. Since the torch has limited battery life they need to figure out which is the fastest way to get all 5 of them across the bridge. The times each take to get across are:

1. Anna: 5 Minutes
2. Barry: 7 Minutes
3. Charles: 1 minute
4. David: 2 minutes
5. Ernest: 9 minutes

I am asked how big the search space is of the problem. This is where I am getting stuck. There are 5 people, and two sides of the bridge where they can be. There is also a variable amount of people that can cross at a time (1-3 people).

My state representation is $\{ A, B, C, D, E \}$ representing the first letter of each person, with this being the set of people on the left side of the bridge. Hence, my goal state is $\{ \}$ - all people on the right side of the bridge.

I've also worked out the sequence of moves that leads to the optimal solution - my issue is just the size of the search space.

How do I go about calculating the size of the search space?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Before you can calculate the size of the [thing], you need to decide exactly what the [thing] is.

In this case, you've decided that the state space is the set of people on the left side of the bridge. The people on the left can be any subset of the people, so any subset of $\{A, B, C, D, E\}$. The number of subsets of an $n$-element set is a well-known fact you should recall from your discrete mathematics classes.

Note that people moving across the bridge is not part of the state: it's a transition from one state to another (also known as an action). If you included that information in the state, you'd just make the search take longer. For example, instead of having the state "$A$, $B$, and $E$ are on the left" transitioning to "$A$ and $E$ are on the left", you'd have it transition to "$A$ and $E$ are on the left and $B$ is on the bridge", which would then have no choice but to transition to "$A$ and $E$ are on the left" (and nobody is on the bridge). Adding a bunch of states that have only one successor is only going to slow down your search.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ David, thank you for your reply. The statement you made about states vs actions makes a lot of sense. So I only take the possible subsets of {A, B, C, D, E} into consideration. I've underestimated the module to be honest, so now I am slowly going over everything to make sure I understand well. $\endgroup$
    – Will777
    Feb 4, 2015 at 12:39
  • $\begingroup$ Yes, you only count the subsets of $\{A, \dots, E\}$ into account, since that's what you (sensibly and correctly) defined the states to be. $\endgroup$
    – David Richerby
    Feb 4, 2015 at 12:40
  • 1
    $\begingroup$ Thanks again David. It makes much more sense now, and to be honest, a lot of the other problems in the uninformed search chapter are starting to become clearer $\endgroup$
    – Will777
    Feb 4, 2015 at 12:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.