作者leosnake (尼歐)
看板Grad-ProbAsk
標題[理工] 102 台大 演算法
時間Mon Jan 20 21:54:42 2014
http://exam.lib.ntu.edu.tw/sites/default/files/exam/graduate/102/102415.pdf
請問一下第三題(a)
如果n=2，也就是 binary tree ，可以用矛盾證明。
但是n>2 時，命題就不一定成立了。
考慮n=3的case, 假設T為 C={x,y} 的optimal decoding tree，
則T會長這樣：
root
/ \
x y
如此T並非full ternary tree(3-ary tree)。
也就是說，當要壓縮的字元數量少於n時，optimal decoding tree T好像不會是
full n-ary tree.
以上小弟的想法是對或錯，請各位大大指教:)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.228.177.23
※ 編輯: leosnake 來自: 61.228.177.23 (01/20 21:56)
※ 編輯: leosnake 來自: 61.228.177.23 (01/20 21:59)
※ 編輯: leosnake 來自: 61.228.177.23 (01/20 22:00)
→ kiki86151:照你這樣想 那麼二元可以假設T為C={x}來反駁= =? 01/21 01:34
→ leosnake:binary traa的話，把C={x} 的x直接當root 就好 01/21 07:09
→ leosnake:不過好像也有點怪吼 因為這樣就沒有decode了 01/21 07:11
→ leosnake:所以是否應該要加個邊界條件，壓縮的字元數大於等於n？ 01/21 07:14
→ kiki86151:覺得它跟2元一樣有OBT 就找最佳解一定有Greedy choice 01/21 11:46