加权九尾问题可以简化为加权最短路径问题。
部分提出了九尾问题并使用 BFS 算法解决了它。本节介绍问题的变体并使用最短路径算法解决它。

九尾问题是找到导致所有硬币面朝下的最少移动次数。每一步都会翻转一枚正面硬币及其相邻硬币。加权九尾问题将翻转次数指定为每次移动的权重。例如，您可以通过翻转第一行中的第一个硬币及其相邻的两个硬币，将下图a中的硬币更改为下图b中的硬币。因此，此移动的权重为 3。通过翻转中心硬币及其四个相邻硬币，可以将下图 c 中的硬币变为下图 d。所以这个动作的权重是5.

加权九尾问题可以简化为在边加权图中寻找从起始节点到目标节点的最短路径。该图有 512 个节点。如果存在从节点 u 到节点 v 的移动，则创建从节点 v 到 u 的边。将翻转次数指定为边的权重。

回想一下，在第 1 节中，我们定义了一个类 NineTailModel 来建模九尾问题。我们现在定义一个名为WeightedNineTailModel的新类，它扩展了NineTailModel，如下图所示。

NineTailModel类创建一个Graph并获得一个以目标节点511为根的Tree。 WeightedNineTailModel 与 NineTailModel 相同，只不过它创建了一个 WeightedGraph 并获取了一个以目标节点为根的 ShortestPathTree 511。 WeightedNineTailModel 扩展了 NineTailModel。方法 getEdges() 查找图中的所有边。 getNumberOfFlips(int u, int v) 方法返回从节点 u 到节点 v 的翻转次数。 getNumberOfFlips(int u) 方法返回从节点 u 到目标节点的翻转次数。

下面的代码实现了WeightedNineTailModel.

package demo;
import java.util.*;

public class WeightedNineTailModel extends NineTailModel {
    /** Construct a model */
    public WeightedNineTailModel() {
        // Create edges
        List edges = getEdges();

        // Create a graph
        WeightedGraph graph = new WeightedGraph(edges, NUMBER_OF_NODES);

        // Obtain a shortest path tree rooted at the target node
        tree = graph.getShortestPath(511);
    }

    /** Create all edges for the graph */
    private List getEdges() {
        // Store edges
        List edges = new ArrayList();

        for(int u = 0; u .ShortestPathTree)tree).getCost(u);
    }
}

WeightedNineTailModel 扩展 NineTailModel 来构建 WeightedGraph 来建模加权九尾问题（第 10-11 行）。对于每个节点 u，getEdges() 方法查找翻转节点 v 并将翻转次数指定为边的权重 (v, u)（第 30 行）。 getNumberOfFlips(int u, int v) 方法返回从节点 u 到节点 v 的翻转次数（第 38-47 行）。翻转次数是
之间不同单元格的数量 两个节点（第 44 行）。

WeightedNineTailModel 获得以目标节点 511 为根的 ShortestPathTree（第 14 行）。请注意，tree 是 NineTailModel 中定义的受保护数据字段，ShortestPathTree 是 Tree 的子类。 NineTailModel 中定义的方法使用 tree 属性。

getNumberOfFlips(int u)方法（第49-52行）返回从节点u到目标节点的翻转次数，即从节点开始的路径成本u 到目标节点。该成本可以通过调用 ShortestPathTree 类中定义的 getCost(u) 方法获得（第 51 行）。

下面的代码给出了一个程序，提示用户输入一个初始节点，并显示到达目标节点的最少翻转次数。

打包演示； 导入java.util.Scanner； 公共类WeightedNineTail { 公共静态无效主（字符串[] args）{ // 提示用户输入九个币的Hs和Ts System.out.print("请输入最初的九个硬币Hs和Ts："); 扫描仪输入 = new Scanner(System.in); String s = input.nextLine(); char[] 初始节点 = s.toCharArray(); WeightedNineTailModel 模型 = new WeightedNineTailModel(); java.util.List path = model.getShortestPath(NineTailModel.getIndex(initialNode)); System.out.println("抛硬币的步骤是"); for (int i = 0; i package demo; import java.util.Scanner; public class WeightedNineTail { 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(); WeightedNineTailModel model = new WeightedNineTailModel(); java.util.List path = model.getShortestPath(NineTailModel.getIndex(initialNode)); System.out.println("The steps to flip the coins are "); for (int i = 0; i 输入最初的九个硬币 Hs 和 Ts：HHHTTTHHH

抛硬币的步骤是

哈哈哈

TT
呵呵

哈哈哈

THT
TT

TTT

TT
TT

翻转次数为8

程序在第8行提示用户输入由

H和T组成的9个字母组成的初始节点作为字符串，从字符串（第 9 行），创建模型（第 11 行），获取从初始节点到目标节点的最短路径（第 12-13 行），显示路径中的节点（第16–17)，并调用 getNumberOfFlips 获取到达目标节点所需的翻转次数（第 20 行）。