在树的罗马统治数字

Question

我正在尝试在 this paper 第 61-66 页的树中实现罗马统治数的线性算法。它几乎可以工作但是对于下图它 returns 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

TL;DR

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

你可以通过

解决

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

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

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

详情

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

的新参数

我假设您的输入是 adjacency matrix. If that's not correct - what follows will be nonsense - please advise in comments. I'm going to further assume that I don't have to check for loops or anything - so will not consider how that might affect what you're doing (if you need to do these checks programatically - there are 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]

这是正确的 "shape" 树，但节点没有按照 DFS 的正确顺序标记（特别是中间的 "leg" 从下往上编号）。

如果您通过简单地插入

来模拟 parent 的正确值

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

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

在树的罗马统治数字

Roman domination number in a tree

java

tree

graph

更正

TL;DR

详情

评论