java - 如何在给定图中快速计算n个非重叠顶点对中的一个不会在边上的概率

Question

我有 45 个顶点的图，我想计算如果我采用 n 个随机非重叠对，其中一个不会在边缘上的概率。当我说非重叠对时，我的意思是它们不共享任何顶点。

例如，使用 n == 2，并使用此图：

左上顶点被选中的概率是 4/5，那么如果他被选中，它与右上顶点成对的概率是 1/4。

所以结果应该是 (4/5)*(1-1/4)=0.6

我能想到的最快方法是检测哪个顶点的邻居最少，并对这个顶点进行递归。

这是我写的代码（在java中）

public class TwinNeighbor {
    public static double get(byte[][] neighborsArr, int pairAmount) {
        return getRec(neighborsArr, pairAmount, new boolean[neighborsArr.length]);
    }

    private static double getRec(byte[][] neighborsArr, int pairAmount, boolean[] deleted) {
        int deleteAmount = total(deleted);
        if (pairAmount == 0)
            return 1;
        if (pairAmount * 2 > neighborsArr.length - deleteAmount)
            return 0;

        int index = getIndexWithLeastNeighbors(neighborsArr, deleted);
        double total = 0;
        deleted[index] = true;
        for (byte neighbor : neighborsArr[index]) {
            if (deleted[neighbor])
                continue;
            deleted[neighbor] = true;
            total += getRec(neighborsArr, pairAmount - 1, deleted);
            deleted[neighbor] = false;
        }
        double probabilityIfSelected = total / (neighborsArr.length - deleteAmount - 1);
        double probabilityIfNotSelected = getRec(neighborsArr, pairAmount, deleted);
        deleted[index] = false;

        double probabilitySelectCard = (double) pairAmount * 2 / (neighborsArr.length - deleteAmount);
        return probabilitySelectCard * probabilityIfSelected + (1 - probabilitySelectCard) * probabilityIfNotSelected;
    }

    private static int total(boolean[] arr) {
        int total = 0;
        for (boolean b : arr)
            if (b)
                total++;
        return total;
    }

    private static int getIndexWithLeastNeighbors(byte[][] neighborsArr, boolean[] deleted) {
        int minNeighborsAmount = neighborsArr.length;
        int minNeighborsIndex = -1;
        for (int i = 0; i < neighborsArr.length; i++) {
            if (deleted[i])
                continue;
            int neighborsAmount = 0;
            for (byte neighbor : neighborsArr[i])
                if (!deleted[neighbor])
                    neighborsAmount++;
            if (neighborsAmount < minNeighborsAmount) {
                minNeighborsAmount = neighborsAmount;
                minNeighborsIndex = i;
            }
        }
        return minNeighborsIndex;
    }
}

public static void main(String[] args) {
    System.out.println(1 - TwinNeighbor.get(new byte[][] {
            {1},
            {0,2,3,4},
            {1,3,4},
            {1,2,4},
            {1,2,3}
    }, 2));//prints 0.6000000000000001
}

有什么方法可以让我的代码运行得更快吗？

编辑：

如果 n 很小，有没有办法让它更快？(n <= 6, |V| = 45)

标签： javaalgorithmoptimizationprobabilitygraph-theory

Answer 1

不幸的是，n = |V|/2 的特殊情况相当于计算完美匹配的数量，这是一个#P-hard 问题，所以除非出现奇迹，否则你会被指数时间算法困住。

您可以通过记住每个（诱导子图，n'）对的结果来获得 O(n |V| 2 ^|V| ) 时间算法，其中 n' ≤ n。这对 |V| 来说很昂贵 = 45 但并非不可能，特别是如果 n 很小并且您只需评估缺少 ≤ 2n 个顶点的子图。