2

首先，我要说我对理论之类的东西知之甚少。但我想知道这是一个 NP 还是 NP 完全问题。这听起来像是子集和问题的一个特例。

无论如何，我最近一直在玩这款名为 Alchemy 的游戏，它引发了这个想法。基本上，您从 4 个基本元素开始，然后将它们组合成其他元素。

因此，例如，如果您愿意制作元素，这是一个简短的“食谱”

火=基本元素
水=基本元素
空气=基本元素
地球=基本元素
沙子=土+土
玻璃=沙子+火
能量=火+空气
灯泡=能量+玻璃

因此，假设一台计算机只能创建 4 个基本元素，但它可以创建多组元素。因此，您编写一个程序来通过组合其他元素来制作任何元素。该程序将如何处理创建灯泡的列表？

很明显，火+空气=能量，土+土=沙，沙+火=玻璃，能量+玻璃=灯泡。

但是我想不出任何方法来编写程序来处理列表并在不使用蛮力类型方法并检查每个元素并检查其配方的情况下弄清楚这一点。

这是一个NP问题吗？或者我只是无法弄清楚这一点？

4

2 回答 2

4

该程序将如何处理创建灯泡的列表？

当然，您只是向后运行定义；例如

  1. 制作一个灯泡需要 1 能量 + 1 玻璃
  2. 创造能量需要 1 火 + 1 空气

等等。这实际上是一个简单的树遍历。

OTOH，如果您想让计算机弄清楚能量+玻璃意味着灯泡（而不是“一团熔融玻璃”），那么您就没有解决问题的机会。您可能无法让 2 个玩家同意能量 + 玻璃 = 灯泡！

于 2010-11-29T01:44:29.010 回答
3

您可以轻松地将问题建模为图形，并使用任何完整的搜索算法寻找解决方案。如果您没有任何经验，研究自动化规划也可能会有所帮助。我链接到该文本是因为它还介绍了复杂性和搜索算法。

于 2010-11-29T01:42:28.667 回答