java - 在树的罗马统治数字

Question

我正在尝试在 this paper 的第 61-66 页中实现树中罗马统治数的线性算法.它几乎可以工作，但对于下图，它返回 6 而不是 8

 1 1 0 0 0 0 0 0 0 0
 1 1 1 0 0 0 0 0 0 0
 0 1 1 1 0 0 0 1 0 0
 0 0 1 1 1 0 0 0 0 0
 0 0 0 1 1 0 0 0 0 0
 0 0 0 0 0 1 1 0 0 0
 0 0 0 0 0 1 1 1 0 0
 0 0 1 0 0 0 1 1 1 0
 0 0 0 0 0 0 0 1 1 1
 0 0 0 0 0 0 0 0 1 1

谁能帮我解决这个问题。

import java.util.Arrays;

/**
 *
 * @author karo
 */
public class LinearTreeDomination {
    int n;
    int[][] Class;
    int[] Parent;
    private static final int INFINITY = Integer.MAX_VALUE/100;

    public LinearTreeDomination(int[][] graph,int vertex) {
        Class = new int[vertex+1][5];
        Parent = new int[vertex+1];
        n = vertex;
        for (int i = 1; i <= n; i++) {
            Class[i][1] = 1;
            Class[i][2] = 2;
            Class[i][3] = INFINITY;
            Class[i][4] = 0;
        }
        Parent[0] = -1;
        boolean[] bool = new boolean[vertex];
        Arrays.fill(bool, false);
        bool[0] = true;
        dfs(graph,bool,0);
        for (int i = n; i > 0; i--) {
            Parent[i] = Parent[i-1] + 1;
        }

    }

    private void dfs(int[][] graph,boolean[] visited,int index) {
        for(int i = 0 ; i < n ; i++){
            if(graph[i][index] == 1 && index != i){
                if(visited[i] == false){
                    Parent[i] = index;
                    visited[i] = true;
                    dfs(graph,visited,i);
                }
            }
        }
    }


    public int doIt(){
        for (int j = 0; j <= n-2; j++) {
            int k = Parent[n-j];
            combine(k,n-j);
        }
        return min(Class[1][1],Class[1][2],Class[1][3]);
    }


    private void combine(int a, int b) {
        int[] ClassPrim = new int[5];

        ClassPrim[1] = min(Class[a][1]+Class[b][1],Class[a][1]+Class[b][2]
                ,Class[a][1]+Class[b][3]);
        ClassPrim[2] = min(Class[a][2] + Class[b][1],Class[a][2] + Class[b][2]
                ,Class[a][2] + Class[b][3],Class[a][2] + Class[b][4]
                ,Class[a][1] + Class[b][4] + 1,Class[a][3] + Class[b][4] + 2
                ,Class[a][4] + Class[b][4] + 2);
        ClassPrim[3] = min(Class[a][3] + Class[b][1],Class[a][3] + Class[b][2]
                ,Class[a][3] + Class[b][3],Class[a][4] + Class[b][2]);
        ClassPrim[4] = min(Class[a][4] + Class[b][1],Class[a][4] + Class[b][3]);

        for (int i = 1; i <= 4; i++) {
            Class[a][i] = ClassPrim[i];
        }
    }

    private int min(int... values){
        int k = INFINITY;
        for (int val : values) {
            k = Math.min(k, val);
        }
        return k;
    }
}

---

更正

就像 J Richard Snape 所说的问题出在 dfs 方法上，dfs 用于标记顶点，而我没有初始化顶点标签。之后我们应该设置父数组。代码有点困惑和不可读我只是想找到答案。

import java.util.Arrays;

/**
 *
 * @author karo
 */
public class LinearTreeDomination {

    int n;
    int[][] Class;
    int[] Parent;
    int[] Label;
    int Y;
    private static final int INFINITY = Integer.MAX_VALUE / 100;

    public LinearTreeDomination(int[][] graph, int vertex, int from) {
        Y = 0;
        Class = new int[vertex + 1][5];
        Parent = new int[vertex + 1];
        Label = new int[vertex + 1];
        n = vertex;
        for (int i = 1; i <= n; i++) {
            Class[i][1] = 1;
            Class[i][2] = 2;
            Class[i][3] = INFINITY;
            Class[i][4] = 0;
        }
        Label[0] = 0;
        boolean[] bool = new boolean[vertex];
        Arrays.fill(bool, false);
        bool[from] = true;
        dfs(graph, bool, from);
        for (int i = n; i > 0; i--) {
            Label[i] = Label[i - 1] + 1;
        }
        Parent[1] = 0;

        for (int i = 2; i <= n; i++) {
            int counter = 0;
            for (int k = Label[i] - 1; k > 0; k--) {
                if (graph[i - 1][getIt(k) - 1] == 1) {
                    counter++;
                    Parent[Label[i]] = k;
                    break;
                }
            }
        }
    }

    private void dfs(int[][] graph, boolean[] visited, int index) {
        for (int i = 0; i < n; i++) {
            if (graph[i][index] == 1 && index != i) {
                if (visited[i] == false) {
                    Y++;
                    Label[i] = Y;
                    visited[i] = true;
                    dfs(graph, visited, i);
                }
            }
        }
    }

    public int doIt() {
        for (int j = 0; j <= n - 2; j++) {
            int k = Parent[n - j];
            combine(k, n - j);
        }
        return min(Class[1][1], Class[1][2], Class[1][3]);
    }

    private void combine(int a, int b) {
        int[] ClassPrim = new int[5];

        ClassPrim[1] = min(Class[a][1] + Class[b][1], Class[a][1] + Class[b][2], Class[a][1] + Class[b][3]);
        ClassPrim[2] = min(Class[a][2] + Class[b][1], Class[a][2] + Class[b][2], Class[a][2] + Class[b][3], Class[a][2] + Class[b][4], Class[a][1] + Class[b][4] + 1, Class[a][3] + Class[b][4] + 2, Class[a][4] + Class[b][4] + 2);
        ClassPrim[3] = min(Class[a][3] + Class[b][1], Class[a][3] + Class[b][2], Class[a][3] + Class[b][3], Class[a][4] + Class[b][2]);
        ClassPrim[4] = min(Class[a][4] + Class[b][1], Class[a][4] + Class[b][3]);

        for (int i = 1; i <= 4; i++) {
            Class[a][i] = ClassPrim[i];
        }
    }

    private int min(int... values) {
        int k = INFINITY;
        for (int val : values) {
            k = Math.min(k, val);
        }
        return k;
    }

    private int getIt(int k) {
        for (int i = 1; i <= n; i++) {
            if (Label[i] == k) {
                return i;
            }
        }
        return -1;
    }
}

Answer 1

长话短说

我认为基于 dfs() 的图形标签无法正常工作，这会导致您遇到问题。我认为你的 Parent vector 应该是 [-1, 0, 1, 2, 3, 4, 3, 6, 7, 6, 9] - 你的程序计算 [-1, 0, 1, 2, 3, 4, 3, 6, 7, 6, 9] - 这是相同的树结构，但节点以非 DFS 方式标记。

你可以解决这个问题

1. 使您的 dfs() 方法非常聪明，以便它可以检测到邻接矩阵中连接在一起的编号错误的节点，或者

2. 将邻接矩阵更改为如下所示，它具有相同的树形和相同的格式，但连接的节点编号正确

   1  1  0  0  0  0  0  0  0  0
   1  1  1  0  0  0  0  0  0  0
   0  1  1  1  0  1  0  0  0  0
   0  0  1  1  1  0  0  0  0  0
   0  0  0  1  1  0  0  0  0  0
   0  0  1  0  0  1  1  0  1  0
   0  0  0  0  0  1  1  1  0  0
   0  0  0  0  0  0  1  1  0  0
   0  0  0  0  0  1  0  0  1  1
   0  0  0  0  0  0  0  0  1  1
   

详情

仅从您的问题来看，很难看出您的矩阵输入与您链接的论文中的算法有何关系。特别是 - 在那篇论文中，树结构完全由 Parent vector 定义，但您引入了一个名为 Graph 的新参数。

我假设您的输入是 adjacency matrix .如果这不正确 - 以下内容将是无稽之谈 - 请在评论中提出建议。我将进一步假设我不必检查循环或任何东西 - 所以不会考虑这可能会如何影响你正在做的事情(如果你需要以编程方式进行这些检查 - 有 examples on the web )。但是请注意 - 因为邻接矩阵中的对角线全为 1 - 它实际上表示每个节点上都有一个循环的图。

你的邻接矩阵给出了一个看起来像这样的图:

应该这样标记:

这将使用您的索引为 [-1,0,1,2,3,4,3,6,7,6,9] 提供 Parent 值.但是，(如果您在构造函数中输出 Parent)，您会在循环之前得到它以使标签索引基于 1:

[-1, 0, 1, 2, 3, 6, 7, 2, 7, 8, 0]

之后:

[-1, 0, 1, 2, 3, 4, 7, 8, 3, 8, 9]

这是树的正确“形状”，但节点未按 DFS 的正确顺序标记(特别是中间“腿”从下往上编号)。

如果您通过简单地插入来模拟 parent 的正确值

Parent = new int[]{-1, 0, 1, 2, 3, 4, 3, 6, 7, 6, 9};

在Constructor的最后，你会得到你期待的答案(罗马统治数== 8)。这可能暗示我们走在正确的轨道上。请注意，这基本上只是调试...

评论

我可以看到您保留了基于 1 的索引以与论文对应。我认为这是个坏主意——它让 Java 很难阅读。我建议您替换为基于 0 的索引，如果我有时间，我会发布一个使用您的代码的解决方案，但使用基于 0 的索引和 dfs() 已修复。