九尾问题可以简化为最短路径问题。

九尾问题如下。九枚硬币被放置在一个三乘三的矩阵中，一些面朝上，一些面朝下。合法的举动是取出一枚正面朝上的硬币，并将其连同与其相邻的硬币一起翻转（这不包括对角相邻的硬币）。您的任务是找到导致所有硬币面朝下的最少移动次数。例如，从九个硬币开始，如下图（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.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 

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

为根的bfs树（第17行）。

为了创建边，

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

getindex(node)

getnode(index) 方法返回一个由字母 h 和 t 组成的节点（第 74-87 行）。

getshortestpath(nodeindex)

getpath(nodeindex)
获取从指定节点到目标节点的最短路径中的顶点的方法
（第 89-91 行）.

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

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

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 path = model.getShortestPath(NineTailModel.getIndex(initialNode));

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

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

          

        登录后复制以上就是案例研究：九尾问题的详细内容，更多请关注php中文网其它相关文章！