Re: [理工] [資結]-台大98-軟體設計 對答

[polomoss (小澤)]

: 5.
:  (1) B

請問Huffman code algo.是用什麼實作?(queue/stack/tree/heap?...etc)
就是這題要怎麼改才對~?

:  (2) B
: 6.
:  (1) L(u,w)+d(v,u)-d(v,w)>= 0
:   -> d(v,w)>=d(v,u)+l(u,w)
             ^^^
             <=
:   由題目可知d(v,w)為一最短路徑from v to w
:   若 此最短路徑經過u
:   則d(v,w)=d(v,u)+l(u,w)
:   若 最短路徑不經過u
:   則表示 v~>u->w的路徑比較大
:   d(v,w)>d(v,u)+L(u,w)
         ^^^
          <
:   因此可証得 d(v,w)>=d(v,u)+L(u,w)
                    ^^^^^
                     <=
   ---> L(u,w)+d(v,u)-d(v,w) >=0

:  (2)
: a.
:    在G中 假設有條路徑 p(u,v),由u經過x1,x2,...,xn到v
:    則p(w,x)=L(u,x1)+L(x2,x3)+...+L(xn,v)  ...(1)
:    已知在G'中 L'(w,x)=L(w,x)+s(w)-s(x)
:            L(w,x)=L'(w,x)-s(w)+s(x)
:    代入(1)得
:    p(u,v)=L'(w,x1)+L'(x2,x3)+...+L'(xn,v)-s(u)+s(v)
:    若假設G'中沿相同路徑稱為p'(u,v)，則
:    p'(u,v)=L'(u,x1)+L'(x2,x3)+...+L'(xn,v)
:    則
:    p(u,v)=p'(u,v)-s(u)+s(v)
: b.
:       已知在G中w,x有最短路徑d(w,x)屬於p(w,x)
:       且p(w,x)>=d(w,x)   (註 大於或等於)
:       由a知 G'中p(w,x)=p'(w,x)-s(w)+s(x)
:       因此 p'(w,x)-s(w)+s(x) >= d'(w,x)-s(w)+s(x)  (註 大於或等於)
:            p'(w,x)>= d'(w,x)
:       由此知d'(w,x)為一最短路徑且與d(w,x)相同

第二題可以解釋題意嗎? 有點看不懂~不知道問什麼


(3)
可以直接說A是bellman-ford  , B是Dijksta

因為Dijkstra不允許負邊存在，故A適合?

--
     ◤    ◥  答      ◤    ◥  拉      ◤    ◥  米      ◤    ◥  哆
   Σ ◆  ◆   蚊    Σ ◆  ◆   肥    Σ ◆  ◆   開    Σ ◆  ◆   啦
        ︵     吸         ︵     兒         ︵     喇         ︵     太
    ◣++++++◢        ◣++++++◢        ◣++++++◢ 雞     ◣++++++◢ 裸
◥▇▆@ ≡ @▆▇◤     Ψ ≡ Ψ          ▄ ≡ ▄  囉  ▄▄▄ ≡ ▄▄▄
        ▅                ▅          ▄/   ▅   \▄          ▅  ＡΓＶＩＳＳ

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 220.136.82.39
→ polomoss:t大可以順便解是一下第四題嗎? 其實也不是很懂題意
→ taitin:第四題簡單說就是問你，當插入點沒有祖父時，為什麼不用
→ taitin:handle 紅紅衝突Y
→ taitin:huffman不是binary search tree 的PQ
→ taitin:第六題打反了XD感謝提醒
→ taitin:第二題是 Johnson'algo
→ taitin:reweighting 演算法課本 541 25.3
→ taitin:http://en.wikipedia.org/wiki/Johnson's_algorithm
→ taitin:3.的話我覺得還是要解釋，不要直接說XXX算法，畢竟 10pts
→ polomoss:第四題的情況是只有兩點的時候嗎?? 就是可以允許兩個紅
→ polomoss:因為我在作紅黑樹，root都直接變黑色，所以正確作法是
→ polomoss:只有兩個點的時候還是紅紅嗎?第三個點插入才要調整?
→ polomoss:我知道huffman不是BST PQ，想問的是它應該是什麼?
→ polomoss:謝謝回答~^^