php - 在一对多关系中至少获取一次包含所有 child 的 parent 列表

Question

我在 Report 和 Location 之间有一个一对多的关系。我的目标是将我的报告列表缩小到尽可能少的报告，其中包含所有代表的位置。

如果我将它简化为数字列表，它将如下所示，键是报告，数组是位置列表:

{
  1:[1,2],
  2:[1],
  3:[2,3],
  4:[1,3,4]
}

理想的解决方案是选择报告 1 或 3 和 4。可以选择 1 或 3，因为它们都包含位置 2 并且与 Report 重复位置 1 4。需要选择报告 4，因为它是唯一具有位置 4 的报告。

效率不是主要问题。使用 PHP 缩小列表范围的最佳方法是什么？

Answer 1

NP 完备性再次出现。

您要解决的问题称为 Set Cover , 果然是 NP-Complete .

这意味着不太可能存在“高效”(读取，多项式时间)算法。

好消息是，有一些简单的近似算法可以为您提供合适的近似值。

参见 this “明显的”贪心算法(在每个点，选择具有最多未覆盖位置的报告)如何为您提供 log (R) 近似值，其中 R 是报告的数量(实际上，它甚至比这更好)。