案例研究：加权九尾问题

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

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

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

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

NineTailModel 类创建一个 Graph 并获取一个以目标节点 511 为根的 Tree。 WeightedNineTailModel 与 NineTailModel 相同，只不过它创建一个 WeightedGraph 并获取一个以目标节点 511ShortestPathTree 🎜>。 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<WeightedEdge> edges = getEdges();

        // Create a graph
        WeightedGraph<Integer> 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<WeightedEdge> getEdges() {
        // Store edges
        List<WeightedEdge> edges = new ArrayList<>();

        for(int u = 0; u < NUMBER_OF_NODES; u++) {
            for(int k = 0; k < 9; k++) {
                char[] node = getNode(u); // Get the node for vertex u
                if(node[k] == 'H') {
                    int v = getFlippedNode(node, k);
                    int numberOfFlips = getNumberOfFlips(u, v);

                    // Add edge (v, u) for a legal move from node u to node v
                    edges.add(new WeightedEdge(v, u, numberOfFlips));
                }
            }
        }

        return edges;
    }

    private static int getNumberOfFlips(int u, int v) {
        char[] node1 = getNode(u);
        char[] node2 = getNode(v);

        int count = 0; // Count the number of different cells
        for(int i = 0; i < node1.length; i++)
            if(node1[i] != node2[i]) count++;

        return count;
    }

    public int getNumberOfFlips(int u) {
        return (int)((WeightedGraph<Integer>.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 行）。

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

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

        System.out.println("The steps to flip the coins are ");
        for (int i = 0; i < path.size(); i++)
            NineTailModel.printNode(NineTailModel.getNode(path.get(i).intValue()));

        System.out.println("The number of flips is " +  model.getNumberOfFlips(NineTailModel.getIndex(initialNode)));
    }

}

输入最初的九个硬币 Hs 和 Ts：HHHTTTHHH

抛硬币的步骤是

哈哈哈

TTT
呵呵

哈哈哈

THT
TTT

TTT

TTT
TTT

翻转次数为8

程序在第 8 行提示用户输入一个由 9 个字母组成的初始节点，其中包含 H 和 T 的组合作为字符串，从字符串（第 9 行），创建模型（第 11 行），获取从初始节点到目标节点的最短路径（第 12-13 行），显示路径中的节点（第 16-17 行），并调用 getNumberOfFlips 获取到达目标节点所需的翻转次数（第 20 行）。

以上是案例研究：加权九尾问题的详细内容。更多信息请关注PHP中文网其他相关文章！