作者ShenJing (ShenJing)
看板Grad-ProbAsk
標題Re: [理工] 請益 演算法兩題(成大99, 103)
時間Fri Jan 5 18:10:44 2018
部分恕刪，另外在這邊告知一下原po
我在我這篇標題有雞婆加上學校年份，以供未來有需要的人也可以搜到
還請原po見諒
※ 引述《leexu3 (LEE)》之銘言：
: 成大的99年Checkboard
: https://imgur.com/a/rLdeR
: 1.寫不出code 雖然感覺很明顯對 ＝＝
不知道這樣寫pseudo code可不可以：
// size: 記錄大小為2^n * 2^n之checkerboard的n
function board_cover(board bd, size n):
// 若只剩大小為2 * 2之checkerboard，
// 根據我們的做法，必定當中已有1 * 1的square不可cover，
// 等同被移除一塊square
if size == 1:
將一個tromino覆蓋剩餘區域;
return;
else:
將大小為2^n * 2^n之checkerboard劃分為4塊大小為2^n-1 * 2^n-1的board;
分別標記為b1, b2, b3, b4;
判斷該4塊中哪塊board有存在1 square不可cover;
在2^n * 2^n之board的中心覆蓋上一個tromino，其覆蓋的區域各有1 square位在
其它「原不存在不可cover的1 square」的3大塊board;
// 如此一來，此時4大塊2^n-1 * 2^n-1的board各有1 square不可cover
// 遞迴對這4大塊board再去填滿tromino
board_cover(b1, n - 1);
board_cover(b2, n - 1);
board_cover(b3, n - 1);
board_cover(b4, n - 1);
return;
我覺得應該這樣大概寫出做法就可以了，可以的話再畫圖示意，
這樣閱卷老師應該會接受吧QwQ？
資料結構還有其他細節小弟我覺得應該不算此題重點，所以就沒詳述了
（用array存board、中心的index、如何判斷哪一塊存在不可cover的square）
若概念有問題或哪邊還可以寫得更不冗長，還請各位不吝指點，感謝！
: 成大103
: https://imgur.com/a/iFpp4
: Prove that "the longest increasing subsequence problem" can be reduced
: to "the edit distance problem"
: 兩個演算法我會 但不知道怎麼reduced 感覺就是有讀沒有通
: 想上來請益各位 謝謝！
不好意思這題最後的細節我也不清楚
（有了min cost的編輯序列，該如何用這序列去求出LCS，也就是LIS），
以下前段主要來自於林立宇老師的演算法講義
假設LIS中input sequence為X = (7, 4, 1, 2, 6)
對X排序，可得sequence Y = (1, 2, 4, 6, 7)，則求LIS(X)又等同求LCS(X, Y)
再來看Edit distance problem(ED)
定義edit operation及其cost：
1. substitution，Cs = 2
2. insertion，Ci = 1
3. deletion，Cd = 1
題外話，我覺得「替代」的操作在此題reduce中似乎沒用到？（概念有錯還請指正）
接著是min edit cost與LCS length的關係
首先LIS(X) = LCS(X, Y) = (1, 2, 6)
假設為ED(X, Y)為要將X編輯成Y的min cost，
等同於在X中delete非LIS的元素（刪x1, x2的7, 4），接著同時對照Y
在X對應的位置insert被刪掉的元素（在2, 6間插4、在最尾端插7）
由上述例子可知，假設X的元素數量（|X|）為n，LCS元素數為|LCS(X, Y)|
則ED(X, Y) = 2 * (|X| - |LCS(X, Y)|)
所以當若給一input sequence X（也同樣是欲求LIS的X），
排序X得Y，接著先找出具有min cost的編輯序列，
再來我不太理解的是，該如何從這些insert、delete的operation中，
求出X和Y的LCS，也就是X的LIS呢？
林立宇老師的講義上只寫「欲求LIS(X)」，只需在過程中額外記錄一些編輯的程序即可
假設X = (4, 1, 2)，Y = (1, 2, 4)
min cost of edit sequence是從X刪除x1，插入y3到X，
那我們該如何從這兩個operation中，得知X的LIS就是(x2, x3)，也就是1, 2呢？
小弟的猜想是，最後的編輯序列求出後，
「只執行」編輯序列中delete的操作，一旦編輯序列中沒有delete，就output X的內容
值得一提的是，將substitution 視為等同 delete 再 insert，所以成本我設為相同
（2 = 1 + 1）
當最後有了編輯序列後，我將每個substitution都以「delete + insert」的操作取代
或者，一開始直接將substitution的cost設為無限大，
如此一來必不會有substitution的操作出現，即可正確輸出
（感謝FARXIS大耐心提出反例與盲點）
以上是我查過資料後的一些想法，還請大家有其他想法盡量提出、指正，
感謝！
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.26.141.161
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1515147047.A.89D.html
1F：推 FRAXIS: LIS(X) 等同求 LCS(X, Y) 是很顯然的 01/05 20:01
2F：→ FRAXIS: 但是 ED(X, Y) = 2 * (|X| - |LCS(X, Y)|) 你要說明 01/05 20:02
3F：→ FRAXIS: 為什麼你提的方式是 min cost？ 01/05 20:04
感謝F大提出一個我很大的盲點，確實這樣就說是min cost實在不顯然且不嚴謹
立宇老師講義上似乎也沒有提到這部分，我再思考看看
4F：推 FRAXIS: 而且嚴格來說 reduce 是針對 decision problem 的 01/05 20:06
5F：→ FRAXIS: 所以你只要把 LIS 和 ED formulate 成 decision problem 01/05 20:06
6F：→ FRAXIS: 應該就可以了 不需要真的找出解.. 01/05 20:07
原來如此！因為我是看到題目中，Output一個是edit operation的sequence
一個是longest sequence of positions，所以才想說是不是optimization problem
7F：推 FRAXIS: 如果真的要建構解 你的方法也不對 假設 X 已經排好序了 01/05 20:10
8F：→ FRAXIS: 也就是 Y = X，那 LCS(X, Y) = |X|, ED(X, Y) = 0 01/05 20:11
9F：→ FRAXIS: 並沒有所謂的一連串 insert.. 01/05 20:11
那我改成
「只執行」編輯序列中delete的操作，一旦編輯序列中沒有delete，就output X的內容
如此一來，儘管input X是sorted，當要輸出時一開始判斷也會因X沒有delete就Output
請問F大這樣可以嗎？
感謝F大耐心看我的想法並挑出許多瑕疵QwQ
10F：推 FRAXIS: 當 X = (3, 2, 1), Y = (1, 2, 3), LCS(X, Y) = 1 01/05 22:31
11F：→ FRAXIS: ED(X, Y) = 4, 因為是把頭和尾作 substitution 沒有delete 01/05 22:32
對耶！
那請問F大，因為 我將substitution 視為等同 delete 再 insert，所以成本我設為相同
（2 = 1 + 1）
所以為了讓我能以上述建構解的方法正確運作，
當最後有了編輯序列後，我將每個substitution都以「delete + insert」的操作取代
或者，我將substitution的cost設為無限大，如此一來必不會有substitution的操作出現
那請問建構解的部分這樣是否就可行了呢？
另外我google了幾篇有提到這兩者間轉換的文章，似乎都沒說明到為何可以是min cost
請問F大方便提點一下嗎？
※ 編輯: ShenJing (114.26.141.161), 01/06/2018 00:24:12
12F：推 FRAXIS: 因為 |X| = |Y|，所以任何 ED 的可行解 #insert = #delete 01/06 06:54
13F：→ FRAXIS: 所以要最小化 ED 就等於是要 min #delete 01/06 06:55
14F：→ FRAXIS: 所以就一定是 LIS 了.. 01/06 06:55
原來如此！非常感謝F大！
※ 編輯: ShenJing (114.26.141.161), 01/06/2018 07:39:27