Artificial intelligence - bridge and torch problem

Question

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?

Answer 1

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.