Skip to content

伸展树势能函数的设计方法 #45

@ClazyChen

Description

@ClazyChen

原始论文中并没有提到sum-of-log这个函数是怎么被设计出来的
我阅读了一些相关论文,也没有得到答案。目前有两个猜想:

  1. 来自信息论,每条边的权重log(A/B)等于查找过程中经过这条边时获得的信息量
  2. 待定势能函数,根据其需要满足的性质(比如可加性)反推得到
    目前拟在tutorial里使用猜想(1),这可能有助于学生理解这个函数的意义,但还是很难想象通过这种方式构造出sol势能函数

Metadata

Metadata

Assignees

Labels

help wantedExtra attention is needed

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions