Dotcpp  >  编程教程  >  图论  >  什么是树上随机游走?

什么是树上随机游走?

点击打开在线编译器,边学边练

什么是树上随机游走?我们可以假设给定一棵树,树的某个结点上有一个硬币,在某一时刻硬币会等概率地移动到邻接结点上,问硬币移动到邻接结点上的期望距离。


1. 树上随机游走用到的定义:

● 所讨论的树 所讨论的树

● 结点的度数结点的度数

● 结点与 v 结点之间的边的边权结点与 v 结点之间的边的边权

● 结点的父结点结点的父结点

● 结点的子结点集合结点的子结点集合

● 结点的兄弟结点集合结点的兄弟结点集合


2. 向父结点走的期望距离

树上随机游走代表 结点走到其父结点树上随机游走2的期望距离,则有:


 树上随机游走3

 

分子中的前半部分代表直接走向了父结点,后半部分代表先走向了子结点再由子结点走回来然后再向父结点走;分母树上随机游走代表从 u 结点走向其任何邻接点的概率相同。

化简如下:

树上随机游走

初始状态为初始状态

当树上所有边的边权都为 1 时,上式可化为:

树上随机游走

即 u 子树的所有结点的度数和,也即 u 子树大小的两倍-1(每个结点连向其父亲的边都有且只有一条,除 u 与pu之间的边只有 1 点度数的贡献外,每条边会产生 2 点度数的贡献)。


3. 向子结点走的期望距离

设 g(u) 代表pu结点走到其子结点 u 的期望距离,则有:

向子结点走的期望距离

分子中的第一部分代表直接走向了子结点 u,第二部分代表先走向了父结点再由父结点走回来然后再向 u 结点走,第三部分代表先走向 u 结点的兄弟结点再由其走回来然后再向 u 结点走;分母d(pu)代表从08.png结点走向其任何邻接点的概率相同。

化简如下:

向子结点走的期望距离

初始状态为树上随机游走

代码实现(以无权树为例)

vector<int> G[maxn];

void dfs1(int u, int p) {
  f[u] = G[u].size();
  for (auto v : G[u]) {
    if (v == p) continue;
    dfs1(v, u);
    f[u] += f[v];
  }
}

void dfs2(int u, int p) {
  if (u != 1) g[u] = g[p] + f[p] - f[u];
  for (auto v : G[u]) {
    if (v == p) continue;
    dfs2(v, u);
  }
}

知识点标签:


本文固定URL:https://www.dotcpp.com/course/1057

算法竞赛教程
第一章 算法基础
第二章 搜索算法
第三章 排序算法
第四章 字符串相关
第五章 数学相关
第六章 动态规划
第七章 数据结构
第八章 图论
第九章 计算几何
第十章 其他算法
Dotcpp在线编译      (登录可减少运行等待时间)