Java Reference
In-Depth Information
Enter the initial nine coins Hs and Ts: HHHTTTHHH
The steps to flip the coins are
HHH
TTT
HHH
HHH
THT
TTT
TTT
TTT
TTT
Each state of the nine coins represents a node in the graph. For example, the three states in
Figure 28.17 correspond to three nodes in the graph. For convenience, we use a 3
3 matrix to
represent all nodes and use
0
for heads and
1
for tails. Since there are nine cells and each cell is
either
0
or
1
, there are a total of 2
9
(512) nodes, labeled
0
,
1
, . . . , and
511
, as shown in Figure 28.18.
*
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
1
2
0
0
0
0
0
0
0
0
1
3
0
0
1
1
1
1
1
1
1
511
1
1
1
.....
F
IGURE
28.18
There are total of 512 nodes labeled in this order:
0
,
1
,
2
, . . . ,
511
.
We assign an edge from node
v
to
u
if there is a legal move from
u
to
v
. Figure 28.19 shows
a partial graph. Note there is an edge from
511
to
47
, since you can flip a cell in node
47
to
become node
511
.
The last node in Figure 28.18 represents the state of nine face-down coins. For convenience,
we call this last node the
target node
. Thus, the target node is labeled
511
. Suppose the initial
state of the nine tails problem corresponds to the node
s
. The problem is reduced to finding
a shortest path from node
s
to the target node, which is equivalent to finding a shortest path
from node
s
to the target node in a BFS tree rooted at the target node.
Now the task is to build a graph that consists of 512 nodes labeled
0
,
1
,
2
, . . . ,
511
, and
edges among the nodes. Once the graph is created, obtain a BFS tree rooted at node
511
. From
the BFS tree, you can find a shortest path from the root to any vertex. We will create a class
named
NineTailModel
, which contains the method to get a shortest path from the target
node to any other node. The class UML diagram is shown in Figure 28.20.
Visually, a node is represented in a 3
3 matrix with the letters
H
and
T
. In our program,
we use a single-dimensional array of nine characters to represent a node. For example, the
node for vertex
1
in Figure 28.18 is represented as {
'H'
,
'H'
,
'H'
,
'H'
,
'H'
,
'H'
,
'H'
,
'H'
,
'T'
} in the array.
The
getEdges()
method returns a list of
Edge
objects.
The
getNode(index)
method returns the node for the specified index. For example,
getNode(0)
returns the node that contains nine
H
s.
getNode(511)
returns the node that
contains nine
T
s. The
getIndex(node)
method returns the index of the node.
Note that the data field
tree
is defined as protected so that it can be accessed from the
WeightedNineTail
subclass in the next chapter.
The
getFlippedNode(char[] node, int position)
method flips the node at the
specified position and its adjacent positions. This method returns the index of the new node.
*
Search WWH ::
Custom Search