1

我是炼金术士。我可以根据我的食谱书用其他东西做东西。例如：

 2 lead + 1 bismuth -> 1 carbon
 1 oxygen + 5 hydrogen + 3 nitrogen -> 2 carbon
 5 carbon + 5 titanium -> 1 gold
 ...etc.

我的食谱书包含数千个食谱，每一个都消耗一些离散量的一个或多个输入并产生离散量的一个输出。作为一个懒惰的炼金术士，我不想记住我所有的食谱。我想编写一个计算机程序来为我解决这个问题。程序的输入是对我想要的东西的描述，比如“2 金”，以及对我库存的描述，比如“5 钛、6 铅、3 铋、2 碳、1 金”。输出应该是“无法制作”或用于创建事物的指令序列。对于此处给出的示例，输出可能是：

make 2 carbon out of 4 lead + 2 bismuth
make 1 gold out of 4 carbon + 4 titanium

然后，再加上我已经拥有的 1 枚金币，我就有了我想要的 2 枚金币。

最后一点：食谱是加权的；例如，如果可以的话，我更喜欢用铅和铋来制造碳。

有没有一种优雅的方法来制定和解决这个问题？一个幼稚的递归解决方案看起来很诱人，但我可以想到会导致它做指数级工作的配方集。

（而且，作为后续行动，有一天我的研究可能会发现一组循环配方——也许我可以用 1 个氦制造 1 个氢，用 1 个氢制造 1 个氦——我希望能够处理这个问题情况也是如此。）

4

1 回答 1

2

问题是NP难的。

给定一个 CNF-SAT 的实例，用试剂准备炼金术表

  1. 每个变量
  2. 每个字面量
  3. 每个条款（不满意的版本）
  4. 每个条款（满意的版本）
  5. 输出。

反应是

  1. 大量供应相应的正面文字的变量
  2. 大量供应相应的否定文字的变量
  3. 从句（不满意的版本）和满意的文字到子句（满意的版本）
  4. 输出的所有子句（满意的版本）。

问题是我们是否可以在给定每个变量之一和每个子句之一的情况下进行输出（不满意的版本）。

这个问题与确定向量加法系统/Petri网的可达性问题有关；我的减少部分基于该文献中出现的减少。

于 2013-05-31T00:45:43.573 回答