24小时热门版块排行榜

返回列表

当前只显示满足指定条件的回帖，点击这里查看本话题的所有回帖

vampireslg

金虫 (小有名气)

应助: 0 (幼儿园)
金币: 1444.6
散金: 5
红花: 11
帖子: 177
在线: 59.2小时
虫号: 1430582
注册: 2011-10-07
性别: GG
专业: 计算机科学的基础理论

[求助] 有向图的一条路径服从什么分布？

假设有这样一个有向连通图Ｇ，它存在一个起始点，多个终结点，从起始点出发往前走，每走下一步都是随机选择的（注：是有向图，只能从后继结点中选择），一旦抵达任意一个终结点就停止往前走。　
假设这个图非常大，对应了很多个路径。设某一条特定的路径为 t ，那么我在采集了N条（比如100万条）路径后仍然没有采到这条路径 t 的概率Pr(t)要怎么估计？

注：　
１.　我事先并不知道原图中有多少条路径，也没法估计有多少，只知道有很多，暴力枚举所有的路径不能实现。
２．每条路径出现的概率不是均等的，因为图的结构可以会导致某些路径出现在概率高于其他路径　
３.　假设图中是没有那种进去就出不来的强连通分量或者没有后继的非终结节点，这样可以保证从初始点出发必须会在有限步到达某个终结点

举个例子：比如下图（实际情况中图形远比这个大），A是起始点，假设K, L是终结点。
我随机采集路径，采了100条，依然没有采到 A ->B -> D -> G -> C -> D -> E -> H -K 这条路径的概率怎么估计？

digraph-2.jpg

回复此楼

» 猜你喜欢

» 本主题相关价值贴推荐，对您同样有帮助:

一场旅行，一段征程；一山烟云，一湖浮萍。

1楼 2014-11-16 18:48:41

已阅关注TA 给TA发消息送TA红花 TA的回帖

vampireslg

金虫 (小有名气)

应助: 0 (幼儿园)
金币: 1444.6
散金: 5
红花: 11
帖子: 177
在线: 59.2小时
虫号: 1430582
注册: 2011-10-07
性别: GG
专业: 计算机科学的基础理论

引用回帖:

2楼: Originally posted by feixiaolin at 2014-11-16 20:21:22
尝试一下三个概念
1.  概率问题中：马尔可夫链
2.  计算机处理图像边缘问题中：链码；
3.  信号与系统中：梅森公式

十分感谢您的回复，但是
1. 图的结构不知道，对我而言是一个黑盒子，所以马尔可夫链不适用
2. 链码关注的是图像的边界表示，本问题关注有向图的路径存在与否，以多大概率存在，跟链码基本没有关系
3. 跟1中一样，图对我而言是一个黑盒子，其特征值、特征行列式什么的都是不可知的，所以Mason' Rule也无用武之地
尽管如此，还是十分感谢您的回复。

我更关注的是有没有一种类似区间估计的方式给出一个概率估计区间，并且对这个区间给出相应的置信度。