关于目前的铁砧最优算法

[YueLengM]

其实当前使用的算法（BV1Yz4y1U7c1）并不是最优，目前大概还没有一个可以接受任意给定物品的通用铁砧算法。

下面是引用过来的评论

以保护4-lv4 耐久3-lv3 经验修补-lv2 为例
按照当前的算法 结合顺序是 (0+2) + (4+3) 一共消耗 14 级经验。
逐本敲附魔时 ((0+4) + 3) + 2 只有 13 级的消耗。
稍微改变下附魔顺序 (0+4) + (3+2) 也是 13 级，且没有增加次数惩罚。

从第一步的贪心开始，将低消耗附魔与物品优先组合，就决定了后续高消耗附魔被多次计算。

再举一个极端一点例子，1.18 满配的鞋子：灵魂疾行3、荆棘3、摔落保护4、深海3、保护4、耐久3、经验修补
按照目前的算法需要消耗 83 级、而 wiki 给的例子虽然不是最优，但也才只有68级。

[Dinosaur-MC]

是的，我目前正在研究新的算法，我正在尝试将这里的算法改进后加入到程序中来。

[YueLengM]

这个算法确实好了很多，也得出了和上面wiki一样的结果，但是还是没考虑用惩罚换经验的问题。
我曾经也研究过一段时间的铁砧算法，发现层数最小不一定是最小经验消耗的前提。但是又没有很好的判断方法，只能穷举所有情况，很头疼。
最开始提到的满配鞋子就是这种情况，用多一层的代价，减少了 2 级总消耗，单步的最高消耗也从 21 降到了 16。

[Dinosaur-MC]

在2.0Beta版本中，采用了全新的算法，其简要规则如下：

1、惩罚相同且惩罚低的组合优先
2、与非附魔书物品组合且等级花费高的优先
3、等级花费高的作为目标物品优先
4、等级花费高的作为牺牲物品优先
5、若找不到惩罚相同的，则惩罚相近的组合优先

• 算法简要原理为：

1. 一般情况下，无论如何组合，所有选择合并的魔咒（不考虑不兼容与冲突的情况）终要全部合并到目标物品上，其总魔咒花费¹为每个步骤的魔咒花费²之和，而由于魔咒等级和乘数都为常数，所以总魔咒花费也为常数，这个常数称为魔咒花费的最低极限，是不可控量。
2. 铁砧附魔时，除了魔咒花费外，随着合并操作次数的增多，就会产生累积惩罚³，导致附魔花费急剧上升。由累积惩罚的等级花费计算公式和累积惩罚的自增原理⁴可知，我们可以通过控制对物品的合并策略将累积惩罚降至最低，这种策略方法就是让具有相同累积惩罚的物品优先合并，如0+0→1，1+1→2...，其次是累积惩罚最接近的两个物品优先合并，这样就可以避免或减少像0+2→3这样出现累积惩罚的提前升高。
3. 随着合并操作次数⁵不可避免地增加，每过一个步骤经验等级花费由于累积惩罚而不断增加，要是再加上魔咒花费，那么这个花费将增加得更快，越往后的步骤花费越高，越容易超过39级的等级限制，以至于附魔成本太高或附魔无法完全完成。所以，当累积惩罚也达到最低极限后，我们就需要根据铁砧的魔咒花费计算机制控制将魔咒花费高的物品率先与目标物品合并，魔咒花费低的物品最后再合并，使往后的步骤尽可能地不会因为魔咒花费而扩大成本，实现了每步骤的等级花费平均⁶和总经验值花费最小。

这个算法既可以更好地平均惩罚，达到最低总消耗，也可以尽可能地平均步骤消耗，降低过程的最高步骤消耗，从而降低总经验值的消耗。所以我就称之为综合平均算法或全局平均算法。

Footnotes

1. 铁砧附魔的整个过程中，忽略惩罚、修复和重命名的花费后剩余所需的总经验等级 ↩

2. 魔咒等级*乘数 ↩

3. 其等级花费计算公式为 f(n) = 2^n - 1, n∈N ↩

4. 铁砧上每次合并操作后，输出物品的惩罚次数为取目标物品的累积惩罚次数和牺牲物品的累积惩罚次数的最大值后加一 ↩

5. 总操作次数 = 参与合并物品总数 - 1 ↩

6. 因为累积惩罚量是从0开始指数上升的，所以将魔咒花费高的转移到前面的步骤可以类似地平均每一步骤的总花费。 ↩

[zouxiaofei1]

穷举所有情况的思路是可行的，有一个基于状态压缩动态规划的实现 https://github.com/zouxiaofei1/MC_enchant_calc

[YueLengM]

穷举所有情况的思路是可行的，有一个基于状态压缩动态规划的实现 https://github.com/zouxiaofei1/MC_enchant_calc

我看这个目前只考虑了初始无惩罚和无合并附魔的情况，同时没有考虑降低单次最低需求经验。

这种我也实现过最小经验算法，还做了一点单次最低优化，但是有几个单次经验不及上面mcbbs里人工列举出的，倒是目前也没发现有总经验计算错误的。

总之最好还是需要一种能考虑各种情况的通用算法。

[Lotuses-robot]

穷举所有情况的思路是可行的，有一个基于状态压缩动态规划的实现 https://github.com/zouxiaofei1/MC_enchant_calc

我看这个目前只考虑了初始无惩罚和无合并附魔的情况，同时没有考虑降低单次最低需求经验。

这种我也实现过最小经验算法，还做了一点单次最低优化，但是有几个单次经验不及上面mcbbs里人工列举出的，倒是目前也没发现有总经验计算错误的。

总之最好还是需要一种能考虑各种情况的通用算法。

有没有一种可能分别做模式？

即分最小单次经验和最小总经验？

[Lotuses-robot]

毕竟到后期不缺经验啊，只需要防止 “过于昂贵”

[YueLengM]

毕竟到后期不缺经验啊，只需要防止 “过于昂贵”

说道这个实用性的话，我个人觉得这个算法的研究价值还是高于实际价值的。不缺经验的时候，用完全二叉树的合并方法先合并贵的，原版和魔改大多数情况都遇不到过于昂贵。而缺经验的时候，附魔书也比较难获取。更多时候是，在整合包里遇到某些特殊情况才想起来开这种工具算一下。

说回来单次最小经验的情况，大方向应该就是从贵到便宜依次合并就行，单次合并只考虑惩罚和价值，既然惩罚是逐步增加的，那就应该趁着惩罚低把贵的书合到装备上。不过后期可能会出现小价值的书累加起来变得很贵的情况。具体的话还要多尝试一下看看规律。

[Dinosaur-MC]

穷举所有情况的思路是可行的，有一个基于状态压缩动态规划的实现 https://github.com/zouxiaofei1/MC_enchant_calc

我看这个目前只考虑了初始无惩罚和无合并附魔的情况，同时没有考虑降低单次最低需求经验。
这种我也实现过最小经验算法，还做了一点单次最低优化，但是有几个单次经验不及上面mcbbs里人工列举出的，倒是目前也没发现有总经验计算错误的。
总之最好还是需要一种能考虑各种情况的通用算法。

有没有一种可能分别做模式？

即分最小单次经验和最小总经验？

我目前的开发路线正是朝着通用算法而去的，可是高三不给时间了ToT，路漫漫也。

[Dinosaur-MC]

在V2.1.0Beta中新增的算法已基本解决“后续高消耗附魔被多次计算”的问题，JE1.18 满配的鞋子（灵魂疾行3、荆棘3、摔落保护4、深海3、保护4、耐久3、经验修补）与WiKi给出的68级相同。