MATLAB: Self avoiding random walk

random walkself avoiding

i need help. what i think i have to do is choose a direction at random and then look at a direction i want to go to if it's empty then carry on. if the direction is used then you start another walk. 1000 walks and lenght 1 to 25. how do i calcalute the number of successful walks. the code i have is a random walk
r=[0 0];
X=[0];Y=[0];
for
t= 1:1:100
B=rand(1,1)*4;
if B<1
new_position=r+[1 0];
elseif B<2
new_position=r+[0 1];
elseif B<3
new_position=r+[-1 0];
else
new_position=r+[0 -1];
end
X=[X new_position(1)];
Y=[Y new_position(2)];
r=new_position;
end
plot(X,Y)

Best Answer

As I see it from all you have stated, Nawal, you wish to "walk" point-to-point starting at (0,0) for a maximum of 25 steps, at each step moving a distance of one unit in one of four possible directions: up, left, down, or right with equal probabilities. However you wish to quit the walk if before 25 successful steps you would occupy a point that has already been traversed. Your aim is to count the number of successful walks, that is, the number in which you successfully reached 25 unoccupied points, out of a total of one thousand attempted walks. Do I state your problem correctly? (Your later remark that "it lands within a certain distance" throws some uncertainty into this interpretation. Are you sure you meant to concede this? You are dealing with exact integral positions here. Based on your earlier remarks, that "certain" distance should be an exact zero!)
In the following code the variable w will count the number of walks, the variable c will count the number of successful walks, the variable s will count the number of successful steps taken in each walk, and the 51 x 51 array Occ will record the positions already occupied during each walk.
c = 0; % This counts the number of "successful" walks
tx = [1,0,-1,0];
ty = [0,1,0,-1];
for w = 1:1000 % w counts the walks attempted

  Occ = zeros(51); % Keeps track of occupied points
  x = 26; % It is equivalent to start at (26,26) rather than (0,0)
  y = 26;
  Occ(x,y) = 1; % w counts the walks attempted
  s = 0; % Start number of steps at zero for each walk
  b = true;
  while b & (s<25) % Quit if walk abandoned or succesful
    r = randi(4);
    x = x + tx(r);
    y = y + ty(r);
    if Occ(x,y) == 1
      b = false;
    else
      Occ(x,y) = 1;
      s = s + 1;
    end
  end
  if s == 25
    c = c + 1; % Count the number of successful walks
  end
end
Related Question