随机生成自避行走

hbghlyj · 发表于 2023-5-25 06:05

在$n\times n$网格如何随机生成自避行走

下面是基于对称的,不是随机生成的.
size(5cm);

int n = 7; // size of the lattice
real cellSize = 0.2; // size of each lattice cell

path selfAvoidingWalk = (0,0) -- (1, 0) -- (2, 0) -- (3, 0) -- (3, 1) -- (3, 2) -- (3, 3) -- (2, 3) -- (2, 2) -- (2, 1) -- (1, 1) -- (1, 2) -- (1, 3) -- (0, 3) -- (0, 2)--(0,1);
selfAvoidingWalk=shift(4)*selfAvoidingWalk--shift(3)*xscale(-1)*reverse(selfAvoidingWalk);
selfAvoidingWalk=shift(0,4)*selfAvoidingWalk--shift(0,3)*yscale(-1)*reverse(selfAvoidingWalk);

// Draw the lattice grid
for (int i = 0; i <= n; ++i) {
draw((i, 0) -- (i, n), linewidth(.1)+gray);
draw((0, i) -- (n, i), linewidth(.1)+gray);
}

// Draw the self-avoiding walk
draw(selfAvoidingWalk--cycle, blue);
dot(selfAvoidingWalk, red);

hbghlyj · 发表于 2023-5-25 06:19

import graph;
size(200);
// Define the SVG path as a string
string svgPath = "50,50 L 50,150 L 150,150 L 150,100 L 100,100 L 100,50 L 200,50 L 200,150 L 250,150 L 250,250 L 200,250 L 200,200 L 50,200 L 50,350 L 100,350 L 100,250 L 150,250 L 150,300 L 350,300 L 350,250 L 300,250 L 300,100 L 250,100 L 250,50 L 450,50 L 450,100 L 350,100 L 350,200 L 400,200 L 400,150 L 500,150 L 500,50 L 550,50 L 550,300 L 500,300 L 500,200 L 450,200 L 450,250 L 400,250 L 400,300 L 450,300 L 450,400 L 400,400 L 400,350 L 150,350 L 150,400 L 50,400 L 50,550 L 150,550 L 150,600 L 50,600 L 50,750 L 200,750 L 200,700 L 100,700 L 100,650 L 250,650 L 250,750 L 300,750 L 300,600 L 200,600 L 200,500 L 100,500 L 100,450 L 200,450 L 200,400 L 350,400 L 350,450 L 500,450 L 500,350 L 600,350 L 600,200 L 700,200 L 700,100 L 650,100 L 650,150 L 600,150 L 600,50 L 750,50 L 750,250 L 650,250 L 650,350 L 700,350 L 700,300 L 750,300 L 750,450 L 700,450 L 700,400 L 550,400 L 550,550 L 500,550 L 500,500 L 300,500 L 300,450 L 250,450 L 250,550 L 450,550 L 450,600 L 350,600 L 350,750 L 400,750 L 400,650 L 450,650 L 450,750 L 500,750 L 500,600 L 550,600 L 550,750 L 700,750 L 700,700 L 600,700 L 600,450 L 650,450 L 650,500 L 750,500 L 750,550 L 650,550 L 650,650 L 700,650 L 700,600 L 750,600 L 750,750";

// Split the SVG path into individual commands
string[] commands = split(svgPath, " L ");

// Create a list of points to store the coordinates
pair[] points;

// Process each command in the SVG path
for (string command : commands) {
      string[] coordinates = split(command, ",");
      real x = (int)coordinates[0];
      real y = (int)coordinates[1];
      points.push((x/10,y/10));
}
draw(graph(points), linewidth(2));
for(int i=1; i < 16; ++i) {
  for(int j=1; j < 16; ++j) {
dot((5i,5j),red);
  }
}
stackoverflow.com/questions/7371227/
sfu.ca/~eemberly/phys847/assignments/hamiltonian_paths.html
clisby.net/projects/hamiltonian_path/

hbghlyj · 发表于 2023-5-25 08:08

rand.asy (1.03 KB, 下载次数: 0)
取$n=8$,随机种子s从s=1开始尝试,大多数都(走到死胡同了)不能产生哈密顿路.一直到s=26098才成功.
unitsize(5mm);
real dx=0;
void generate(int n,int s){
pair[] pts;
for (int i = 1; i <= n; ++i) {
  for (int j = 1; j <= n; ++j) {
pts.push((dx+i, j));
  }
}
int ptslength=n^2;
  guide w;
  ptslength=n^2;
  srand(s);
  int startIdx = rand()%ptslength;
  pair currentPt = pts[startIdx%ptslength];
  pts.delete(startIdx);
  ptslength-=1;
  w = w--currentPt;
  while (ptslength > 0) {
pair[] possibleNeighbors;
int[] indices;
for(int i=0;i<ptslength;++i){
   pair pt=pts[i%ptslength];
   if(abs(pt-currentPt)==1){
      possibleNeighbors.push(pt);
      indices.push(i);
   }
}
if (possibleNeighbors.length==0) {break;}
int randomNeighborIdx = rand()%(possibleNeighbors.length);
pair nextPt = possibleNeighbors[randomNeighborIdx];
currentPt = nextPt;
pts.delete(indices[randomNeighborIdx]);
ptslength-=1;
w = w -- currentPt;
  }
draw(w);
for (int i:sequence(n^2)) {
   pair p=point(w,i);
   dot(p,red);label((string)i,p);
}
}
generate(8,26098);dx+=9;
generate(7,23011);dx+=8;
generate(6,91);dx+=7;
generate(5,78);dx+=6;
generate(4,14);dx+=5;
generate(3,4);dx+=4;
generate(2,1);

hbghlyj · 发表于 2023-5-25 08:47

用find改写(需要find四次,可能还不如4#的一遍循环快):

rand.asy (1.07 KB, 下载次数: 1)

		自动登录	找回密码
密码			快速注册

随机生成自避行走

如何随机生成哈密顿路?

暴力尝试🥵