查找可以为我的所有项目提供服务的最小节点数
我有一些商店和一些项目，我想从最低数量的商店发货所有项目。
对于Exm：
我有3个商店(s1，s2，s3)和4个商品(p1，p2，p3，p4)。
这些商店有我的商品集的任何一个子集。
用于Exm。
具有(p1，p3)的s1；
具有(p2，p4)的s2；
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;
}回答 1
Stack Overflow用户
发布于 2019-03-29 02:19:46
这就是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..。两个供应商中的任何一个都完成了问题。
一旦你达到了每个剩余产品都有多个供应商的地步，你就进入了启发式区域。我还没有找到一个非常好的解决方案的参考资料；它使用了智能回溯。
计算每种产品的供应商数量，找出最小值。在此最小产品集中选择一种产品。遍历此产品的供应商(按贪婪的顺序排序会有所帮助)，并依次选择每个供应商作为此产品的供应商。将供应商和产品从问题空间中移除并重复出现。
先做这个深度。跟踪到目前为止找到的最佳解决方案；在回溯中将其作为参数传递，因此您还可以砍掉任何不能与现有解决方案的深度相等的分支。
我希望这能让你朝着一个好的解决方案前进。
https://stackoverflow.com/questions/55396914
复制相似问题
腾讯云开发者
