Consider the following puzzle. There are seven adjacent, numbered cells with three blue coins and three red coins. The blue coins (indicated by B) want to occupy cells 1, 2 and 3 while the red coins (indicated by R) want to occupy cells 5, 6 and 7. The desired state is: 1 2 B B 3 4 B 5 6 7 R R R The coins can be in any of the cells, as long as each cell is occupied by at most one coin at a time. One possible state is illustrated below and is called State A: 1 2 BR 3 4 5 B R 6 7 R B A coin is allowed to move to the adjacent cell if that cell is empty. For example, in the figure above, the red coin in cell 4 may move to cell 5. A coin may also move to an empty cell by "jumping" over an adjacent occupied cell into the empty cell two cells away. For example, in the figure above, the blue coin in cell 3 may jump over the red coin in cell 4 into cell 5. You have to find a sequence of moves that will move all six coins into the positions depicted by the desired state. The figure below depicts State B. 1 2 3 R R R 4 5 6 7 B B B 1. Formulate the task as a search problem by defining the following: a state, the goal state and the moves (actions). 2. Draw the first three levels of the state space with the initial state State A. Do not include repeating states. The root node is the first level. 3. Use the heuristic: the number of coins that are not in their correct cells as depicted by the desired state. For example, the heuristic value of start state A is 3 and of start state B is 6. Indicate the heuristic value for each state in your drawing for question 2. Show the values on the same drawing, i.e. you do not need to redraw the partial state space.

Operations Research : Applications and Algorithms
4th Edition
ISBN:9780534380588
Author:Wayne L. Winston
Publisher:Wayne L. Winston
Chapter17: Markov Chains
Section: Chapter Questions
Problem 12RP
icon
Related questions
Question

Please answer questions from number 1 to 3 if these questions in the image provided below(NOTE: THESE QUESTIONS ARE NOT GRADED!)

Consider the following puzzle. There are seven adjacent, numbered cells with three blue coins
and three red coins. The blue coins (indicated by B) want to occupy cells 1, 2 and 3 while the red
coins (indicated by R) want to occupy cells 5, 6 and 7.
The desired state is:
1
2
B B
3 4
B
5
6
7
R
R
R
The coins can be in any of the cells, as long as each cell is occupied by at most one coin at a time.
One possible state is illustrated below and is called State A:
1
2
BR
3 4 5
B R
6
7
R
B
A coin is allowed to move to the adjacent cell if that cell is empty. For example, in the figure
above, the red coin in cell 4 may move to cell 5. A coin may also move to an empty cell by
"jumping" over an adjacent occupied cell into the empty cell two cells away. For example, in the
figure above, the blue coin in cell 3 may jump over the red coin in cell 4 into cell 5.
You have to find a sequence of moves that will move all six coins into the positions depicted by
the desired state.
The figure below depicts State B.
1
2 3
R R R
4
5
6
7
B
B
B
1. Formulate the task as a search problem by defining the following: a state, the goal state and
the moves (actions).
2. Draw the first three levels of the state space with the initial state State A. Do not include
repeating states. The root node is the first level.
3. Use the heuristic: the number of coins that are not in their correct cells as depicted by the
desired state. For example, the heuristic value of start state A is 3 and of start state B is 6.
Indicate the heuristic value for each state in your drawing for question 2. Show the values on
the same drawing, i.e. you do not need to redraw the partial state space.
Transcribed Image Text:Consider the following puzzle. There are seven adjacent, numbered cells with three blue coins and three red coins. The blue coins (indicated by B) want to occupy cells 1, 2 and 3 while the red coins (indicated by R) want to occupy cells 5, 6 and 7. The desired state is: 1 2 B B 3 4 B 5 6 7 R R R The coins can be in any of the cells, as long as each cell is occupied by at most one coin at a time. One possible state is illustrated below and is called State A: 1 2 BR 3 4 5 B R 6 7 R B A coin is allowed to move to the adjacent cell if that cell is empty. For example, in the figure above, the red coin in cell 4 may move to cell 5. A coin may also move to an empty cell by "jumping" over an adjacent occupied cell into the empty cell two cells away. For example, in the figure above, the blue coin in cell 3 may jump over the red coin in cell 4 into cell 5. You have to find a sequence of moves that will move all six coins into the positions depicted by the desired state. The figure below depicts State B. 1 2 3 R R R 4 5 6 7 B B B 1. Formulate the task as a search problem by defining the following: a state, the goal state and the moves (actions). 2. Draw the first three levels of the state space with the initial state State A. Do not include repeating states. The root node is the first level. 3. Use the heuristic: the number of coins that are not in their correct cells as depicted by the desired state. For example, the heuristic value of start state A is 3 and of start state B is 6. Indicate the heuristic value for each state in your drawing for question 2. Show the values on the same drawing, i.e. you do not need to redraw the partial state space.
Expert Solution
steps

Step by step

Solved in 2 steps

Blurred answer
Recommended textbooks for you
Operations Research : Applications and Algorithms
Operations Research : Applications and Algorithms
Computer Science
ISBN:
9780534380588
Author:
Wayne L. Winston
Publisher:
Brooks Cole
C++ Programming: From Problem Analysis to Program…
C++ Programming: From Problem Analysis to Program…
Computer Science
ISBN:
9781337102087
Author:
D. S. Malik
Publisher:
Cengage Learning
C++ for Engineers and Scientists
C++ for Engineers and Scientists
Computer Science
ISBN:
9781133187844
Author:
Bronson, Gary J.
Publisher:
Course Technology Ptr
Programming Logic & Design Comprehensive
Programming Logic & Design Comprehensive
Computer Science
ISBN:
9781337669405
Author:
FARRELL
Publisher:
Cengage
LINUX+ AND LPIC-1 GDE.TO LINUX CERTIF.
LINUX+ AND LPIC-1 GDE.TO LINUX CERTIF.
Computer Science
ISBN:
9781337569798
Author:
ECKERT
Publisher:
CENGAGE L
CMPTR
CMPTR
Computer Science
ISBN:
9781337681872
Author:
PINARD
Publisher:
Cengage