目錄
1. 問題描述
2. 思路2
2.1 從鬼腳圖出發進行變形
2.2 反向變換
2.3 進一步探索
3. 小結
1. 問題描述
參見程式員的演算法趣題Q56: 鬼腳圖中的橫線(思路1)
2. 思路2
仍然考慮圖1的{1234-->3421}的例子，
在之前的討論中我們已經得到了{1234-->3421}的兩個鬼腳圖連線方式，如下圖所示的(2.2.2)和(2.3.1)，
2.1 從鬼腳圖出發進行變形
考慮將橫線縮為一個點進行變形（類似于拓撲學中的那種變形）會得到什么呢？如下圖所示：
圖1
進一步將線扯扯直，讓每一對Uk—Dk的路徑變成直線，我們會發現以上圖(A)和圖(B)會得到相同的圖，如下圖所示（先扯直U1-D1, U3-D3, U4-D4，得到(C)，然后再挪動以下位置將U2-D2也扯直得到(D)，以下我們稱這種圖為交叉圖）：
圖2
這個意味著什么呢？是不是意味著原問題可以轉變為“上下兩排之間對應數字之間連線，求最小的交叉點的個數”的問題呢？
下面我們來進一步探索，
2.2 反向變換
注意，從以上圖(D)的交叉圖出發遵照前述鬼腳圖的規則是可以恢復出原鬼腳圖的（恢復的方法參見以下說明），下面我們從一個一個與圖(D)略微不同的交叉圖(E)（這種不同僅僅在于上下兩排點的相對間距不同導致直線連接后的交叉點的位置不同而已）出發看看反向能恢復出什么來，
首先從U1（記得前面我們提過U表示Upper，D表示Down，Uk表示上邊的k節點，Dk表示下邊的k節點）出發，因為U1到D1經過(1)，(2)，(3)三個交叉點，我們知道每個交叉點對應一條橫線，因此可以先畫出三條橫線，而且橫2位置在橫1之下，橫3在橫2之下，
接下來，考慮U2的路徑，U2的路徑先碰到交叉點(4)，對應鬼腳圖上橫4的線，但是橫4是應該往左畫還是往右畫呢？首先橫4必然是在橫2上面（如果不是的話，U2出發后就應該先碰到交叉點(2)）；其次，如果往左畫的話，要么在橫1上面，要么在橫1下面，在橫1下面畫不行，因為這樣破壞了U1的路徑，在橫1上面畫也不行，因為這樣的話，U2在(4)之后就應該是碰到(1)而不是如左圖中的(2)，所以，橫4只能是往右畫，而且必須在橫1上面，然后，U2在(4)之后碰到(5)，這對應著在右圖需要追加一條新的橫5，顯然它只能往右畫（因為D2在右邊）而且必然在橫3下邊（不然的話U2在(4)之后就會碰到(3)），
接下來，考慮U3的路徑，此時圖上已經有了橫1，2，3，4，5，很顯然U3經過(4)和(1)可以到達D3，這個在作圖和右圖都成立，因此不需要追加新的橫線，
接下來，考慮U4的路徑，左圖中U4先碰到(3)然后是(5)，右圖上也已經存在這一條路徑了，
圖3
好了，大功告成，我們的確從一個新的交叉圖恢復出了對應的鬼腳圖，而且，surprisingly，這個鬼腳圖與我們之前的討論所得到(2.2.2)和(2.3.1)都不同，我們得到了一個新的鬼腳圖！
2.3 進一步探索
如上所述，圖(D)和圖(E)的差異僅在于上下兩排節點的間距稍微不同而已，進一步，顯而易見的是，不管從圖(D)出發還是從圖(E)出發，總可以使得多個交叉出現重疊，這種情況意味著什么呢？還能不能恢復出對應的鬼腳圖，重疊的交叉點算多個點還是算一個點？如果算一個點的話，是不是意味著出現了橫線更少的鬼腳圖呢？
圖4
如上圖所示，在圖(G)中，經過調節上下兩排點的相對間隔后，交叉點(1)（2）（4）重疊了，讓我們看看基于這個圖能恢復出什么來？
首先從U1出發，因為U1到D1經過(1-2-4)（代表上圖中三條線公共交叉點）和(3)，我們知道每個交叉點對應一條橫線，但是如果把(1-2-4)看作一條橫線的話，那么在U1和D1之間只有兩條橫線，而在鬼腳圖中U1和D1之間隔著3格，不可能只經過兩條橫線到達，由此我們知道多重交叉點必須看作是多個交叉點，不能看作是一個，因此我們仍然把(1-2-4)看作是(1)和(2)和(4)（編號是無所謂的），那么U1到D1的路徑可以是(1)-(2)-(3)也可以是(1)-(4)-(3)，由于編號是無所謂的，不失一般性，我們就仍然考慮是(1)-(2)-(3)，這樣的話我們仍然可以先畫出三條橫線，而且橫2位置在橫1之下，橫3在橫2之下，(這個與上一節相同)
接下來，考慮U2的路徑，此時圖中已經有了橫1、橫2和橫3，由于是三個重疊的交叉點，U2的路徑是算碰到(1)和(2)和(4)中的哪個呢？顯然(2)可以排除，因為橫2在橫1下面，U2不可能在遇到橫1之前先碰到橫2，
考慮U2先碰到的是交叉點(4)，對應鬼腳圖上橫4，那么必然有橫4在橫1上面，但是橫4是應該往左畫還是往右畫呢？首先橫4必然是在橫2上面（如果不是的話，U2出發后就應該先碰到交叉點(2)）；其次，如果往左畫的畫，要么在橫1上面，要么在橫1下面，在橫1下面畫不行，因為這樣破壞了U1的路徑（與上一個例子的道理相同），在橫1上面畫呢也不行，因為這樣U1就會先碰到橫4因而破壞了U1的路徑，結論是橫4不能往左畫，只能是往右畫，而且必須在橫1上面，然后，U2在(4)之后碰到(5)，這對應著在右圖需要追加一條新的橫5，顯然它只能往右畫（因為D2在右邊）而且必然在橫3下邊（不然的話U2在(4)之后就會碰到(3)），
接下來，考慮U3、U4的路徑就和上一節的例子一樣了，由此得到了圖(H)，其實和圖(F)是相同的，
本節的討論得到的結論是，多重交叉點必須作為多個不同的交叉點來處理，這樣我們仍然可以恢復出對應的合法的鬼腳圖，
3. 小結
今天的討論感覺前進了一大步，問題似乎轉變成了一個更容易進行演算法處理的問題，不過我仍然沒有完全想清楚這種對應意味著什么，目前也沒有能力給出稍微嚴謹一點的數學證明，隱隱約約覺得這個跟圖論（或甚至拓撲學）中的東西有關聯？暫且貼出來看看有沒有高手能夠指點一下^-^.
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/353303.html
標籤：其他