案例研究：九尾问题

九尾问题可以简化为最短路径问题。
九尾问题如下。九枚硬币被放置在一个三乘三的矩阵中，一些面朝上，一些面朝下。合法的举动是取出一枚正面朝上的硬币，并将其连同与其相邻的硬币一起翻转（这不包括对角相邻的硬币）。您的任务是找到导致所有硬币面朝下的最少移动次数。例如，从九个硬币开始，如下图（a）所示。当你翻转最后一排的第二枚硬币后，九枚硬币现在如下图（b）所示。翻转第一排第二枚硬币后，九枚硬币全部面朝下，如下图(c)所示。

我们将编写一个程序，提示用户输入九个硬币的初始状态并显示解决方案，如下面的示例运行所示。

输入前九个硬币hs和ts：hhhttthhh
抛硬币的步骤是
哈哈哈
tt
哈哈哈
哈哈哈
tht
tt
tt
tt
tt

九个硬币的每个状态代表图中的一个节点。例如，上图中的三个状态对应图中的三个节点。为了方便起见，我们使用 3 * 3 矩阵来表示所有节点，并使用 0 表示头部，1 表示尾部。由于有 9 个单元，每个单元要么是 0 要么是 1，所以总共有 2^9 (512) 个节点，标记为 0、1、 。 。 。 、511，如下图

如果存在从u到v的合法移动，我们将从节点v分配一条边到u。下图显示了部分图表。请注意，从511到47有一条边，因为您可以翻转节点47中的单元格以成为节点511。

下图中最后一个节点代表九个面朝下的硬币的状态。为了方便起见，我们将最后一个节点称为目标节点。因此，目标节点被标记为511。假设九尾问题的初始状态对应节点s。问题简化为寻找从节点s到目标节点的最短路径，相当于在以目标节点为根的bfs树中寻找从节点s到目标节点的最短路径。

现在的任务是构建一个由 512 个节点组成的图，标记为0、1、2、。 。 。 ，511，以及节点之间的边。创建图后，获取以节点511为根的 bfs 树。从bfs树中，你可以找到从根到任意顶点的最短路径。我们将创建一个名为ninetailmodel的类，其中包含获取从目标节点到任何其他节点的最短路径的方法。类uml图如下图所示。

在视觉上，节点以字母 h 和 t 的 3 * 3 矩阵表示。在我们的程序中，我们使用九个字符的一维数组来表示一个节点。例如，下图中顶点 1 的节点表示为 {'h', 'h', 'h', 'h', 'h', 'h ', 'h', 'h', 't'} 在数组中。

getedges() 方法返回edge 对象的列表。

getnode(index) 方法返回指定索引的节点。例如，getnode(0) 返回包含 9 个 h 的节点。 getnode(511) 返回包含 9 个 t 的节点。 getindex(node) 方法返回节点的索引。

请注意，数据字段tree被定义为受保护，以便可以从weightedninetail子类访问它。

getflippednode(char[] node, intposition)方法翻转指定位置及其相邻位置的节点。该方法返回新节点的索引。

position是

0到8之间的值，指向节点中的一枚币，如下图

例如下图中的节点

56，在0位置翻转，就会得到节点51。如果你在位置1翻转节点56，你将得到节点47.

flipacell(char[] node, int row, int column)

方法翻转指定行和列处的节点。例如，如果翻转第 0 行 0 处的节点 56，则新节点为 408。如果翻转行2和列0的节点56，新节点是30.下面的代码展示了 ninetailmodel.java 的源代码。

import java.util.*;

public class ninetailmodel {
    public final static int number_of_nodes = 512;
    protected abstractgraph<integer>.tree tree; // define a tree

    /** construct a model */
    public ninetailmodel() {
        // create edges
        list<abstractgraph.edge> edges = getedges();

        // create a graph
        unweightedgraph<integer> graph = new unweightedgraph(edges, number_of_nodes);

        // obtain a bsf tree rooted at the target node
        tree = graph.bfs(511);
    }

    /** create all edges for the graph */
    private list<abstractgraph.edge> getedges() {
        list<abstractgraph.edge> edges = new arraylist(); // store edges

        for (int u = 0; u = 0 &amp;&amp; row = 0 &amp;&amp; column  getshortestpath(int nodeindex) {
        return tree.getpath(nodeindex);
    }

    public static void printnode(char[] node) {
        for (int i = 0; i 



<br>构造函数（第 8-18 行）创建一个包含 512 个节点的图，每条边对应于从一个节点到另一个节点的移动（第 10 行）。从图中，得到一棵以目标节点511<p>为根的bfs树（第17行）。<strong>

</strong>为了创建边，</p>getedges<p>方法（第21-37行）检查每个节点<strong>u</strong>以查看它是否可以翻转到另一个节点<strong>v</strong>。如果是这样，请将 (<strong>v</strong>, <strong>u</strong>) 添加到 <strong>edge</strong> 列表（第 31 行）。 <strong>getflippednode(node,position)</strong> 方法通过翻转节点中的 <strong>h</strong> 单元及其邻居来查找翻转节点（第 43-47 行）。 <strong>flipacell(node, row, column)</strong> 方法实际上翻转节点中的 <strong>h</strong> 单元格及其邻居（第 52-60 行）。<strong>

</strong>getindex(node)</p>方法的实现方式与将二进制数转换为十进制数相同（第62-72行）。 <p>getnode(index)<strong> 方法返回一个由字母 </strong>h<strong> 和 </strong>t<strong> 组成的节点（第 74-87 行）。</strong>

<strong></strong>getshortestpath(nodeindex)</p> 方法调用 <p>getpath(nodeindex)<strong></strong>
获取从指定节点到目标节点的最短路径中的顶点的方法<strong>
（第 89-91 行）.</strong>

<br>printnode(node)<br> 方法在控制台上显示一个节点（第 93-101 行）。</p>

<p>下面的代码给出了一个程序，提示用户输入初始节点并显示到达目标节点的步骤。<strong>
</strong>

</p>
<pre class="brush:php;toolbar:false">import java.util.Scanner;

public class NineTail {

    public static void main(String[] args) {
        // Prompt the user to enter nine coins' Hs and Ts
        System.out.print("Enter the initial nine coins Hs and Ts: ");
        Scanner input = new Scanner(System.in);
        String s = input.nextLine();
        char[] initialNode = s.toCharArray();

        NineTailModel model = new NineTailModel();
        java.util.List<integer> path = model.getShortestPath(NineTailModel.getIndex(initialNode));

        System.out.println("The steps to flip the coins are ");
        for (int i = 0; i 



程序在第 8 行提示用户输入由 9 个字母组成的初始节点，并以 <p>h<br>s 和 </p>t<p>s 的组合作为字符串，从字符串中获取字符数组（第 9 行），创建一个图形模型获取bfs树（第11行），获取从初始节点到<strong>的最短路径
目标节点（第 12-13 行），并显示路径中的节点（第 16-18 行）。</strong>


          <strong>

            
        </strong></p></integer>

登录后复制

以上就是案例研究：九尾问题的详细内容，更多请关注其它相关文章！

Tags： 节点硬币