| 查看: 729 | 回复: 2 | |||
vampireslg金虫 (小有名气)
|
[求助]
有向图的一条路径服从什么分布 ？
|
|
假设有这样一个有向连通图Ｇ，它存在一个起始点，多个终结点，从起始点出发往前走，每走下一步都是随机选择的（注：是有向图，只能从后继结点中选择），一旦抵达任意一个终结点就停止往前走。 假设这个图非常大，对应了很多个路径。设某一条特定的路径为 t ，那么我在采集了N条（比如100万条）路径后仍然没有采到这条路径 t 的概率Pr(t)要怎么估计 ？ 注： １. 我事先并不知道原图中有多少条路径，也没法估计有多少，只知道有很多，暴力枚举所有的路径不能实现。 ２．每条路径出现的概率不是均等的，因为图的结构可以会导致某些路径出现在概率高于其他路径 ３. 假设图中是没有那种进去就出不来的强连通分量或者没有后继的非终结节点，这样可以保证从初始点出发必须会在有限步到达某个终结点 举个例子： 比如下图（实际情况中图形远比这个大），A是起始点，假设K, L是终结点。 我随机采集路径，采了100条，依然没有采到 A ->B -> D -> G -> C -> D -> E -> H -K 这条路径的概率怎么估计 ？  digraph-2.jpg |
回复此楼» 猜你喜欢
» 本主题相关价值贴推荐，对您同样有帮助:
关于白噪声滤除问题
已经有12人回复
- 关于matlab中的plot描点画线问题
已经有4人回复
- 第一性原理如何描述化学反应动力学？
已经有21人回复
feixiaolin
荣誉版主 (文坛精英)
-
专家经验: +518 - 应助: 942 (博后)
- 贵宾: 1.275
- 金币: 3430
- 散金: 58785
- 红花: 532
- 沙发: 11
- 帖子: 24215
- 在线: 2601.8小时
- 虫号: 2139575
- 注册: 2012-11-21
- 专业: 光学信息获取与处理
- 管辖: 数学
2楼2014-11-16 20:21:22
vampireslg
金虫 (小有名气)
- 应助: 0 (幼儿园)
- 金币: 1444.6
- 散金: 5
- 红花: 11
- 帖子: 177
- 在线: 59.2小时
- 虫号: 1430582
- 注册: 2011-10-07
- 性别: GG
- 专业: 计算机科学的基础理论
3楼2014-11-17 07:50:04
