减少此算法的时间复杂度

Question

我正在玩一款拥有武器锻造组件的游戏,你可以将两种武器结合起来获得新武器.武器组合的绝对数量(参见http://www.gamefaqs.com/ps/914326-vagrant-story/faqs/8485上的 "6.1.刀片组合表" )很难弄清楚你最终可以创造出什么通过反复锻造你当前的武器,所以我尝试编写一个程序来为我做这个.我给它一份我目前拥有的武器清单,例如:

• 弗朗西斯
• tabarzin
• 短剑的一种

它给了我所有可以伪造的武器清单:

• 球梅斯
• chamkaq
• 短剑
• 弗朗西斯
• 大新月
• 扔刀

问题是我使用的蛮力算法扩展得非常差; 计算7种起始武器的所有可能武器需要大约15秒,而计算8种起始武器需要几分钟.我希望它能够计算多达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添加到我的起始武器列表中,那么我有以下列表:

• 弗朗西斯
• tabarzin
• 短剑的一种
• 短剑的一种

然后我就可以伪造以下物品:

• 球梅斯
• 战斧
• 战刀
• chamkaq
• 短剑
• 弗朗西斯
• 短剑的一种
• 库地
• 大新月
• scramasax
• 扔刀

添加一个重复的kris让我可以伪造四个我以前无法做到的新项目.它还将锻造测试的总数增加到了四个项目列表中的252个,而三个项目列表中则增加了27个.

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

Answer 1

首先记住蛮力解决方案,即排序source_weapons,使其可以删除(例如,通过用逗号连接转换为字符串),并在输入/输出对的映射中查找.如果不存在,则按正常方式进行计算并将结果添加到地图中.这通常会带来很大的成功.

或者,您可以进行向后搜索.鉴于多种武器,通过用一种可能的方式用两种武器替换其中一种武器来形成前体.从包含由目标武器组成的单例多重集构成的单例列表开始,通过列表元素的前任重复扩展列表,然后剔除作为其他元素的超集的多重集.到达固定点时停止.

如果线性编程是一种选择,那么有一些系统的方法来修剪搜索树.特别是,通过(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,

这里q_i是1如果i是目标的项目,否则减去的数量i最初可用.这个简单的版本有高效的解决方案.由于反应始终为2 => 1,因此您始终可以恢复整数解的可行锻造计划.因此,我建议针对此问题进行整数编程.以下段落可能仍有意义.

我知道装运LP解算器可能不方便,所以这里有一个让你不用的洞察力.当且仅当其双重有界时,该LP是可行的.直观地说,双重问题是为每个项目分配一个"值",这样,无论你伪造,你的库存总价值都不会增加.如果目标项的价值超过可用库存,那么您无法伪造它.您可以使用您可以想到的任何方法来分配这些值.

Answer 2

我认为你不太可能对这个问题得到一个很好的一般性答案,因为如果有一个有效的算法来解决你的问题,那么它也能够解决NP完全问题.

例如,考虑在二进制矩阵中找到最大独立行数的问题.
这是已知的NP完全问题(例如,通过显示与最大独立集问题的等价性).

我们可以通过以下方式将此问题简化为您的问题:

我们可以开始为二进制矩阵中的每一列保留一个武器,然后我们想象每一行描述制作新武器的另一种方法(比如战斧).我们构造武器翻译表,使得使用方法i制作战斧,我们需要所有武器j使得M [i,j]等于1(这可能涉及发明一些额外的武器).

然后我们构建了一系列超级武器,可以通过组合不同数量的战斧来制造.

例如,巨型终极战斧可能需要组合4个战斗轴.

如果我们能够找出可以从你的起始武器构造的最好的武器,那么我们已经解决了在原始二进制矩阵中找到最大数量的独立行的问题.