self avoiding random walk
3 views (last 30 days)
Show older comments
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)
2 Comments
Image Analyst
on 18 Nov 2013
Edited: Image Analyst
on 18 Nov 2013
http://www.mathworks.com/matlabcentral/answers/13205-tutorial-how-to-format-your-question-with-markup How do you define "empty"? Are you trying to avoid having the next step cross any paths on the route so far?
Accepted Answer
Roger Stafford
on 19 Nov 2013
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
6 Comments
Image Analyst
on 20 Nov 2013
Edited: Image Analyst
on 20 Nov 2013
You're right. I didn't notice that. Comments in the code, and proper indenting, would have been helpful.
More Answers (1)
Image Analyst
on 19 Nov 2013
"By empty I mean the point is occupied/ already visited" - I doubt that will never happen, at least probably not in your lifetime. The chance of a pair of double precision numbers being repeated exactly is vanishingly small.
7 Comments
Image Analyst
on 19 Nov 2013
Edited: Image Analyst
on 19 Nov 2013
Still unclear. When do you want to stop it?
- If it lands anywhere in the "backwards" half plane?
- Or if it lands within a certain distance from the last point?
- Or if it lands within a certain distance from any prior point?
Which case(s)?
See Also
Categories
Find more on Preprocessing Data in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!