Apply both breadth-first search and best-first search to a modified version of MC problem. In the modified MC, a state can contain any number of M’s and any number of C’s on either side of the river. Assume the goal is always to move all the persons on the left side to the right side. The Initial state should be a parameter given to the program at beginning of execution. As in the original problem, boat capacity =2, the boat cannot move by itself, and on either side C’s should not outnumber M’s. For best-first
Using c++
Apply both breadth-first search and best-first search to a modified version of MC problem. In the modified MC, a state can contain any number of M’s and any number of C’s on either side of the river. Assume the goal is always to move all the persons on the left side to the right side. The Initial state should be a parameter given to the program at beginning of execution. As in the original problem, boat capacity =2, the boat cannot move by itself, and on either side C’s should not outnumber M’s. For best-first search, you need to come up with an appropriate heuristic. In addition to solving the problem, your grade will also be based on th effectiveness of the heuristic.
As an example, the program should execute as follows.
Initial state…
Enter number of M’s on left side of the river: 3
Enter number of C’s on left side of the river: 1
Enter number of M’s on right side of the river: 0
Enter number of C’s on right side of the river: 0
Enter location of the boat: L
The output should contain the solution obtained by breadth-first and best-first algorithms. In addition, the output should contain number of states expanded by each
Breadth-first solution
MM->
M<-
MM->
M<-
MC->
Number of states expanded using breadth-first= …
Best-first solution
…
Number of states expanded using best-first= …
Step by step
Solved in 2 steps
