image-20240524114034544

假设每个用户都有一定的缓存，可以用来存储一些已经被播放过的文件。假设两个用户的缓存里有对方正在请求的文件，那么就可以用异或编码将用户请求的文件编成一个文件，然后再广播给用户，从而节省带宽资源。

1、那么某个时刻，给定每个用户缓存里的文件和用户要请求的文件，哪些文件应该被编码到一起？

image-20240524114539528

这就是一个最小团覆盖问题了。因此，作者设计了一个启发式算法进行求解。

2、其实用户的请求是不同步的，每时每刻都在有用户到达和用户离开。用户离开的影响不大，因为从团里面删除一个顶点，剩下的还是一个团。用户到达就需要重新求解最小团覆盖问题。由于重新求解的代价比较大，所以设计了一种启发式方法来解决新用户到达后的团划分问题。

3、其实推荐列表里的文件顺序是可以改变的，从而进一步压榨出编码传输的机会。作者设计了一个排序方法来配合前面的两个算法，进一步找到编码传输的机会。

image-20240524115614596

4、缓存里的内容应该怎么更新？缓存的文件的作用是，当其他用户请求这个文件时，可以有编码传输的机会，那么这个文件的价值就和其他用户什么时候请求这个文件有关。