requirements - NP Hard 与需求工程的关系

Question

我想从需求工程的角度而不是数学的角度了解 NP-Hard。任何输入表示赞赏。

Answer 1

需求工程是在工程设计过程中定义、记录和维护需求的过程。我能想象到的与 NP-hard 问题的唯一联系如下：
如果问题应该由算法解决，则要求使用一种算法不是NP难的。
NP-hard 本质上（不是数学上）意味着必须计算问题的所有可能解决方案，然后选择最好的解决方案。
典型的例子是旅行推销员问题：
给定许多要访问的城市，找到访问每个城市一次的最短访问。
为了找到最短路径，必须构建所有可能的路径，然后必须选择最短的路径。找到这个最佳解决方案的时间随着城市的数量呈指数增长，即对于更多的城市来说，它是不可解决的。
PS：当然，有些算法可以在合理的时间内很好地解决这个特定问题。