我正在玩一个带有武器锻造部件的游戏，在该游戏中，您将两种武器结合在一起得到新的武器。大量的武器组合(请参阅http://www.gamefaqs.com/ps/914326-vagrant-story/faqs/8485的“6.1。叶片组合表”)使您很难弄清楚最终可以通过反复锻造从当前武器中创造出什么，因此我尝试编写一个程序来为我完成此任务。我给它列出了我目前拥有的武器，例如:
francisca
它列出了我可以伪造的所有武器:
问题是我使用的蛮力算法伸缩性极差。计算七个起始武器的所有可能武器大约需要15秒，而计算八个起始武器则需要几分钟。我希望它能够计算多达64种武器(您一次可以拥有的最大武器)，但是我认为我的寿命不足以看到结果。
function find_possible_weapons(source_weapons)
{
for (i in source_weapons)
{
for (j in source_weapons)
{
if (i != j)
{
result_weapon = combine_weapons(source_weapons[i], source_weapons[j]);
new_weapons = array();
new_weapons.add(result_weapon);
for (k in source_weapons)
{
if (k != i && k != j)
new_weapons.add(source_weapons[k]);
}
find_possible_weapons(new_weapons);
}
}
}
}
用英语:我尝试从我的来源武器列表中选择两种武器的每种组合。对于这些组合中的每一个，我都会创建一个新列表，列出该组合之后要使用的所有武器(即，新组合的武器加上除我组合的两个武器以外的所有源武器)，然后重复这些操作新列表的步骤。
有一个更好的方法吗？
请注意，以相反的顺序组合武器可以更改结果(Rapier + Firangi =短剑，但Firangi + Rapier = Spatha)，因此我无法在
j循环中跳过这些逆转。编辑:这是我上面给出的测试示例的明细，以显示算法的作用。方括号中的一行显示了组合的结果，以下一行是由此产生的新武器列表:
francisca,tabarzin,kris
[francisca + tabarzin = chamkaq]
chamkaq,kris
[chamkaq + kris = large crescent]
large crescent
[kris + chamkaq = large crescent]
large crescent
[francisca + kris = dirk]
dirk,tabarzin
[dirk + tabarzin = francisca]
francisca
[tabarzin + dirk = francisca]
francisca
[tabarzin + francisca = chamkaq]
chamkaq,kris
[chamkaq + kris = large crescent]
large crescent
[kris + chamkaq = large crescent]
large crescent
[tabarzin + kris = throwing knife]
throwing knife,francisca
[throwing knife + francisca = ball mace]
ball mace
[francisca + throwing knife = ball mace]
ball mace
[kris + francisca = dirk]
dirk,tabarzin
[dirk + tabarzin = francisca]
francisca
[tabarzin + dirk = francisca]
francisca
[kris + tabarzin = throwing knife]
throwing knife,francisca
[throwing knife + francisca = ball mace]
ball mace
[francisca + throwing knife = ball mace]
ball mace
另外，请注意，武器列表中的重复项非常重要，无法删除。例如，如果我在启动武器列表中添加第二个kris，以便获得以下列表:
francisca
那么我就能伪造以下物品:
增加了一个重复的kris，使我得以锻造四个以前无法做到的新物品。它还将四项列表的伪造测试总数从三项列表的27个增加到252个。
编辑:我感到解决此问题将需要比我更多的数学和计算机科学知识，因此我将放弃。乍一看似乎很简单，但随后的旅行推销员也是如此。我接受David Eisenstat的回答，因为关于记住和跳过重复的项目列表的建议在执行时间上有很大的不同，并且似乎适用于许多类似的问题。
最佳答案
首先从蛮力解决方案memoizing开始，即对source_weapons排序，使其可哈希化(例如，通过用逗号连接转换为字符串)，然后在输入/输出对映射中查找它。如果不存在，请照常进行计算，然后将结果添加到 map 中。这通常会导致不费吹灰之力的大胜利。
或者，您可以进行向后搜索。给定多种武器，以各种可能的方式通过用伪造武器的两种武器代替一种武器来形成前身。从由目标武器组成的单例多集组成的单例列表开始，由列表元素的前任反复扩展列表，然后剔除其他超集的多集。到达固定点时停止。
如果可以选择线性编程，则可以使用系统的方法来修剪搜索树。特别地，通过(i)无限供应“催化剂”(也许在这里不需要吗？)使问题变得更加容易(ii)允许“部分”锻造，例如，如果X + Y => Z，则为0.5 X + 0.5 Y => 0.5Z。然后有一个LP公式如下。对于所有i + j => k(i和j伪造k)，变量x_{ijk}是执行该伪造的次数。
minimize sum_{i, j => k} x_{ijk} (to prevent wasteful cycles)
for all i: sum_{j, k: j + k => i} x_{jki}
- sum_{j, k: j + i => k} x_{jik}
- sum_{j, k: i + j => k} x_{ijk} >= q_i,
for all i + j => k: x_{ijk} >= 0,
如果
q_i是目标项目，则1是i，否则减去最初可用的i数量。这个简单的版本有高效的求解器。由于反应始终为2 => 1，因此您始终可以为整数解决方案恢复可行的锻造时间表。因此，我建议针对此问题进行整数编程。以下段落可能仍然令人感兴趣。我知道运送LP解算器可能会带来不便，因此，本文提供了一个见解，您可以不用这样做。当且仅当其对偶有界时，此LP才可行。直观上，双重问题是为每个项目分配一个“值”，以使无论您伪造多少，库存总值都不会增加。如果目标项目的值(value)超过可用库存，则您无法伪造它。您可以使用可以想到的任何方法来分配这些值。