作者dsa66253 (Kobe Mary)
看板Grad-ProbAsk
標題[理工] WEPL 與 OPST差別
時間Thu Jan 23 23:36:05 2020
如題 Weighted external path length與optimal binary size search tree 差別在哪？
我知道他們都是給一個表格 寫著各點的值
然後WEPL是求出 最小的external path的總和
而OBST求出的是整顆樹的cost最小。前者是greedy 後者為DP
但就是說不上來 他們到底差在哪...好像有關係，又沒有關係，也不知道盲點在哪。請問
有人有對他們更深的了解嗎？或者說我不知得他們兩的應用在哪
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 150.117.242.146 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1579793767.A.E86.html
1F：→ gash55025502: 前者的考點幾乎都在Huffman 不太會跟OPST一起出現01/24 00:26
2F：→ dsa66253: 我想了想obst好像是為了要找搜尋成本低 也就是搜尋次數01/24 00:33
3F：→ dsa66253: 少的樹？但WEPL?01/24 00:33
4F：推 ekids1234: obst 考慮內部節點01/24 03:07
5F：推 mistel: 整個定義都不一樣了吧 WEPL是走到外部節點的路徑數 OBST01/24 06:57
6F：→ mistel: 是到各節點的高度權重和01/24 06:57
7F：→ dsa66253: 是不是兩個都是搜尋成本的指標 WEPL是一定會走到externa01/24 19:31
8F：→ dsa66253: l node，OBST被搜尋的點可能會在internal node01/24 19:31
※ 編輯: dsa66253 (27.247.0.243 臺灣), 01/24/2020 19:32:12
9F：推 mistel: 嗯嗯我覺得應該是這樣 01/24 20:39