【Minecraft】鐵砧算法介紹
—— 棘手的問題 ——
無論是對精通鐵砧的玩家還是亂敲附魔書的小白，都先試著思考這樣一個問題：
一個頭盔，一本荊棘 3、一本保護 4 還有一本水下呼吸 3，如何用最少的經驗將這 3 本附魔書合并到頭盔上？
多數玩家面臨這樣的問題，可能直接就直接亂敲了，比如直接一本一本敲上去。了解過一些鐵砧機制的玩家可能會選擇，4 個物品先兩兩合并，之后再敲一起。那么哪種路線更好呢？
同時，除了合并附魔書的路線，還有順序問題：當我們把附魔書放上去就會發(fā)現(xiàn)，荊棘 3 是比其他兩本書都要貴的，整整要 12 級經驗。而保護 4 反而最便宜，只要 4 級。所以是先敲貴的，還是便宜的？
—— 巨大的空間 ——
綜合來看 3 本附魔書可以產生共 5 種合并路線：
在最左的位置是頭盔的情況下，剩下的 3 個位置又各有 6 種放置物品的方法。也就是說，僅僅 3 本書就產生了 30 種不同的結果。
同樣 4 本書就會有 14 種路線，24 種擺放，共 336 種結果；7 本書 2162160 種結果；n 本書? 種結果。
鐵砧基礎知識
為了解決問題，我們先來了解一下，鐵砧是如何計算單次合并消耗的經驗量的。
首先是來自 wiki 的解釋：
目標物品和犧牲物品的累積懲罰之和。
如果同時進行重命名，則額外產生重命名的費用。
如果目標物品耐久度未滿，則耗費2級用于維修。
如果犧牲物品擁有魔咒，則產生附魔費用。
這里我們忽略第二點和第三點，我們只討論簡單的合并情況。
上面涉及到幾個概念：
目標物品和犧牲物品：對應鐵砧合并時左側和右側的物品。（后文直接用左右代替）
累計懲罰：每次鐵砧操作后得到的新物品會產生累計懲罰，下次合并消耗額外的經驗。
附魔費用：每個附魔都有自己的價值，附魔越貴越多，消耗經驗也就越多。
簡單來說，消耗經驗 = 附魔費用 + 左累計懲罰 + 右累計懲罰
不會用沒關系，具體如何計算，我們下面舉例說明：
測試三本附魔書：荊棘 3、保護 4 和經驗修補。這三本書都是創(chuàng)造直接拿的，所以它們的累計懲罰都為 0。
我們首先來觀察組合頭盔和荊棘附魔書是什么樣的：
這個操作會消耗 12 級經驗，同時新物品會多出現(xiàn)一個 tag：RepairCost，也就是上述的累計懲罰。
這里使用的是 Kiwi 模組提供的 NBT 顯示功能。除了通過觀察 NBT，也可以嘗試對物品改名，因為改名固定消耗 1 級經驗，所以改名時附魔花費減一就是物品的累計懲罰。
如果我們再嘗試其他附魔書可以得到下面的結果：
荊棘 3——12 級、保護 4——4 級、經驗修補——2 級
通過這樣，我們就得到了附魔書對應的附魔費用，因為次數兩個物品的累計懲罰都為 0。
接下來我們嘗試合并保護和荊棘，通過上面的表格我們可以算出，這次操作會消耗 12 級經驗，當然鐵砧也會告訴我們：
之后我們嘗試把新的附魔書與頭盔合并：
可以看到需要 17 級，這個數字是怎么來的呢。我們知道此時附魔書有 1 級的累計懲罰，所以書的價值就是 16 級，也剛好是荊棘 3 的 12 級加上保護 4 的 4 級?？梢缘贸?，附魔費用是線性疊加的。我們也可以認為附魔費用，就是“價值”，新書的價值就是兩個書的和。
那么累計懲罰如何計算呢，對于新物品（新獲得的、新合成的、沒有經過鐵砧操作或被砂輪抹去附魔的物品），它們的累計懲罰都為 0。經過一次鐵砧后變?yōu)?1，之后 3、7、15 …… ?；蛘哒f每次都是前一次的兩倍加 1 也就是 2n+1。當然這里的前一次指的是左右兩個物品中懲罰較大的那個。
現(xiàn)在我們知道了計算一套合成的全部方法：
通過改名可以知道一個物品的累計懲罰；右邊放書可以獲得附魔費用。
合并后價值（附魔費用）是兩個物品價值相加；累計懲罰變成兩倍再加一。
鐵砧計算方法
現(xiàn)在我們可以脫離鐵砧進行模擬計算了，這里我們用一個 wiki 上的例子實踐一下：
這是一個一共消耗 68 級經驗的靴子附魔合成。
因為我們不關心是對靴子還是對什么別的物品合并，也不關心附魔書是什么，我們只關心所有物品的價值和懲罰，所以讓我們把這個過程抽象為一顆二叉樹：
其中，每一個節(jié)點代表一個物品，數字代表物品的價值；每條邊代表物品合并需要額外花費的懲罰。這樣改成樹更有助于我們計算。此時我們只要把所有的右側節(jié)點（紫色）數字相加，再把所有邊上的數字相加，就得到了總的經驗花費。對于這個例子則是 58 + 10 = 68。
至此，我們學會了如何口算模擬計算鐵砧消耗。
既然教會了大家如何計算鐵砧消耗，那么這篇專欄就到這里了……？
探索最小經驗之路
什么，你問怎么解決之前說的經驗最小化問題？啊這，你真的這么想聽嗎，那我們借助二叉樹再把問題抽象化。
請解下面的算法題：
題目：
給定 n 組數字，分別代表 n 個節(jié)點（物品）的價值和懲罰。用這 n 個節(jié)點作為葉子節(jié)點構建一顆二叉樹：父節(jié)點的價值是葉子節(jié)點的和，懲罰是葉子節(jié)點中較大的那個乘 2 并加 1；節(jié)點的懲罰標注在其與父節(jié)點鏈接的邊上。全部節(jié)點計算完畢后，樹的最終得分為：全部右節(jié)點的價值和加邊上的懲罰和。
要求：
根據給定的輸入，構建出滿足要求的得分最小的二叉樹。
可是我也不會，所以你來幫我算吧！我溜了！
開玩笑的，我還是會在這里進行解題的，然而沒開玩笑的是，我確實不會解上面這道題。但是我可以幫你解開這道題的變種：去除輸入懲罰后的題目。如果沒有輸入懲罰，只有價值的情況下，這道題其實簡單一些。
在正式解題之前，可能不少觀眾會覺得：哇…這，這我也算不過來啊，有沒有個簡單結論直接告訴我怎么搞。
或者說只是單純的太長不想看，那么這里就是一個簡單結論：別多想，兩兩合并，就像上面?wiki 那個例子一樣。
如果你還要更好一點，那么：在兩兩合并的基礎上，裝備第一次敲附魔書的時候，和最貴的那個合并。剩下的就…隨緣吧。
我們來分析這道題，把這道題分成幾個步驟：
構建一顆 n 個葉子節(jié)點的二叉樹
將價值排序填入樹中
計算樹的分數
不斷重復這些步驟，直到比較出分數最小的樹。
那么我們先挑最簡單的來：計算樹的分數?將價值填入給定的樹中
我們依然使用上面的 wiki 例子：
因為我們限定所有輸入物品懲罰都是 0，所以在樹結構固定的情況下，總懲罰也是固定的（對于這個例子也就是 10）。因此我們要做的就是如何填入價值，讓所有紫節(jié)點的和最小。
對于價值和，我們先試著填入未知量：
于是我們可以得到這棵樹的價值和是：a+c+e+g+(b+c)+(f+g)+(d+e+f+g) = a+b+2c+d+2e+2f+3g
我們可以這樣理解，未知數的系數就是它出現(xiàn)在右節(jié)點的次數，通過從上到下標注每個節(jié)點出現(xiàn)在右側的次數，就可以快速得出紫色節(jié)點的和。
這樣我們可以快速得到葉子節(jié)點的系數：1 1 2 1 2 2 3
我們可以嘗試帶入例子中的的價值：
可以看到計算與實際結果一致，也就是說我們可以計算每個葉子節(jié)點的系數作為權重來快速計算價值和。
而且通過計算可以發(fā)現(xiàn)，同系數時價值互換對結果不會產生影響。所以為了價值和最小，有如下算法（也是后面會用到的書本排序算法）：
計算全部葉節(jié)點權重
按照節(jié)點權重升序填入降序的價值
至此，我們得到了比較兩棵樹好壞的方法：
權重和懲罰相同，兩棵樹等價
權重相同的情況下，懲罰和小的樹好
懲罰相同的情況下，權重較低的樹好
都不同的情況下，需要帶入書本價值計算
接下來我們解決另一個問題：如何確定樹的結構
然而到現(xiàn)在為止，我們一直在簡化模型，但需要計算的樹的數量一直沒有改變。如果還是 n 本書有 ?種樹的話計算量依舊很大。?
但是與其從零開始構建一棵樹，不如在之前的基礎上更新。所以，我們可以嘗試先構建 1 本書時候的樹，然后向這棵樹添加新的節(jié)點。每次使用貪心算法的思想嘗試做到最好。這樣逐漸得到 2 本書時候最優(yōu)的樹，直到 n 本書。至少這樣不用把所有的樹都暴力搜索一次，而是一次性得出最好的樹。
雖然貪心的結果不一定是對的，但至少我們先試試。
那么先來看最簡單的一棵樹：
對于這棵樹接下來有兩個生長方向：
可以看出來，兩棵樹的懲罰和是相同的，但是左樹的權重更低，就意味著消耗的經驗更少。
所以我們可以得出結論：向左生長優(yōu)于向右生長。
我們接著左樹繼續(xù)生長，依然有兩種結果：（現(xiàn)在起紫色標注改為葉子節(jié)點）
現(xiàn)在出現(xiàn)了分歧：左樹懲罰低但權重高，右樹懲罰高但權重低。
這里我們可以這樣理解：選擇左樹就是選擇多算一次附魔書的價值（因為權重是系數），選擇右樹就是選擇 +2 經驗懲罰。
這樣事情就清楚了，如果書比較貴，那就選擇右側，如果書便宜那就選擇左側。
所以讓樹生長，無非只有兩種選擇：向右生長和向左下生長；具體的生長方向取決于書的價值。
然而這并沒有太大幫助，無非只是排除了右下生長這一種情況。
我們還有很多問題要解決：
權衡生長方向時選擇什么書的價值作為標準，最貴的還是最便宜的？
繼續(xù)生長下去單次生長的可選位置增多，可能會產生不同的分支，如何確保結果不是局部最優(yōu)解而是全局最優(yōu)解？
這樣貪心算法的結果一定是對的嗎？
這些問題暫時還不能解決，但是現(xiàn)在的模型還有優(yōu)化的空間。
通過觀察二叉樹，我們可以搞點騷操作：因為每次鐵砧操作必定是兩兩合并，所以最后葉子節(jié)點一定是成對的，每次生長都會增加兩個節(jié)點。如果我們去除所有的葉子節(jié)點轉而觀察所有的“合并”操作，是不是可以簡化模型？
比如這樣一顆 5 層的樹：
物品變?yōu)榱?/span>合并操作
接下來我們需要驗證新模型是否可以繼承之前的性質：
對于懲罰：顯而易見因為刪除的葉子節(jié)點的懲罰均為 0，所以懲罰不會產生任何變化。
對于權重：因為權重是自上而下計算的，所以我們可以通過加回葉子節(jié)點的方式補回到原來的樹來計算。所以新模型葉子節(jié)點權重小，那舊模型也一樣小。在接下來的計算中也可以得到體現(xiàn)。
“向左生長優(yōu)于向右生長”
可以看到對于這 4 個可以生長的方向（虛線圓所示）中，所有情況都會讓樹的層數增加，而且所增加的懲罰是等同的，所以我們只需要比較他們增加的權重，就可以判斷哪里是最優(yōu)的生長方向。
對于4個方向中有兩個右節(jié)點，根據之前的左優(yōu)于右生長規(guī)則，這兩處都是不好的生長方向。那么還剩下兩個左節(jié)點。
此時我們比較他們產生的新權重：如果選擇左 1，權重的變化是 0 -> 0, 1； 如果選擇左 2，權重的變化是 1 -> 1, 2。左 2 的權重是比較高的，因此最優(yōu)的生長方向是左 1。所以左右優(yōu)先原則在簡化后的模型上依然適用。
事實上對于任意一個方向的生長，其權重的變化均為 x -> x, x+1，也就是說 x 高的其權重也高（即可以不去看方塊節(jié)點的權重，而直接去看圓節(jié)點）。
權重是方向決定的，每向右一次，權重就增加 1，這意味著在選擇生長方向時，左側總是優(yōu)先于右側，也就是說對于單個節(jié)點的左右優(yōu)先規(guī)則對于整棵樹也適用。進而我們還可以推論出，整棵樹延伸最遠的地方，一定是最左側。
基于這個結論，我們可以對需要生成的樹按照層數進行分類。比如我們要生成一顆 10 個節(jié)點的樹（10 次合并操作或 10 本附魔書加 1 個物品）可以生成一顆高度（深度）為 4 的最優(yōu)樹，然后是高度為 5、6、7 …… 10 的最優(yōu)樹。之后將這些樹進行比較再得出一個最優(yōu)解。
這樣做的好處是固定了樹的高度，防止樹亂生長，同時也減少了計算量。因為在除了最左側的位置再往深生長不是最優(yōu)的?，F(xiàn)在我們才真正有一個構建樹的起點。
現(xiàn)在我們開始嘗試構建一顆樹，這里以高度為 4 的樹為例。
首先構建主要路徑（做左側分支）
如圖最左側為主要路徑，虛線為接下來可生長的位置。
可以觀察到，可以生長的三個位置，同懲罰也同權重，所以均為等價位置。那么看似會產生三條分支，這里選擇最上面的作為生長方向演示。
接下來我們有 4 個可生長的位置，其中相同顏色的為等價節(jié)點。這里其實我們可以看出一個新結論：一個節(jié)點產生的新位置一定比本身要差。不難理解，作為一個新節(jié)點，肯定是沒有后代節(jié)點的，所以無論是向左還是向右生長，都會產生額外的懲罰，更不用提向右還會增強權重。
利用新的結論，我們可以知道，藍色優(yōu)于黃色和紅色。因為黃色和紅色的父節(jié)點和其他藍色是等價的。
所以如果繼續(xù)生長也是在藍色位置選擇其一，同樣再產生的新節(jié)點，還是沒有剩下的那個藍色節(jié)點好。因此選擇兩個節(jié)點之后，兩個藍色節(jié)點都會使用。正因為等價節(jié)點會被如此接連使用，可以得出：等價節(jié)點不會產生分支。那么之前說的產生分支也就不存在了。
讓我們繼續(xù)。
左右優(yōu)先原則
到這里，我們才遇到了第一個分支情況。首先我們可以排除紅色。接下來藍色和黃色選擇哪一個？
藍色會增加 7 點懲罰和 1 權重，黃色會增加 1懲罰和 2 權重。也就是說，是選擇多 6 點懲罰還是多一本書的價值。如果多一本書，哪一本書？（這也對應了之前的問題其一）
這里提前說結論，用來參照的書，是所有書中價值最小的那本。我會在后面提供解釋，但現(xiàn)在先讓我們繼續(xù)。
如果書價值大于 6 那么選擇藍色：
此時接下來三種情況等價。并且最終會順利填完全部位置。
如果書價值小于6 那么選擇黃色：
因為之前存在等價節(jié)點，所以這里我們面臨相同的選擇，但是這一次我們不能用最便宜的書了，因為我們已經使用過了，所以我們要用第二便宜的書作為判斷標準。
如果第二本書依然便宜：
否則：
雖然這里產生了分支，但是請注意如果再增長一個節(jié)點，兩個分支又會合并：
可以看出，當等價態(tài)出現(xiàn)時，不管如何選擇，再增長的狀態(tài)下都會最終合并。又因為我們保持每一個分支都是最優(yōu)的，所以就算是在分支合并前停下，得到的結果也是屬于這一高度的樹的全局最優(yōu)解（對第二問題的回答）。同時正因為會合并，所以貪心算法是可用的（第三個問題）。
接下來無論怎樣也都可以順利填完 4 層，也就是 15 個節(jié)點。如果我們不需要這么多節(jié)點，只需要在節(jié)點數達到目標時停下即可。
現(xiàn)在讓我們解答遺留下來的第一個問題：為什么選擇價值最小的書？
根據之前的書本排序算法，我們知道權重越大的節(jié)點，最后分配到的書價值也就越小。所以這個問題可以轉換成，此時節(jié)點權重一定是最大的嗎？（這里指的節(jié)點是面臨選擇時權重較大的那個節(jié)點，因為面臨選擇時都是一個節(jié)點權重大懲罰小，另一個權重小懲罰大，因為懲罰是可計算的，所以需要書才能判斷的節(jié)點是兩者中權重大的那個。）
對于這個問題，我們可以假設存在一個更大權重的節(jié)點：
在這里面臨選擇的是黃色和藍色節(jié)點，此時存在一個權重更高的紅色節(jié)點，意味著黃色不能被分配到最便宜的書。
從這里我們開始分析，既然紅色節(jié)點存在，而且自己的權重大于 0，那么它自己一定在某棵子樹的右節(jié)點上。換句話說，紅色節(jié)點的祖宗節(jié)點，一定有一個是右節(jié)點：
同時，既然這個祖宗節(jié)點存在，而且是作為右節(jié)點，根據之前的左右優(yōu)先原則，有右節(jié)點的前提一定是左節(jié)點存在。于是也肯定存在綠色這樣一個等于黃色節(jié)點權重的節(jié)點。
既然綠色已經存在，那就說明綠色比黃色更優(yōu)，或者等價。但是黃色作為可選的新生節(jié)點，就算存在，其懲罰也一定為 1。所以綠色的懲罰一定小于等于 1。顯然作為合并節(jié)點，懲罰不可能小于 1。所以綠色必然和黃色等價?，F(xiàn)在，根據等價節(jié)點優(yōu)先的規(guī)則，此時懲罰和權重都更差的紅色節(jié)點就必然不能存在。因此當沖突存在時，不可能存在權重更大的節(jié)點。甚至可以說，在任何時候，都不可能存在一個權重高于所有可選節(jié)點的權重的節(jié)點。
現(xiàn)在我們解決了之前遺留的全部問題，也得出了一個合理的樹構建算法。
接下來，對于其他層數的樹也做像上面一樣的構建操作，直到節(jié)點數達到目標。
最后針對每一棵樹排序出最優(yōu)書本順序（書本排序算法），并計算出分數。這樣我們就可以比較出所有樹中最優(yōu)的那一個。
代碼實現(xiàn)
下面是一份鐵砧最小經驗算法的 Python 代碼實現(xiàn)
現(xiàn)在我們唯一需要解決的問題就是，如果最開始附魔書有懲罰怎么辦？
我不會?ˉ\_(ツ)_/ˉ?……
未完待續(xù)？
