问题描述:
假设有一条狗放在某个城市中心点，它试图逃出城市，此城市有N条南北走向的街道和N条东西走向的街道，所有街道均匀交叉分布构成网格形式。这条狗在逃出城市的过程中，遇到每个交叉路口则按照随机概率的大小选择前进方向，它能够通过灵敏的嗅觉和记忆不走重复路。当狗走到某个交叉路口时，如果三个可选方向均指向以前走过的路口就必须回头，则陷入死胡同状态。
基本要求:
狗尝试逃出的次数设为T。
1) 假设给出某个确定的N值(N=50)，分析并输出这条狗陷入死胡同的概率是多少，行走路径的平均长度是多少？成功逃出的平均路径长度和陷入死胡同的平均路径长度各是多少？
2) 给出一组不同的N值，通过运算分析出N的规模大小与陷入死胡同的概率，这两者之间的联系。
基本思路:
建立一个二维数组表示城市街道，为了方便，可以把数组大小设置为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结论:
自回避随机行走问题在各个领域都有出现，但此类问题不能精确的计算出定量答案，只能通过模拟得出定性结论。可以发现，自回路逃离的成功率会随着道路长度的增加而不断减少，平均逃离长度也随之增加。
本文由 ukuq 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Mar 22, 2019 at 08:33 pm
