2

这个问题可能很愚蠢，但它确实让我困惑了很长时间。

我阅读了很多关于无线传感器网络的论文。许多研究人员将他们的问题建模为 ILP 的形式。但是，ILP 是 NP 完全的，因此它对于解决问题效率不高。

那么为什么人们将他们的问题写成 ILP 的形式呢？他们这样做是为了让他们的问题清晰易懂吗？还是我在理解 ILP 和 NPC 之间的关系时犯了一些错误？

非常感谢您能帮我解决这个问题。

4

2 回答 2

2

虽然这个问题可能被认为是题外话，但基本上有几点需要解决。

  1. 你是对的，一般整数线性规划是NP-hard。
  2. 如果需要解决一个特定的问题，而一般整数线性规划是最具体的表达方式，那么对此无能为力；有些问题很难解决。
  3. 在某些情况下，可以使用LP松弛来代替，因为可以证明启发式或某种近似比率。

这里的关键点是整数线性规划是表达问题的一种普遍形式。基本上，我将您的问题理解为以下问题。

“为什么人们使用算法难以解决的模型来描述实际问题？”

好吧，如果总体上可以规避这个缺点，那么用排序的方式表达每个问题将是一个好主意，这在算法上很容易。

于 2016-02-12T11:59:21.450 回答
0

NP-hard 指的是最坏情况下算法的复杂度。对于大多数 NP-hard 问题，我们有有效的算法（启发式或精确算法）在大多数情况下表现良好，即使它们在最坏的情况下表现不佳。因此，ILP 在实践中是一个非常有用的工具，即使它在某些问题上做得不好。

我有一把锤子。有些工作我的锤子根本不适合，或者需要很长时间。但它仍然是一个非常有用的工具，因为它可以很好地为我完成很多工作。

ILP 在很多方面都是一回事。

于 2016-02-13T00:37:20.097 回答