作者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/cn.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