performance - 降低该算法的时间复杂度

Question

我正在玩一款具有武器锻造组件的游戏，您可以在其中组合两种武器以获得一种新武器。武器组合的绝对数量(参见 http://www.gamefaqs.com/ps/914326-vagrant-story/faqs/8485 中的“6.1. Blade 组合表”)使得很难弄清楚通过反复锻造最终可以从当前武器中创造出什么，所以我尝试编写一个程序来执行此操作为我。我给它列出了我目前拥有的武器，例如:

• 弗朗西斯卡
• 他巴津
• 克里斯

它给了我可以锻造的所有武器的列表:

• 球锤
• 查卡克
• 德克
• 弗朗西斯卡
• 大月牙
• 飞刀

问题是我使用的是一种扩展性极差的蛮力算法；七件起始武器计算所有可能的武器大约需要 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);
            }
        }
    }
}

In Chinese:我尝试了我的源武器列表中两种武器的每一种组合。对于这些组合中的每一个，我创建了一个新列表，列出了我在该组合之后拥有的所有武器(即新组合的武器加上除我组合的两个之外的所有源武器)，然后我重复这些新列表的步骤。

有更好的方法吗？

请注意，以相反顺序组合武器会改变结果(Rapier + Firangi = Short Sword，但 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

另外请注意，武器列表中的重复项很重要，无法删除。例如，如果我在我的起始武器列表中添加第二个克里斯，那么我就有了以下列表:

• 弗朗西斯卡
• 他巴津
• 克里斯
• 克里斯

然后我可以锻造以下元素:

• 球锤
• 战斧
• 战刀
• 查卡克
• 德克
• 弗朗西斯卡
• 克里斯
• 库迪
• 大月牙
• scramasax
• 飞刀

添加一把重复的剑让我能够锻造四件我以前无法打造的新元素。它还将四项列表的伪造测试总数从三项列表的 27 项增加到 252 项。

编辑:我觉得解决这个问题需要比我拥有的更多的数学和计算机科学知识，所以我打算放弃它。起初这似乎是一个足够简单的问题，但后来，旅行推销员也是如此。我接受 David Eisenstat 的回答，因为记住和跳过重复项目列表的建议在执行时间上产生了如此巨大的差异，并且似乎适用于许多类似的问题。

Answer 1

开始 memoizing蛮力解决方案，即对 source_weapons 进行排序，使其可散列(例如，通过用逗号连接转换为字符串)，并在输入/输出对的映射中查找它。如果不存在，则照常进行计算并将结果添加到 map 中。这通常会事半功倍。

或者，您可以进行向后搜索。给定多套武器，通过以所有可能的方式用两种武器替换其中一种武器来锻造它来形成前辈。从由目标武器的单例多重集组成的单例列表开始，通过列表元素的前辈重复扩展列表，然后剔除作为其他超集的多重集。到达固定点时停止。

---

如果线性规划是一种选择，那么就有系统的方法来修剪搜索树。特别是，让我们通过 (i) 允许无限供应“催化剂”(这里可能不需要？) (ii) 允许“部分”锻造，例如，如果 X + Y = > Z，然后 0.5 X + 0.5 Y => 0.5 Z。然后有一个 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,

如果 i 是目标项，则 q_i 为 1，否则减去 i 最初可用的数量.这个简单版本有高效的求解器。由于 react 始终为 2 => 1，因此您始终可以为整数解恢复可行的锻造计划。因此，我会推荐整数规划来解决这个问题。下面的段落可能仍然很有趣。

我知道运送 LP 解算器可能不方便，所以这里有一个见解可以让您摆脱困境。当且仅当其对偶有界时，此 LP 才是可行的。直觉上，对偶问题是为每件元素分配一个“值(value)”，这样无论您如何锻造，您的库存总值(value)都不会增加。如果目标元素的值(value)高于可用库存，则您无法伪造它。您可以使用任何您能想到的方法来分配这些值。