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

看板Grad-ProbAsk作者polomoss (小澤)時間16年前 (2010/02/20 18:17)推噓0(0推 0噓 14→)

留言14則, 2人參與討論串7/8 (看更多)

: 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

02/20 18:27, , 1^F

02/20 18:27, 1^F

→

taitin

02/20 21:33, , 2^F

02/20 21:33, 2^F

→

taitin

02/20 21:34, , 3^F

02/20 21:34, 3^F