算法学习---概率与期望

本文主要是介绍算法学习---概率与期望，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

根据期望的线性性质，

(E[aX +bY]=aE[X] + bE[Y]) 。所以另外一种求期望的方式是分别求出每一种代价产生的期望贡献，然后相加得到答案。在本题中，路径期望总长度等于每条边产生的期望贡献之和。而每条边产生又等于经过这条边的期望次数乘这条边的代价。所以，我们只需要算每条边的期望经过次数即可。

((u,v,w)) 的期望经过次数是不好直接算的，但如果我们能算得点

(u) 的期望经过次数为

(dp(u,v)) ，那么边

((u,v,w)) 的期望经过次数是

(dp(u)*\frac1{|G_u|}) ，对答案的贡献就是

(w*dp(u)*\frac1{|G_u|})

如何计算点

(u) 的期望经过次数

(dp(u)) 呢？我们依然考虑 DP 的方式，首先有

(dp(u) = 1) ，转移采取刷表的方式：

[dp(e_{to})\leftarrow dp(u)*\frac1{|G_u|},e\in G_u ]

在用边

(e) 刷表的同时，边

(e) 的贡献就可以计算了，十分简洁。因为这种方法计算答案十分的便捷，而且适用范围广，所以这种『利用期望的线性性质，单独计算贡献的方法』是我们计算期望首选的方法。

typedef long long ll; inline int readInt() { static int n, ch; n = 0, ch = getchar(); while (!isdigit(ch)) ch = getchar(); while (isdigit(ch)) n = n * 10 + ch - '0', ch = getchar(); return n; } const int MAX_N = 100000 + 3, MAX_M = MAX_N * 2; struct edge { edge *next; int to, cost; edge(edge *next = NULL, int to = 0, int cost = 0): next(next), to(to), cost(cost) {} } pool[MAX_M], *pit = pool, *first[MAX_N]; int n, m, deg[MAX_N], outDeg[MAX_N]; double f[MAX_N]; void solve() { static int q[MAX_N]; int l = 0, r = 0; q[r++] = 0; double ans = 0; f[0] = 1.0; while (r - l >= 1) { int u = q[l++]; for (edge *e = first[u]; e; e = e->next) { f[e->to] += f[u] / outDeg[u]; ans += f[u] * e->cost / outDeg[u]; if (--deg[e->to] == 0) q[r++] = e->to; } } printf("%.2f\n", ans); } int main() { n = readInt(), m = readInt(); for (int i = 0, u, v, w; i < m; ++i) { u = readInt() - 1, v = readInt() - 1, w = readInt(); first[u] = new (pit++) edge(first[u], v, w); deg[v]++, outDeg[u]++; } solve(); }

这篇关于算法学习---概率与期望的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！