應該如何擺多米諾骨牌？

01-21

現在有n張多米諾骨牌，需要擺放到n個位置上，這n個位置在同一條直線上。
但是擺放不一定穩，有一定可能性倒下。
這裡假設每次擺放一張骨牌，倒向兩邊的概率分別均為p，而擺穩的概率為1-2p。
如果骨牌倒向某一方向了，那麼這個方向相鄰位置的骨牌也會倒向相同的方向，所有倒了的骨牌需要重新擺放。
問題是:以什麼順序擺放骨牌，才能讓擺放次數的期望值最小，這個最小期望是多少？

例如:擺放3張骨牌。先擺1，再擺3，3無論倒向哪一邊1都不會倒，只需要重擺3即可;而如果擺完了1擺2，那麼2倒向1這邊的話1就也倒了，1、2都必須重擺。

我的演算法是這樣:

第一輪擺放:

1-3-5-....-n case n odd

1-3-5-...-n-1 case n even

每個骨牌都是一個 cluster

第二輪擺放:

1-2-3,5-6-7,9-10-11....就是在第一輪的基礎上,往兩個骨牌中間添加一個,但是要保證添加而形成的新的cluster不相鄰:

原來是1-3 5-7 9-11

添加2 6 10 可以保證最佳的不相鄰程度,在這輪添牌出問題後,只需恢復1(+1)個骨牌

形成新的 cluster:1-2-3 5-6-7 9-10-11 13-14-15

同理第三輪如下:

1-2-3-4-5-6-7,9-10-11-12-13-14-15.......

以此類推直到全部擺放完成.

這個演算法的思路是想保證每次添加新骨牌,它因失誤倒下而影響的骨牌數都是最少的情況.

大概是每一步是局部最優，至於是不是全局最優還需要進一步思考.

============

更新：這個演算法得到的期望數量級肯定比 $n^2$ 少,估計了一下大概是 $n*log_2{n}$ .事實上,按從左到右順序擺放骨牌的這種基本排法,其期望數量級就是 $n^2$ .這還是不算條件概率的,算上條件概率的話還要少.

所以我覺得另外一個答案估算的期望數量級是不是有點問題....

想了一種動態規劃的辦法，不過發現算不下去。本來不準備放出來的，@sqybi 可以幫忙看一下么？

假設 $E(a,b,c)$ 代表左邊已經擺好a塊連續的骨牌，還需要在右邊擺b塊骨牌，且最後一塊放在c（ $1le cle b$ ）的期望擺放次數。

因為最後才放c，在放c之前左邊和右邊的擺放是獨立的，期望的步數為 $min_{1le i le c-1} E(a,c-1,i) + min_{1le i le b-c} E(0,b-c,i)$ 步。

然後關鍵的時刻到了，我們需要擺放第c塊骨牌，此時這個位置的左邊有連續a+c-1塊骨牌，右邊有b-c塊，所以從放下最後一塊骨牌到徹底擺好的期望步數為（注意這個問題是左右對稱的）

$1+pcdot min_{1le i le a+c} E(b-c,a+c,i) + p cdot min_{1le i le b-c+1} E(a+c-1,b-c+1,i)$

將兩個式子加起來得到

$egin{aligned} E(a,b,c)=min_{1le i le c-1} E(a,c-1,i) + min_{1le i le b-c} E(0,b-c,i)\+1+pcdot min_{1le i le a+c} E(b-c,a+c,i) + p cdot min_{1le i le b-c+1} E(a+c-1,b-c+1,i) end{aligned}$

但這個動態規劃貌似沒法歸化到若干基本情形，而是已知n-1塊牌的結論，n塊牌的情形變成解一個n元的方程組……（式子左邊的項和式子右邊最後的兩項都在「前兩項相加等於a+b」這條對角線上）

-------------看到了 @王贇 Maigo 的simulation之後的想法---------------------

看到了王贇的simulation結果，感覺 Last move/Total move的趨勢線的斜率很接近黃金分割比。然後就聯想到了按黃金分割比尋找單峰函數最大值的方法。

猜測極限情況下，最後一塊位置大概在0.618n左右。這樣如果擺了最後一塊後往少的一側倒，就重新擺少的一側，最後一塊位置不變。往多了一側倒就把多的一側重新按0.618 0.382 分，最後一塊放在整個區間0.618*0.618 ~0.382處。此時剩下的部分相當於我們已經擺好的比較長的區間中比較長的一段。

然後關於總的時間，如果p固定，那麼隨著n增大會是n的多項式時間，指數項取決於p。

提到動態規劃我覺得可以用一個參數搞定

DP(n)表示擺放連續n個骨牌需要的期望擺放次數

我們先假設我們最後一次擺放骨牌的位置是確定的（我們之後將會證明這件事情）

然後我們計算DP(n)

先計算我們擺放左邊k，右邊m個骨牌（k+m+1=n）

其期望為：((DP(k)+DP(m))/2+1)*(1/(2p)-1)+DP(k)+DP(m)+1

所以我們的DP方程就很容易得到了，直接枚舉k算最小值就好了

注意到我們的最終最小值只與DP(k)+DP(m)的和有關，所以如果我們能夠證明這個DP函數是凸的，就能得到 @思無邪SyiMyuZya答案中的結論了。。。

（然而這個是凸的感覺非常顯然但是我不會證）

接下來我們證明最開始的假設：最後一次擺放骨牌的位置是確定的，這種情況下可以達到最優解

否則，我們不妨設前兩次擺放的位置不同k1，k2

那麼，我們認為k1 k2都是當前情況下的最優解

即k1擺下後，有一邊倒了（不妨假設為左邊倒了），然後我們的最優位置變為k2

那麼如果我們在k1沒有放之前，只擺好了k1右邊，那麼此時最優位置為k2

故可以知道k2也是最開始的最優解

所以我們知道，k2是不會優於k1的，於是k1也可以作為k2的解

所以我們可以如數學歸納法證明所有的最優解都可以是k1

（多圖預警）

（6月2日大幅度修改答案）

這道題並不簡單。

最初的時候，我想的是類似於二分的策略：留出最中間的位置，先把左右兩邊分別擺好，再把最後一張牌插到中間去。這樣想的理由是：擺左右兩邊時互不影響，擺中間那張時最多倒一半。至於左右兩邊的擺法，可以用相同的思路遞歸下去。

其實只想到這裡，思路並不完整。如果擺最後一張牌的時候倒了，恢復的時候就不那麼容易了。假設我們要擺100張牌，最後擺的是第50張，另外99張牌擺的時候都沒有倒。現在恰好這第50張倒了，並且碰倒了左邊的49張牌。那麼如何恢復呢？這就有兩種策略：

沿用原策略——先把左邊49張牌恢復好，最後擺第50張牌；
對左邊的50張牌重新二分——先擺1~24，再擺26~50，最後擺25。

顯然，策略2可能有問題——擺26~50的過程中，可能把51~100也碰倒。

但策略1就是最優的了嗎？似乎也很難證明。

=====================

然後，我想到了動態規劃的思想。

用 $f(k)$ 代表擺好k張牌所需的擺牌次數的期望。

為了求 $f(k)$ ，可以把最後擺的那張牌的序號j看作決策。

於是有 $f(k) = min_{1 le j le k} f(j-1) + f(k-j) + 1 + p cdot [ ldots ]$

式中，右邊的 $f(j-1)$ 代表擺好左邊j-1張牌所需的次數（的期望，下略）， $f(k-j)$ 代表擺好右邊k-j張牌所需的次數，1表示擺最後這張牌所必需的次數，後面的p乘以某個東西代表如果最後這張牌碰倒了左邊或右邊的牌，就需要額外擺的次數。

問題來了：如果最後一張牌碰倒了左邊或右邊的牌，剩下的問題並不是原問題的子問題，而是原問題的推廣：要緊挨著若干張牌再擺一些牌，期望的擺牌次數是多少。

那麼我們重新定義狀態：用 $g(k,i)$ 表示總共要擺k張牌，其中最後k-i張已擺好，擺剩下的i張牌所需的擺牌次數的期望。或者說，緊挨著k-i張牌再擺i張牌，期望的擺牌次數是多少。 $f(i) = g(i,i)$ 。

這樣就可以寫出狀態轉移方程了：

$g(k,i) = min_{1 le j le i} g(j-1, j-1) + g(k-j, i-j) + 1 + p cdot [g(k, j) + g(k, k-j+1)]$

式中，前3項的含義與之前相同；中括弧里的兩項，分別代表如果最後那張牌（第j張）碰倒了左邊、右邊時，還需的擺牌次數。

邊界條件為 $g(*,0) = 0$ 。

問題看似解決了，實則不然。

把 $g(k,i)$ 中的k看作階段。

上面這個狀態轉移方程中，右邊中括弧中的兩項跟左邊處於同一個階段。

也就是說，同一個階段的各個狀態是相互依賴的，並沒有拓撲序，不能依次計算。

由於min算符的存在，這些狀態也並不構成線性方程組。

怎麼辦呢？那就只好迭代了。

在每個階段，初始時給每個狀態 $g(k,i)$ 都賦一個很大的初值，然後反覆使用狀態轉移方程使得各個 $g(k,i)$ 不斷減小，直到穩定。

只不過，這樣做的時間複雜度就無法估計了。

狀態轉移方程中有個min，如果把它換成argmin，就可以得到最優決策，記作 $h(k,i)$ 。

我最初的二分法思路，其實就是說 $h(k,k) = left lfloor frac{k+1}{2} ight floor$ 。

而倒牌之後的兩種恢復策略，用 $h(k,i)$ 表達則分別是：

$h(k,i) = i$ （只需對 $i = left lfloor frac{k+1}{2} ight floor$ 和 $i = left lceil frac{k+1}{2} ight ceil$ 成立）；
$h(k,i) = left lfloor frac{i+1}{2} ight floor$ 。

那麼究竟哪一種策略對呢？抑或是都不對？且看計算結果。

評論中 @張雨萌觀察到， $h(k,i)$ 常常不是唯一的。

一般情況下，會存在一整段的j，使得狀態轉移方程右端的值都相等且最小（未經證明）。

在修改答案之前，我只是簡單地方程右端取最小值。

由於浮點誤差的存在，最小值的下標就存在隨機性，而我所觀察到的「混沌」現象，正來源於此。

現在我為浮點誤差設置了一定的容錯量，並考慮使狀態轉移方程右端取得最小值的最小的j和最大的j，分別稱之為 $h_ ext{min}(k,i)$ 和 $h_ ext{max} (k,i)$ 。

=====================

下面這是p = 0.01（倒牌概率很小）的情況。

第一行的第一個圖是擺牌期望次數 $g(k,i)$ ，縱軸是k，橫軸是i。

第二行的第一個圖是上圖的對角線，即 $g(k,k)$ 。

第一行的第二、三個圖分別是最後一張牌編號的上下界 $h_ ext{min}(k,i)$ 和 $h_ ext{max} (k,i)$ 。

第二行的第二個圖是上面兩個圖的對角線，即 $h_ ext{min}(k,k)$ 和 $h_ ext{max} (k,k)$ ，以及 $h(k,k) = left lfloor frac{k+1}{2} ight floor$ 。

我們來慢慢分析。

先看左上的 $g(k,i)$ 圖。圖中的條紋基本是豎著的，這說明擺牌期望次數 $g(k,i)$ 基本由i（還需擺牌的張數）決定——反正倒牌概率很小，已經擺好的牌對擺牌期望次數的影響不大。

再看左下的 $g(k,k)$ 圖。擺牌期望次數隨牌數基本線性增長，且 $g(k,k)$ 略大於k，十分合理。

再看右下的 $h_ ext{min}(k,k)$ 、 $h_ ext{max} (k,k)$ 圖。圖形很有規律：

它由一個接一個的平行四邊形在頂點處相連構成，每個平行四邊形的邊長是上一個的2倍。
各個平行四邊形橫邊的縱坐標都是2的冪，相連的頂點的橫坐標是2的冪減1。
$h(k,k) = left lfloor frac{k+1}{2} ight floor$ 是夾在這些平行四邊形內部的。

這說明，最後一張牌有多種最優選擇，只要別偏離中心太遠就可以。而「二分」式地選擇最後擺最中間的牌，確實是一種最優策略。

最後看右上方最複雜的 $h_ ext{min}(k,i)$ 、 $h_ ext{max} (k,i)$ 圖。我們發現它們似乎是由許多漸變三角形層疊而成的。

最大的那一層（大約是 $i le 0.6k$ 的部分），有 $h_ ext{min}(k,i) = h_ ext{max}(k,i) = i$ 。

這個的意思是說，在總共需要擺k張牌，且已經擺好了一頭的至少0.4k張牌時，最好是把與這些牌緊鄰的位置空出來最後擺。這是一種比較保守的策略，目的是為了防止在第2步中碰倒已擺好的牌。

這支持了第1種倒牌恢復策略（ $i = left lfloor frac{k+1}{2} ight floor$ 和 $i = left lceil frac{k+1}{2} ight ceil$ 都在這一層內，k=2和4時有點小例外，不過不影響結論），而推翻了第2種倒牌恢復策略。

除了最大的那一層以外的部分（大約是 $i>0.6k$ 的部分）， $h_ ext{min}(k,i)$ 與 $h_ ext{max} (k,i)$ 往往相差很大。

這個的意思是說，如果已經擺好的牌只佔很小一部分，我們可以不用來故意保護它們。最後一張牌擺哪一張，這個選擇的自由度很大。

不過，在第1種倒牌恢復策略中，不會遇到這種情況。

=====================

先不要急著下結論，我們來看看倒牌概率取其它值的情況。

p = 0.1：

p = 0.2：

p = 0.3：

p = 0.4：

p = 0.45：

p = 0.49：

隨著倒牌概率的增大，我們可以觀察到如下變化：

左上 $g(k,i)$ 圖的條紋由豎的慢慢變成橫的，即 $g(k,i)$ 從主要由i決定變成主要由k決定。

這很容易理解：倒牌概率大了之後，擺牌是舉步維艱的，一不小心就會把之前的牌都碰倒。這樣，最初擺好了多少張牌就不重要了（反正一會兒都要倒），重要的是一共要擺多少張牌。

左下 $g(k,k)$ 圖呈現出了分段線性，拐點都是2的冪。這很有意思。

右下 $h_ ext{min}(k,k)$ 、 $h_ ext{max} (k,k)$ 圖一直沒有變化！這說明二分的思路一直是對的。

右上 $h_ ext{min}(k,i)$ 、 $h_ ext{max} (k,i)$ 圖變化不大，最顯著的變化就是層與層之間的邊界（尤其是最大層的邊界）由曲線變成和折線。

幸運的是， $i = left lfloor frac{k+1}{2} ight floor$ 和 $i = left lceil frac{k+1}{2} ight ceil$ 一直都是包含在最大層里的，所以倒牌恢復策略1是一直得到支持的。

=====================

總結一下：雖然未經證明，不過通過動態規劃計算，我們有較大的把握認為「二分法+倒牌恢復策略1」是使得擺牌期望次數最少的一種方法。

具體來說，是這樣：

若總共需要擺k張牌，則用二分法空出第 $left lfloor frac{k+1}{2} ight floor$ 個位置，先把左右兩邊都擺好，再把空位填上。擺兩邊的時候，使用同樣的方法遞歸進行。
若擺最後一張牌時碰倒了一側的牌，則先把被碰倒的牌恢復好（同樣用二分法），再把最後一張牌擺上。

=====================

附動態規劃及畫圖的Matlab代碼：

n = 100; p = 0.01; % 可修改 cost = zeros(n,n); decision_min = zeros(n,n); decision_max = zeros(n,n); for k = 1:n cost(k, 1:k) = 9e19; % 若想找虐，可繼續改大 change = true; while change change = false; for i = 1:k a = [0, diag(cost(1:i-1, 1:i-1))"]; b = fliplr([0, diag(cost(k-i+1:k-1, 1:i-1))"]); c = cost(k, 1:i); d = cost(k, k:-1:k-i+1); s = a + b + 1 + p * (c + d); m = min(s); if m &< cost(k,i) cost(k,i) = m; idx = find(abs(s - m) / m &< 1e-10); % 1e-10是浮點容錯量 decision_min(k,i) = idx(1); decision_max(k,i) = idx(end); change = true; end end end end clf; subplot(2,3,1); imagesc(cost); xlabel("Remaining"); ylabel("Total"); title("Expected moves"); colorbar; p1 = get(gca, "Position"); subplot(2,3,2); imagesc(decision_min); xlabel("Remaining"); ylabel("Total"); title("Last move (min)"); colorbar; p2 = get(gca, "Position"); subplot(2,3,3); imagesc(decision_max); xlabel("Remaining"); ylabel("Total"); title("Last move (max)"); colorbar; subplot(2,3,4); plot(diag(cost)); xlabel("Remaining = Total"); ylabel("Expected moves"); p = get(gca, "Position"); p(3) = p1(3); set(gca, "Position", p); subplot(2,3,5); hold all; plot(diag(decision_min), "b"); plot(floor(((1:n) + 1) / 2), "r"); plot(diag(decision_max), "g"); xlabel("Remaining = Total"); ylabel("Last move"); p = get(gca, "Position"); p(3) = p2(3); set(gca, "Position", p); legend({"Min", "floor((k+1)/2)", "Max"}, "Location", "NorthEastOutside");

其實我強烈懷疑用動態規劃解法的答案啊，不過運籌學得少，說不出哪裡不對，可能有兩個問題：

第一，最優擺法的路徑是不是唯一的？我覺得不是。

第二，骨牌倒了之後面對的還是不是原來的問題？我覺得也不是。

好吧，以上都是感性認識，胡亂扯扯，下面試著寫點兒。

——————————————————————————————————————

我就先用概率論的方法硬解吧，看能解到哪一步：

$n=1$ ：

即在左右緊鄰連續骨牌數為 $left( 0,0 ight)$ 的空位擺一張成功的期望次數 $E(0,0)=frac{1}{1-2p}$

$n=2$ ：

設在左右緊鄰連續骨牌數為 $left( 1,0 ight)$ 或 $left( 0,1 ight)$ 的空位擺一張成功的期望次數為

$Eleft( 1,0 ight) = Eleft( 0,1 ight)$ ，有如下方程： $Eleft( 1,0 ight) =1 * left( 1-2p ight) + left(Eleft( 1,0 ight) + 1 ight) * p + left(Eleft( 1,0 ight) + Eleft( 0,0 ight) + 1 ight) * p$ 代入已知的 $E(0,0)=frac{1}{1-2p}$ ，可以得到： $Eleft( 1,0 ight) = Eleft( 0,1 ight) =frac{1-p}{left( 1-2p ight) ^2}$

——————————————————————————————————————

按這個思路，核心問題是解 $Eleft( m,n ight)$ ，但 $Eleft( m,n ight)$ 的計算過程中涉及到尋優問題，不過尋優問題里涉及的 $Eleft( x,y ight)$ 滿足 $x<m,y<n$ 倒是真的，先推到這兒佔個坑。= =|

這個不可能求得出準確數來，讓計算機模擬模擬就行了，因為即使最簡單的2分策略，生成函數一看也就知道不是初等的。

對塊數足夠大時的極限行為有估計我還是比較相信的。

更不好辦的是，一塊倒了之後帶倒一片，擺回去的策略可能就不是原來那個了，

寫一個擺法，假設有15塊，不倒的時候應該是這個順序

1.3.2.5.7.6.4.9.11.10.13.15.14.12.8

-----------------------------------------

經過簡單的考慮，對於特定的塊數，擺回去就是用原策略，這個應該是可以計算的。

搞定了，回去再寫，先舉個例子，p=1/3，期望的數量級大約在5/6*O(n^2)

知乎小透明，也對多米諾骨牌從來沒有了解，只是一種設想讓他如何不倒，

如果桌面是電磁鐵的，而骨牌添加一定磁性(磁力多大根據需要調整)，達到盡量在擺放完之前不會碰倒的效果呢

加熱後可揮發的膠等原理亦可，只是一種設想，就是，暫時粘住嘛~

不喜可以噴

一個人擺的話，每二十個空一段，或者指定個數空一段，避免雪崩。

多人擺，思路一樣。