Five people need to walk from this side to the other side of a bridge at...

  

Transcribed Image Text:

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. Erne 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? 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. Erne 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 rating: 100% (QA)

There are 5 people and two sides of the bridge where they can be There is also ... View the full answer