精华内容
下载资源
问答
  • “在概率论中,随机游走是确定一个点相对于随机运动的可能位置的过程,给定在特定距离和特定方向上移动的概率(每一步都相同)” - —— 从这些解释中,我们可以得出结论,基本上随机游走是对象在空间(1D、2D、3D ...
  • 随机游走matlab代码概率模型编程 书籍:概率模型简介,第十版精装书 – 2009 年 12 月 17 日by Sheldon M. Ross (Author) * Best_Prize_Problem [Matlab 脚本] “最佳奖品问题”演示 Page.126 * random_graph_...
  • 题解:bfs+图上随机游走+概率 对于一张n个点的连通图,记起点为s,那么有一个结论,从s出发然后回到s的概率为 (s的度数+1)/(总度数+n)。 我们可以从s点开始bfs构建连通图,若图包含了对角线即x==y,那么图是无穷...

    题意:求在坐标图上,随意游走无穷步,回到起点的概率。只能游走gcd(x,y) > 1的坐标。

    题解:bfs+图上随机游走+概率
    对于一张n个点的连通图,记起点为s,那么有一个结论,从s出发然后回到s的概率为 (s的度数+1)/(总度数+n)。

    我们可以从s点开始bfs构建连通图,若图包含了对角线即x==y,那么图是无穷的,概率自然在极限下趋于0。

    然后我们可以证明这张不包含对角线的连通图,它的大小只有几百,贴一下题解的证明:

    在这里插入图片描述
    bfs的时候直接记录度数即可。

    #define _CRT_SECURE_NO_WARNINGS
    #include<iostream>
    #include<cstdio>
    #include<string>
    #include<cstring>
    #include<algorithm>
    #include<queue>
    #include<stack>
    #include<cmath>
    #include<vector>
    #include<fstream>
    #include<set>
    #include<map>
    #include<sstream>
    #include<iomanip>
    #define ll long long
    using namespace std;
    int t, d[8][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1},{1, 1}, {1, -1}, {-1, 1}, {-1, -1} };
    ll x, y, xx, yy;
    ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
    map<pair<int, int>, bool> m;
    int main() {
    	//freopen("J.in", "r", stdin);
    	scanf("%d", &t);
    	while (t--) {
    		m.clear();
    		scanf("%lld%lld", &x, &y);
    		int flag = 0;
    		queue<pair<ll, ll> > q;
    		q.push(make_pair(x, y));
    		int num = 0;
    		m[make_pair(x, y)] = true;
    		++num;
    		pair<ll, ll> pp;
    		int ans = 0, ans1;
    		flag = 0;
    		while (!q.empty()) {
    			ll tx = q.front().first;
    			ll ty = q.front().second;
    			int id = m[make_pair(tx, ty)];
    			q.pop();
    			for (int i = 0; i < 8; i++) {
    				xx = tx + d[i][0], yy = ty + d[i][1];
    				pp = make_pair(xx, yy);
    				if (gcd(xx, yy) == 1) continue;
    				if (xx == yy) {
    					flag = 2;
    					break;
    				}
    				if (m[pp]) {
    					++ans;
    					//v[num].push_back(id);
    					continue;
    				}
    				m[pp] = true;
    				++num;
    				++ans;
    				//v[num].push_back(id);
    				q.push(pp);
    			}
    			if (flag == 2) break;
    			if (!flag) {
    				ans1 = ans;
    				flag = 1;
    			}
    		}
    		if (flag == 2) {
    			puts("0/1");
    			continue;
    		}
    		int fz = ans1 + 1;
    		int fm = ans + num;
    		int gc = gcd(fz, fm);
    		printf("%d/%d\n", fz / gc, fm / gc);
    	}
    	return 0;
    }
    
    展开全文
  • 给你一张无向连通图,从第111点随机游走到nnn点。花费为经过的边的编号的和.问你如何安排边的编号使得期望花费最小化. n≤500,m≤n2n \leq 500,m \leq n^2n≤500,m≤n2 题目思路: 很容易想到,求出每条边期望经过次数...

    题目1:[HNOI2013]游走

    题目大意

    给你一张无向连通图,从第11点随机游走到nn点。花费为经过的边的编号的和.问你如何安排边的编号使得期望花费最小化.

    n500,mn2n \leq 500,m \leq n^2

    题目思路:

    很容易想到,求出每条边期望经过次数,然后贪心安放即可.

    但是mm太大,无法求解.考虑先求每个点期望经过次数.

    考虑到nn点就停止了,所以不考虑nn的贡献。
    显然有转移:
    f1=1+(1,j)Efjdujf_1=1+\sum_{(1,j)\in E}^{}\frac{f_j}{du_j}
    fn=0f_n=0
    fi=(i,j)Efjduj, i[2,n)f_i=\sum_{(i,j)\in E}^{}\frac{f_j}{du_j}, \ i \in [2,n)

    对于一条边(i,j)(i,j),它期望经过的次数是:

    gi,j=fidui+fjdujg_{i,j}=\frac{f_i}{du_i} + \frac{f_j}{du_j}

    所以跑高斯消元后,对边排序计算即可。

    AC代码:

    #include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    #define pb push_back
    #define pii pair<int,int>
    #define mp make_pair
    const int maxn = 505;
    const double eps = 1e-8;
    vector<int> e[maxn];
    int du[maxn];
    double a[maxn][maxn];
    double res[maxn] , ans[maxn * maxn];
    int main()
    {
        ios::sync_with_stdio(false);
        int n , m; cin >> n >> m;
        for (int i = 1 ; i <= m ; i++){
            int x , y; cin >> x >> y;
            e[x].pb(y);
            e[y].pb(x);
            du[x]++;
            du[y]++;
        }
        for (int i = 1 ; i <= n ; i++) a[i][i] = 1;
        for (int i = 1 ; i < n ; i++){
            for (auto v : e[i]){
                a[i][v] = -1.0 / du[v];
            }
        }
        a[1][n + 1] = 1;
        // guess消元
        int r , c;
        for (r = c = 1 ; r <= n && c <= n ; r++ , c++){
            int p = r;
            for (int j = r + 1 ; j <= n ; j++){
                if (a[p][c] < a[j][c]){
                    p = j;
                    break;
                }
            }
            // 不会有自由元
            swap(a[p] , a[r]);
            for (int j = 1 ; j <= n ; j++){
                if (j == r) continue;
                if (fabs(a[r][c]) < eps) continue;
                double d = a[j][c] / a[r][c];
                for (int k = c ; k <= n + 1 ; k++)
                    a[j][k] -= d * a[r][k];
            }
        }
        for (int i = 1 ; i <= n ; i++) res[i] = a[i][n + 1] / a[i][i];
        int cnt = 0;
        for (int i = 1 ; i <= n ; i++){
            for (auto v : e[i]){
                if (v < i) continue;
                ans[++cnt] = res[i] / du[i] + res[v] / du[v];
            }
        }
        sort(ans + 1 , ans + 1 + cnt);
        double gg = 0;
       // cout << "cnt = " << cnt << endl;
        for (int i = 1 ; i <= cnt ; i++){
            gg += (cnt - i + 1.0) * ans[i];
        }
        cout << fixed << setprecision(3);
        cout << gg << endl;
        return 0;
    }
    

    题目2:bzoj3270-博物馆

    题目大意:

    给出一个无向图,两个人初始在两个点上。当一个人在一个点i上的时候,每一次,他有p[i]p[i]的概率留在原位,有1p[i]1−p[i]的概率等概率地选择直接连边的一个点走出去。当两个人在同一时刻走到同一个点,那么他们相遇,过程结束。现在求他们在每一个点相遇的概率。

    题目思路:

    跟题目1没本质区别,就是升维了。令f(i,j)f(i,j)代表两个人从最开始到站在i,ji,j期望次数,然后大力转移即可.

    题目3:2019HNCPC-H-有向图

    题目大意:

    给你一张图。n+mn+m个点。从1点开始随机游走。有一个概率矩阵Pi,jP_{i,j}代表从iji到j的概率.后mm个点走到后则只会原地踏步.问你无限次之后停在后m个点的概率.

    题目思路:

    E(i)E(i)为无限次之后经过ii点的期望次数。由于到i, i[n+1,n+m]i ,\ i \in[n+1,n +m]后就会停止。所以求解出来的期望就是概率。

    转移和上述问题无差别,列方程高斯消元即可.

    题目4:HDU5955-AC自动机+概率dp+高斯消元

    题目大意:

    n个人,每个人有一个长度为LL的字符串。你随机生成字符串无限次直到最后LL个字符串为某个人的字符串.问每个人的概率.

    题目思路:

    建Tire图。在Tire图上跑概率dp.然后高斯消元即可.

    问题结构和题目3一模一样。我们可以直接求期望,然后概率=期望.

    展开全文
  • 随机游走matlab代码QUT 随机游走 使用随机游走的人群在大学校园内行走的 Matlab 模拟 人群在大学校园内行走的行为是使用随机行走来模拟的。 该项目的目的是确定哪些区域和建筑物将被访问最多,假设人口的随机步行...
  • python模拟随机游走

    2019-10-02 00:03:06
    下面是一个单一的200步随机游走的例子,从0开始,步长为1和-1,且以相等的概率出现。纯Python方式实现,使用了内建的 random 模块: # 随机游走 import matplotlib.pyplot as plt import random position = ...

     

    在python中,可以利用数组操作来模拟随机游走。

     

    下面是一个单一的200步随机游走的例子,从0开始,步长为1和-1,且以相等的概率出现。纯Python方式实现,使用了内建的 random 模块:

    # 随机游走
    import matplotlib.pyplot as plt
    import random
    
    position = 0
    walk = [position]
    steps = 200
    for i in range(steps):
        step = 1 if random.randint(0, 1) else -1
        position += step
        walk.append(position)
    
    fig = plt.figure()
    ax = fig.add_subplot(111)
    ax.plot(walk) plt.show()

     

     

    第二种方式:简单的把随机步长累积起来并且可以可以使用一个数组表达式来计算。因此,我用 np.random 模块去200次硬币翻转,设置它们为1和-1,并计算累计和:

    # 随机游走
    import matplotlib.pyplot as plt
    import numpy as np
    
    nsteps = 200
    draws = np.random.randint(0, 2, size=nsteps)
    steps = np.where(draws > 0, 1, -1)
    walk = steps.cumsum()
    
    fig = plt.figure()
    ax = fig.add_subplot(111)
    ax.plot(walk)
    plt.show()

     

     

    一次模拟多个随机游走

    # 随机游走
    import matplotlib.pyplot as plt
    import numpy as np
    
    nwalks = 5
    nsteps = 200
    draws = np.random.randint(0, 2, size=(nwalks, nsteps)) # 0 or 1
    steps = np.where(draws > 0, 1, -1)
    walks = steps.cumsum(1)
    
    fig = plt.figure()
    ax = fig.add_subplot(111)
    for i in range(nwalks):
        ax.plot(walks[i])
    
    plt.show()

     

     

     

    当然,还可以大胆的试验其它的分布的步长,而不是相等大小的硬币翻转。你只需要使用一个不同的随机数生成函数,如 normal 来产生相同均值和标准偏差的正态分布:

    steps = np.random.normal(loc=0, scale=0.25, size=(nwalks, nsteps))

     

    转载于:https://www.cnblogs.com/hhh5460/p/4356635.html

    展开全文
  • 随机游走(Random Walk)算法

    千次阅读 2021-03-09 15:54:01
    一维的随机游走可定义如下: 每过一个单位时间,游走者从数轴位置x出发以固定概率随机向左或向右移动一个单位. 不妨将n时刻游走者的位置记为Ln,则有 其中X1,X2,…,Xn为相互独立的随机变量,满足 最经典的一维...

    随机游走

    • 英文:random walk

    • 定义:随机游走,概念接近于布朗运动,是布朗运动的理想数学状态。

    • 核心概念:任何无规则行走者所带的守恒量都各自对应着一个扩散运输定律。

    • 随机游走算法基本思想是:
      从一个或一系列顶点开始遍历一张图。在任意一个顶点,遍历者将以概率1-a游走到这个顶点的邻居顶点,以概率a随机跳跃到图中的任何一个顶点,称a为跳转发生概率,每次游走后得出一个概率分布,该概率分布刻画了图中每一个顶点被访问到的概率。用这个概率分布作为下一次游走的输入并反复迭代这一过程。当满足一定前提条件时,这个概率分布会趋于收敛。收敛后,即可以得到一个平稳的概率分布。

    随机游走过程

    一维的随机游走可定义如下: 每过一个单位时间,游走者从数轴位置x出发以固定概率随机向左或向右移动一个单位.
    不妨将n时刻游走者的位置记为Ln,则有
    在这里插入图片描述
    其中X1,X2,…,Xn为相互独立的随机变量,满足
    在这里插入图片描述

    • 最经典的一维随机游走问题有赌徒输光问题酒鬼失足问题

    (1)赌徒在赌场赌博,赢的概率是p,输的概率1-p,每次的赌注为1元,假设赌徒最开始时有赌金1元,赢了赌金加1元,输了赌金减1元。问赌徒输光的概率是多少?
    (2)一个醉鬼行走在一头是悬崖的道路上,酒鬼从距离悬崖仅一步之遥的位置出发,向前一步或向后退一步的概率皆为1/2,问酒鬼失足掉入悬崖的概率是多少?

    **

    一维有边界的随机游走问题

    **

    • 下面先对一维双边界随机游走问题进行求解:
    • 设初始位置为
      x=n,边界为x=0和x=w,其中0<=n<=w,n、w为整数。游走者每个单位时间移动一次,向左、向右移动的概率都为1/2,达到边界后停止移动。

    若用Sn表示初始位置为x=n时最终落入边界x=0的概率。显然我们会有S0=1和Sw=0,即初始位置为边界的情况。
    若0<n<w,则考虑其下一次移动。有1/2的概率向左到达 n-1,有1/2的概率向右到达n+1。 则由全概率公式可得,
    在这里插入图片描述
    整理得到
    在这里插入图片描述
    利用
    在这里插入图片描述
    可得
    在这里插入图片描述
    累加法可得,
    在这里插入图片描述
    由S0=1,Sw=0,可得
    在这里插入图片描述
    同理,Tn初始位置为x=n时最终落入边界x=w的概率,可得Tn=n/w。 对于单边界情况,可以令w趋于正无穷得到,即可得Sn=1,Tn=0。

    展开全文
  • 下面是一个单一的200步随机游走的例子,从0开始,步长为1和-1,且以相等的概率出现。纯Python方式实现,使用了内建的 random 模块: # 随机游走 import matplotlib.pyplot as plt import random position = 0 walk ...
  • 因此,在使用逐笔报价数据进行的简单运行测试中,随机游走假设被驳回。 此外,价格较长时间的连续上涨往往会出现较大的反转。 调查结果表明,那些能够访问实时、逐笔交易数据的市场参与者可能在预测汇率变动方面...
  • 函数为, f=6r*exp(-3*r^2/(na^2))/(na^2) f —— 描述距离为 r 的醉酒者的概率密度n —— 描述他们走过的步数a——描述一个酒鬼每次行走的范围 从仿真中可以看出,理论函数与实验函数非常相似,说明了该模型的正确...
  • Python模模拟拟随随机机游游走走图图形形效效果果示示例例 这篇文章主要介绍了Python模拟随机游走图形效果,涉及Python随机数概率运算及图形绘制相关操作技巧,需要的 友可以参考下 本文实例讲述了Python模拟随机游走...
  • 推荐算法随机游走

    千次阅读 2018-05-31 20:59:47
    从某个节点\(u\)出发进行随机游走,以\(\alpha\)的概率选择继续从当前节点任选一个与之相连的其他节点进行下一次的随机游走或者从\(u\)重新开始游走,那么节点\(v_i\)被访问到的概率 $$p(v_i)=(1-\alpha)(v_i==u)+ ...
  • 图神经网络-随机游走

    2021-05-13 11:38:40
    在带重启的随机游走算法中, 一个节点转移到另一个节点的概率有两个(为了避免混乱, 应当心中常记这两项): 转移矩阵中的概率(我们简单的称之为转移概率) 综合了转移矩阵和重启(restart)概率的转移概率(这里我称之为...
  • 随机游走(Random Walk)搜索算法 随机游走算法 定义:随机游走,概念接近于布朗运动,是布朗运动的理想数学状态。 核心概念:任何无规则行走者所带的守恒量都各自对应着一个扩散运输定律。 随机游走算法的基本思想...
  • 对于无黑洞的随机游走问题可以使用线性方程组求解,对于有黑洞的随机游走问题就无法使用线性方程组进行求解了。 有黑洞的随机游走问题举例: 随机给定一个魔方状态,随机旋转期望通过多少步才能旋转到目标状态? 这...
  • 如果直接dp,状态里肯定要带上已走过的点的集合,感觉上不太好做。  考虑一种对期望的minmax容斥:其中Max(S)为遍历完S集合的期望步数,Min(S)为遍历到S集合中一个点的期望步数。当然才不管怎么证,反正看上去非常...
  • 基于随机游走的personalRank算法是从...数据集随机分成训练集和测试集,指定训练集中任意点开始进行随机游走,游走的时候根据不同点之间的权重来选择游走方向的概率,到达下一个点以后会根据指定的alpha值随机决定继...
  • 研究了随机游走模型中转移概率矩阵的计算方法,并针对推荐系统中的随机游走模型,提出了一种基于隐含因子的方法来计算转移概率矩阵。这种方法通过矩阵分解的技术将随机游走模型中的节点映射为隐含因子向量,并使用该...
  • 基于视觉注意的随机游走图像分割.pdf,传统随机游走图像分割需要多次交互设置种子点以获得理想的分割结果。在视觉注意的基础上,提出了一种新的自动确定种子点的随机游走图像分割算法。首先对图像进行超像素分割,并...
  • 该算法在聚类过程中结合像素的空间信息计算像素的隶属度,在基于随机游走的半监督图像分割算法中像素结点构成的四连通图上插入类属结点作为已标记结点,将随机游走者第一次游走到某个类属结点的概率作为该像素隶属于该...
  • Random Walk(随机游走

    万次阅读 2019-02-24 17:24:10
    金融和经济模型和概率统计学难以分离,对于这样的随机二级市场数据的理解和操作也是计算机科学的一个领域,十分有魅力的计算金融学。 普通数据挖掘方法大多都是确定性模型,对于输入的输出往往没有随机性,而一些能...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 391
精华内容 156
关键字:

概率随机游走