[理工] WEPL 與 OPST差別

[dsa66253 (Kobe Mary)]

如題 Weighted external path length與optimal binary size search tree 差別在哪？
我知道他們都是給一個表格 寫著各點的值
然後WEPL是求出 最小的external path的總和
而OBST求出的是整顆樹的cost最小。前者是greedy 後者為DP
但就是說不上來 他們到底差在哪...好像有關係，又沒有關係，也不知道盲點在哪。請問
有人有對他們更深的了解嗎？或者說我不知得他們兩的應用在哪

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 150.117.242.146 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1579793767.A.E86.html
→ gash55025502: 前者的考點幾乎都在Huffman 不太會跟OPST一起出現
→ dsa66253: 我想了想obst好像是為了要找搜尋成本低 也就是搜尋次數
→ dsa66253: 少的樹？但WEPL?
推 ekids1234: obst 考慮內部節點
推 mistel: 整個定義都不一樣了吧 WEPL是走到外部節點的路徑數 OBST
→ mistel: 是到各節點的高度權重和
→ dsa66253: 是不是兩個都是搜尋成本的指標 WEPL是一定會走到externa
→ dsa66253: l node，OBST被搜尋的點可能會在internal node
※ 編輯: dsa66253 (27.247.0.243 臺灣), 01/24/2020 19:32:12
推 mistel: 嗯嗯我覺得應該是這樣