自回避随机行走问题

in 数据结构 with 0 comment

问题描述:

假设有一条狗放在某个城市中心点,它试图逃出城市,此城市有N条南北走向的街道和N条东西走向的街道,所有街道均匀交叉分布构成网格形式。这条狗在逃出城市的过程中,遇到每个交叉路口则按照随机概率的大小选择前进方向,它能够通过灵敏的嗅觉和记忆不走重复路。当狗走到某个交叉路口时,如果三个可选方向均指向以前走过的路口就必须回头,则陷入死胡同状态。

基本要求:

狗尝试逃出的次数设为T。

1) 假设给出某个确定的N值(N=50),分析并输出这条狗陷入死胡同的概率是多少,行走路径的平均长度是多少?成功逃出的平均路径长度和陷入死胡同的平均路径长度各是多少?

2) 给出一组不同的N值,通过运算分析出N的规模大小与陷入死胡同的概率,这两者之间的联系。

Self_avoiding_walk.svg.png

基本思路:

建立一个二维数组表示城市街道,为了方便,可以把数组大小设置为n+2,其中0和n-1表示边界。并用true和false标识道路是否走过,以避免重复走同一条道路。起始位置可以用(n+1)/2+1表示。n为奇数时,中间位置只有一个,n为偶数时,中间位置有四个,考虑到对称性,我们依然可以认为该位置为中心位置。

每一次移动前,判断将要移动的方格是否可以移动,如果不可以,则取判断是否已走入死胡同。

每一次移动后,判断位置信息是否已到达边界。

最后统计需要的数据。

代码实现:

以CPP为例:

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<time.h> 
    
int main(void){
    srand((unsigned)time(0));//初始化随机种子
    int n = 0;//街道数
    int t = 0;//尝试次数
    printf("input n for blocks and t for try times:");
    scanf("%d %d", &n,&t);//读取街道数和尝试次数
    if(t>400000){
        printf("too much times!Stack overflow!");
        return 1;
    }
    bool road[n + 2][n + 2]; //记录道路是否走过的数组
    long len[t];             //每一次尝试所走的路径长度以及是否成功
    bool isSuc[t];
    for (int i = 0; i < t; i++){ //初始化
        len[i] = 0;
        isSuc[i] = false;
    }
    for (int i = 0; i < t;i++){//尝试t次
        for (int k = 0; k < n+2;k++)//初始化道路数组
            for (int j = 0; j < n+2;j++)
                road[k][j] = true;
        int tmp = -1;//记录随机结果,用于判断方向
        int nowX = (n+1) / 2 +1;//记录当前位置
        int nowY = (n+1) / 2 +1;
        int l = 0;//记录本次路径长度
        road[nowX][nowY] = false;  
        while(true){
            tmp =rand()%4;
            if((tmp==0) && road[nowX-1][nowY]){//向左走,且左道路可走
                road[--nowX][nowY] = false;
                l++;
            }else if((tmp==1)&& road[nowX][nowY+1]){
                road[nowX][++nowY] = false;
                l++;
            }else if((tmp==2)&&road[nowX+1][nowY]){
                road[++nowX][nowY] = false;
                l++;
            }else if((tmp==3)&&road[nowX][nowY-1]){
                road[nowX][--nowY] = false;
                l++;
            }else if(!road[nowX-1][nowY]&&!road[nowX+1][nowY]&&!road[nowX][nowY+1]&&!road[nowX][nowY-1]){//如果以上道路不可走,判断是否走进死胡同
                len[i] = l;
                break;
            }   
            if(nowX==0||nowX==n+1||nowY==0||nowY==n+1){//每一次走完后,判断是否已走出
                len[i] = l;
                isSuc[i] = true;
                break;
            }
        }
    }
    long allLen = 0, sucLen = 0, failLen = 0, sucTimes = 0,failTimes=0;
    for (int i = 0; i < t;i++){//计算各个数据
        if(isSuc[i]){
            sucLen += len[i];
            sucTimes++;
        }else{
            failLen += len[i];
            failTimes++;
        }
        allLen += len[i];
    }
    printf("all_len=%ld suc_len=%ld fail_len=%ld suc_times=%ld fail_times=%ld\n", allLen, sucLen, failLen, sucTimes, failTimes);
    printf("suc_rate=%.5f  ave_suc_len=%.2f  ave_fail_len=%.2f  ave_all_len%.2f\n", (float)sucTimes / t, (float)sucLen / sucTimes, (float)failLen / failTimes, (float)allLen/t);
    return 0;
}

样例:

//输入 50 100
all_len=6429 suc_len=1046 fail_len=5383 suc_times=12 fail_times=88
suc_rate=0.12  ave_suc_len=87.17  ave_fail_len=61.17  ave_all_len64.29

结论:

自回避随机行走问题在各个领域都有出现,但此类问题不能精确的计算出定量答案,只能通过模拟得出定性结论。可以发现,自回路逃离的成功率会随着道路长度的增加而不断减少,平均逃离长度也随之增加。

Responses