问题是：

汤米有一个大小为 N 的方形房子，分为几个单元，他想在房子周围放置传感器检测设备以确保安全。每个传感器可以从它放置的位置检测多达 K 步数。屋内有M个位置是杆子，传感器无法通过它检测到。他计划最多放置 5 台设备，并想知道如何使用最少数量的设备来覆盖整个房子。

让我们像下面这样可视化示例（= 是空单元，o 是极单元）

=====

哦==

=====

=ooo=

=====

如果他将设备 (D) 放在位置 (3, 4)，设备覆盖范围将如下所示（每个单元格内的数字表示来自设备的实例）

==323

ooo12

321D1

=ooo2

====3

我的问题是：

有没有解决这个问题的最佳解决方案？

我已经搜索并阅读了一些关于 Set Cover, Exact Cover 问题的文章，但找不到解决上述问题的方法。

我有一个套装封面问题要解决我希望将套装名称返回给我的地方。我认为存储命名集的好方法是在字典中。我发现这个实现算法但使用集合列表的博客，我正在尝试修改代码以适应字典。

这将集合作为列表返回：

IE

但不是名字。

为了获得名称，我不能使用集合的值来识别名称，因为在我的实际数据中，一些子集可能是相同的（我猜在这种情况下两者都可以）。无论如何，我想要一个返回每个选定集合名称的解决方案。

我想这必须通过修改subset = max(subsets.values(), key=lambda s: len(s - covered))行来实现，但我不确定如何在保留算法集的同时获取从此操作中选择的集的名称。我怎样才能做到这一点？

期望的输出：

我通常不会就 SO 提出问题，所以如果这个问题似乎不适合 SO，请告诉我（当然，我们仍然会感谢您的帮助）。

我还是一名学生，目前正在学习算法课程。我们最近了解了分支定界范式，由于我没有完全理解它，所以我尝试在我们的课本中做一些练习。我遇到了一个特殊的 Set Cover 问题实例：

令 U 是一组元素，S = {S1, S2, ..., Sn} 是 U 的一组子集，其中所有集合 Si 的并集等于 U。概述分支定界算法以找到最小S 的子集 Q，因此对于 U 中的所有元素 u，Q 中至少有两个集合，其中包含 u。具体来说，详细说明如何将问题分解为子问题以及如何计算上限和下限。

我的第一个想法是按降序对 S 中的所有集合 Si 进行排序，根据它们包含的元素数量，这些元素还没有被当前选择的 S 的子集覆盖至少两次，所以我们当前的 Q 实例。考虑递归解决这个问题，我按排序顺序选择第一个集合 Si 并进行一次递归调用，在其中我取这个集合 Si 和一个我没有的地方（意味着从那些递归调用开始，不再考虑子集） . 如果我选择它，我将遍历这个所选子集 Si 中的每个元素并为其所有元素增加一个计数器（在递归调用之前），这样我最终会知道，当一个元素已经被两个或更多选择的元素覆盖时子集。由于我为每个递归调用对未选择的集合 Si 进行排序，理论上（至少在我看来）我会一直做出目前最好的选择。而且由于我基本上创建了递归调用的二叉树，因为我总是使用当前选择的最佳子集进行一次调用，而我最终会覆盖所有 2^n 的可能性，这意味着最终我会找到最佳的解决方案。

我现在的问题是我不知道或者更确切地说我将如何实现上限和下限的启发式算法，因此算法可以丢弃二叉树中的一些路径，这永远不会比当前最好的 Q 更好。将不胜感激我能得到的任何帮助。

有一组需要涵盖的项目。这些项目的子集是可用的。如果我们要求覆盖整个项目的这些子集的最小数量，那么问题就是众所周知的 Set Cover 问题。用最小解来表示 Set Cover 问题的解。但是，我们有一个解决方案，其中项目的子集涵盖所有项目，并且此解决方案中的每个子集分别涵盖某些特定项目。让我们将此解决方案称为最小解决方案。我需要找出我们如何从最小解决方案中找到最小解决方案？执行此操作的最佳近似因子是什么？

问候，

我有这个问题需要解决：

输入：

• 城市之间的路线列表，所有路线都将从同一个起点开始
• 集所有城市

输出：

• 可以访问所有城市的路径组，如果没有找到则返回组以最少的路线覆盖大部分城市。

示例：

测试用例 1：

输入

• 路线清单：

  1. Newyork -> Washington -> Los Angeles -> Chicago
  2. Newyork -> Houston -> Alaska
  3. Newyork -> Dallas
  4. Newyork -> Houston -> Washington -> Chicago -> Los Angeles -> Alaska
  5. Newyork -> Alaska
  6. Newyork -> Chicago
  7.Newyork -> Los Angeles

• 城市：Newyork, Washington, Los Angeles, Chicago, Alaska, Dallas, Houston

输出：

1. Newyork -> Houston -> Washington -> Chicago -> Los Angeles -> Alaska
2.Newyork -> Dallas

这是最好的团体，因为只有 2 条路线它可以访问所有给定的城市

测试用例 2：

输入

• 路线清单：

  1. Newyork -> Washington -> Los Angeles -> Chicago
  2. Newyork -> Houston -> Alaska
  3. Newyork -> Dallas
  4. Newyork -> Alaska
  5. Newyork -> Chicago
  6.Newyork -> Los Angeles

• 城市：Newyork, Washington, Los Angeles, Chicago, Alaska, Dallas, Houston

输出：

1. Newyork -> Washington -> Los Angeles -> Chicago
2. Newyork -> Houston -> Alaska
3.Newyork -> Dallas

这是最好的团体，因为它有 3 条路线可以访问所有给定的城市

测试用例 3：

输入

• 路线清单：

  2. Newyork -> Houston -> Alaska
  3. Newyork -> Dallas
  4. Newyork -> Alaska
  5. Newyork -> Chicago
  6.Newyork -> Los Angeles

• 城市：Newyork, Washington, Los Angeles, Chicago, Alaska, Dallas, Houston

输出：

1. Newyork -> Houston -> Alaska
2. Newyork -> Chicago
3. Newyork -> Dallas
4.Newyork -> Los Angeles

这是最好的团体，因为有 4 条路线，它可以访问 6/7 个城市（除了Washington）

执行

那么对于我可以使用的算法有什么建议吗？

我想对一组覆盖问题（关于危险品等）进行建模，为此，我一直在使用 ILOG CPLEX。我已经定义了我需要的所有变量和集合，除了 2。

之后我尝试设置我的模型，但我的问题是我希望以下内容总结“这种危险材料（m）所需的车辆（k）”的变量。为此，从表 D[mm][kk] 开始，该表在每个地方都显示需要多少类型 k 的车辆来响应涉及 m 类型危险品的事件，我制作了 cov[mm][kk] ，这是一个二进制表，在每个地方显示是否需要车辆 k 来处理危险品 m。之后，我为该表的每一行总结了“1”的数量以及必须检查的“k”的数量。但是，例如，对于一个危险品，需要 3 种（可能的 5 种）车辆类型，根据我如何解决这个问题，我可能正确地求和 k=1 到 3，但我想要正确的求和（索引将不正确）。但，

有人可以帮我解决这个问题吗？我在想一些比需要更复杂的事情吗

我是设置覆盖问题的新手，我已经能够编写一个简单的贪心算法来解决python中的一个简单实例；

这很好用，但现在我想尝试将粒子群优化等优化算法应用于问题，但我无法将问题表述为算法（和其他启发式算法）的目标函数。请帮忙。

我正在尝试用python实现一个基本问题os Set覆盖的问题，但是纸浆一直给我错误：AttributeError：'LpAffineExpression'对象没有属性'solve'

这就是我要解决的问题

这是我的代码：