algorithm - 查找可以为我的所有项目提供服务的最小节点数

Question

我有一些商店和一些商品，我想从最少数量的商店中运送所有商品。

例如:

我有 3 家商店(s1、s2、s3)和 4 件商品(p1、p2、p3、p4)。

这些商店有我的元素集的任何子集。

对于考试。

s1 有 (p1,p3);

s2 有 (p2,p4);

s3 有 (p2,p3,p4);

所以可以提供我所有商品的最小商店是:

(s1,s3).

我用蛮力检查了所有可能的商店组合并找到了最小值。但这要花很多时间。

public static void main(String[] args) {

    Map<String, Set<String>> buckets = new HashMap<>();
    buckets.putIfAbsent("s1", new HashSet<>());
    buckets.putIfAbsent("s2", new HashSet<>());
    buckets.putIfAbsent("s3", new HashSet<>());
    buckets.get("s1").add("p1");
    buckets.get("s1").add("p3");

    buckets.get("s2").add("p2");
    buckets.get("s2").add("p4");

    buckets.get("s3").add("p2");
    buckets.get("s3").add("p3");
    buckets.get("s3").add("p4");

    Set<String> allsku = new HashSet<>();
    for (String node : buckets.keySet()) {
        allsku.addAll(buckets.get(node));
    }

    Long val = System.currentTimeMillis();
    Set<String> result = getBestCmnm(buckets, new HashSet<>(), allsku);
    System.out.println(result + " " + (System.currentTimeMillis() - val));
}


static Set<String> getBestCmnm(Map<String, Set<String>> buckets, Set<String> choosedNode, Set<String> remainingSku) {
    if (remainingSku.size() == 0) {
        return choosedNode;
    }
    Set<String> result = new HashSet<>();
    Set<String> presentNode = new HashSet<>(buckets.keySet());
    presentNode.removeAll(choosedNode);
    int min = Integer.MAX_VALUE;
    for (String node : presentNode) {
        if (containAny(buckets.get(node), remainingSku)) {
            Set<String> choosedNode1 = new HashSet<>(choosedNode);
            choosedNode1.add(node);
            Set<String> remainingSku1 = new HashSet<>(remainingSku);
            remainingSku1.removeAll(buckets.get(node));
            Set<String> val = getBestCmnm(buckets, choosedNode1, remainingSku1);
            if (val.size() < min) {
                min = val.size();
                result = val;
            }
        }
    }
    return result;
}

private static boolean containAny(Set<String> from, Set<String> to) {
    for (String f : to) {
        if (from.contains(f)) {
            return true;
        }
    }
    return false;
}

Answer 1

这是 set cover problem ，同构于“顶点覆盖问题”。我见过的所有解决方案都使用矩阵表示哪些集合涵盖哪些项目:

     p1  p2  p3  p4
s1   x   -   x   -
s2   -   x   -   x
s3   -   x   x   x

首先，请注意您的情况有两个最佳解决方案:(s1, s2) 和(s1, s3)。如果您有一个额外的优化来最小化所有集合大小的总和(作为多个最小集合计数解决方案之间的决胜局)，那么您有一个更大的问题需要解决。

当您扫描解决方案时，请注意“贪心算法”。它是最容易解释的，具有很好的算法复杂性，并给出了很好的近似值——但要证明它是次优的是微不足道的。

“贪婪”是通过选择涵盖最多产品的集合来衡量的。然后，您从问题空间中删除该集合和那些产品，并重新解决剩余的问题。

在您的情况下，这是微不足道的:s3 涵盖最多 -- 3 种产品。您将 s3 放入解决方案集中，从需求中删除 p2 p3 p4，现在剩下一个 2x1 矩阵:

    p1
s1   x
s2   -

这给出了解决方案 {s1, s3}。

---

预处理

对于您获得的任何输入，请确保通过一些简单的预处理来减小问题的大小。除非您还需要二次优化(最小计数)，否则寻找子集:删除属于另一个子集的任何集合。

最重要的是，在每个阶段，您(作为解决方案的一部分)获取作为任何产品的唯一提供者的任何集合。在您发布的示例中，您会立即将 s1 放入解决方案中，因为它是 p1 的唯一提供者。这也会从问题空间中删除 p3，留下

    p2  p4
s2   x   x
s3   x   x

...并且任一供应商都解决了问题。

---

一旦达到每个剩余产品的多个供应商点，您就进入启发式区域。我一直无法找到一个非常好的解决方案的引用资料；它使用智能回溯。

计算每种产品的供应商数量并找到最小值。在此最小集合中选择一个产品。遍历此产品的供应商(按贪婪顺序排序会有所帮助)并依次选择每个供应商作为此产品的供应商。从问题空间中移除供应商和产品并重现。

深度优先。跟踪迄今为止找到的最佳解决方案；将其作为回溯中的参数传递，因此您还可以砍掉任何不等于现有解决方案深度的分支。

---

我希望这能让您朝着好的解决方案迈进。