自避行走 精确计数

xiongzm

大家都熟悉无规行走问题(random walking)，如果不允许交叠，就是自避行走问题(self-avoiding walking ).。考虑二维SAW，比如二维方格上的SAW，走1步有4种方法；走2步有12种走法，走3步有36种走法，4步100种：
5 －－－184； 6－－－780；  7－－－2171； 8－－－5916；
9－－－16268； 10－－－44100；
继续下去，100步应该有多少种走法了？
问题延伸到3维立方格点，金刚石格点等，就更复杂了。

很容易编一个简单的递归程序计算，但效率很低，即使在机群上计算，走30多步也不是一天能算出来的。如果有一个并行算法，如果还能够做成分布式计算，速度就会提高，应该容易超过现有的记录。我不熟悉并行算法，刚开始学习，想到这个问题，请大家支持。

count

说说你的算法?

xiongzm

下面是最初始的代码之一，显然可以有一些小的优化，但是如何并行，网格是个问题。

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <string.h>

#define N9 10000000

int space[100][100][100];
long int NumConf0,NumConf1,NumConf2;
long int NumConf02D,NumConf12D;
int step,N,X,Y,Z;
int search();
int search2D();
int direction(int x,int y,int z);
time_t startTime,endTime;

int direction2D(int x, int y)
{
   if (space[X+x][Y+y][Z] == 0){
         X+=x;
         Y+=y;
         space[X][Y][Z]=1;
         if(step < N) direction(0,0,1);
         search2D();
         space[X][Y][Z]=0;
         X-=x;
         Y-=y;
         }
   return (0);
}

int search2D()
{
   step++;
   if (step <= N) {
  
   direction2D(-1,0);
   direction2D(0,-1);
  
   direction2D(1,0);
   direction2D(0,1);
   }
   else {
   NumConf02D++;
   if ( NumConf02D >= N9)
      {
               NumConf02D %= N9;
               NumConf12D++;
       }
   }
   
   step--;
   return (0);
}

int direction(int x, int y, int z)
{
   if (space[X+x][Y+y][Z+z] == 0){
         X+=x;
         Y+=y;
         Z+=z;         
         space[X][Y][Z]=1;
         search();
         space[X][Y][Z]=0;
         X-=x;
         Y-=y;
         Z-=z;         
         }
   return (0);
}

int search()
{
   step++;
   if (step < N) {
  
   direction(-1,0,0);
   direction(0,-1,0);
   direction(0,0,-1);
   
   direction(1,0,0);
   direction(0,1,0);
   direction(0,0,1);
   }
   else {
   NumConf0++;
   if ( NumConf0 >= N9)
      {
               NumConf0 %= N9;
               NumConf1++;
               if (NumConf1 >= N9)
               {
                       NumConf1 %= N9;
                       NumConf2++;
               }
               if (NumConf1%1000 ==0)
               {
                 endTime=time(NULL);
               printf ("%ld seconds %ld-%ld-%ld\n",endTime-startTime,NumConf2,NumConf1,NumConf0);
               }
       }
   }
   
   step--;
   return (0);
}

int main(int argc, char *argv[])
{      
        FILE *fcn;
        
        int i,j;
        long num0,num1;
       
        N=0;
        if (argc == 2 )
            {
                for (i=0;i<strlen(argv[1]);i++)
                      {
                         j=*(argv[1]+i)-'0';
                         if ( j < 0 || j >= 10)
                            {
                                 printf("Usage: %s N\n",*(argv));
                                
                                exit(1);
                             }
                         else
                            {
                             N*=10;
                             N+=j;
                             }
                      }
                }
        else
        {
         printf("Usage: %s N\n",*argv);
  
         exit(1);
        }
       
        printf("      166 seconds on Pentium3/800MHz for N=16\n");
        printf("       79 seconds on athlon-mp 2000+ for N=16\n");
       

        X=Y=Z=50;
        space[X][Y][Z]=1;

        startTime = time(NULL);

        for (i=1;i<=N;i++){
                Y++;
                space[X][Y][Z]=1;
                step=i+1;
                direction2D(1,0);
        }
       
          endTime=time(NULL);
        printf ("         %ld seconds.\n",endTime-startTime);
       
        NumConf0 *= 48;
        NumConf1 *= 48;
        NumConf2 *= 48;
        NumConf1 += NumConf0/N9;
        NumConf0 %= N9;
        NumConf2 += NumConf1/N9;
        NumConf1 %= N9;

        NumConf02D--;
        NumConf02D *= 24;
        NumConf12D *= 24;
        NumConf12D += NumConf02D/N9;
        NumConf02D %= N9;

        NumConf0 += NumConf02D;
        NumConf1 += NumConf0/N9;
        NumConf0 %= N9;
       
        NumConf0 += 6;
       
        NumConf1 += NumConf12D;
        NumConf2 += NumConf1/N9;
        NumConf1 %= N9;

        printf("         N= %d CN= ", N);
        if (NumConf2 !=0) printf("%ld",NumConf2);
        j=N9;num0=num1=NumConf1;
             for (i=1;i<8;i++){ j/=10;num1=num0/j;num0%=j;printf("%ld",num1);}
        j=N9;num0=num1=NumConf0;
             for (i=1;i<8;i++){ j/=10;num1=num0/j;num0%=j;printf("%ld",num1);}
        printf("\n");
               
        fcn=fopen("SAW_cubic.dat","a");
        fprintf(fcn,"%10ld seconds N= %d CN= ",endTime-startTime, N);
        if (NumConf2 !=0) fprintf(fcn,"%ld",NumConf2);
        j=N9;num0=num1=NumConf1;
             for (i=1;i<8;i++){ j/=10;num1=num0/j;num0%=j;fprintf(fcn,"%ld",num1);}
        j=N9;num0=num1=NumConf0;
             for (i=1;i<8;i++){ j/=10;num1=num0/j;num0%=j;fprintf(fcn,"%ld",num1);}
        fprintf(fcn,"\n");
       
        fcloseall();

        return(0);
}