Title

目前的 RSS-I 不是批量的，就是一条条边算的。
图很小的时候，RSS-II 不好，RSS-I 好。因为 RSS-I 一条条算，可以直接判 0, RSS-II 一批批算，不能直接判 0,要用蒙特卡洛。
RSS-II 里之后选的边是可以包括之前的未定边的，肯定是有一个 scheme 让 RSS-II 等同于 RSS-I

TODO

测试自己实现的肥波那其堆，主要是内存和时间。 sum of shortest path 当作 influence LPS 加速，用最普通的堆，下沉操作

Idea

先考虑 s-t

1. BFS 出一个拓扑序，DAG 上 dp.
2. BFS+cascade
3. 迭代/随机游走
4. 点概率反推边概率？
5. 从 DAG 衍生，不相交路径容斥
6. 看看 landmark 排序，有一个改进 landmark pruned labeling 的
7. 看看 topk，弄一个含更多边的结构
8. 路径覆盖数量排序，或者 mia 那里覆盖数量排序
9. 树合并
10. 单点贡献排序？
11. 树拆分，查询时只合并链
12. 最短路链上点对就是最短路
13. 能否利用三角不等式相减那一边
14. 最短路覆盖时，n 棵 size 为 n 的树，没棵砍小

讨论

1. DAG dp 是不行的，因为前驱节点的存在概率不是独立的。如果只有 n 到 n+1 层也不可以。
2. 到一个点不相交路径可以容斥，但是很愚蠢。

Dataset

dblp: 2260138 6787979 (经过清理，原始边 1.4kw 条) avg prob 不用乘以 2，就用 log 里的
lastfm: avg prb 要乘以 2

RSS-II 原论文实验中使用了 r=50 的设置，但是原论文是在测试 varience, 实际上 50 条边的概率乘起来，再乘以不够大的采样数量，舍入误差偏大，实际实验中即使使用 10000 以上的采样数量，仍没有收敛到蒙特卡洛的值，所以我们根据收敛性调整，取偏小的 r，在 dblp 数据集中为。（放图） 用一个极端的例子说明这种情况，s 有 50 条出概率为 0.5 的出边，仅有 1 条以 1 的概率通到 t，用 rss 在采样数为 10000 时，每一个分层空间均为 $10000*0.5^50$ 答案因为舍入变成 0，但是实际概率为 0.5，在此例子下，只能将采样数量放大到 $2^50$ 的级别才能获得准确的值。 好了 上面这一段都是狗屁，加了一个 max(1, sample_n) 直接滚回正常收敛。

可以调的阈值，要加到结果文件名里。