这是一个创建于 1492 天前的主题，其中的信息可能已经有所发展或是发生改变。
我们称一个迷宫是完美的，如果迷宫中的任何两个房间之间都有且仅有唯一的道路相连。我们称迷宫中的一个房间是“死角”，当且仅当它只有一条道路与其它房间相通 。换句话说，一旦进去了就必须原路返回，没有其它出路。
问题：假设在一个 n x n 的网格图上，以完全相等的概率在所有的完美迷宫中随机任选一个，那么这个迷宫包含的死角的个数的比例的期望值是多少？这个期望是常数吗？还是随着 n 的增加线性增长？或者 logn 增长？还是什么别的？
解释一下：完美迷宫可以看作是 n x n 网格图的一个生成树，迷宫的死角其实就是生成树的叶节点，其度数为 1 。这个问题的本意就是问，对于网格图的一个完全随机的生成树，其叶节点所占比例 (注意这个比例是随机变量，不同的树比例也不同)随着 n 的变化关系。下图显示的是 80x80 的网格图的一个随机生成树，其中叶节点用蓝色的圆点标出。它有 1884 个叶节点，所占比例为 1884/6400=0.294375 。
你能猜到这个问题的答案吗？
PS: 上一次的 "走出太阳系" 的问题 https://v2ex.com/t/716022 的解答公布了，见 http://pywonderland.com/random-walk-potential-kernel/
本文答案会在下周公布。
第 1 条附言 · 2020-11-20 08:41:08 +08:00
 |
1
kile 2020-10-26 14:29:51 +08:00
这就是数学大佬的世界?..
|
 |
2
mathzhaoliang OP @kile 给程序员的世界添加点不一样的内容 ...
|
 |
3
ZRS 2020-10-28 01:14:54 +08:00 via iPhone
盲猜个 sqrt(n)
|
|
4
mathzhaoliang OP @ZRS 少了，是个线性因子。
|
 |
5
SmallTeddy 2020-10-28 15:00:38 +08:00
首先要分析角形成的几种情况，一共三种，两条线相交于一个直角，为一个角；一条线相交致另一条线中间，为两个角；两条线中部相交，为四个角，而这里考虑的是生成死角的期望，出现死角的情况：两次第一种情况连续出现或者第一种情况加第二种情况出现或者第四种情况和第一种第二种情况混合出现，所以我不会！！！
|
Select Language