Losowa ścieżka przez prostokąt

Question

Chcę napisać kod, aby wygenerować losową ścieżkę przez prostokąt o danym rozmiarze.

Zacznę od punktu (0,0) i iść up lub right dotrzeć xlim i ylim.

Oto mój kod,

y = 10; 
x = 10; 
yOld = 0; 
xOld = 0; 
figure 
axis([0 x 0 y]) 
while yOld < y && xOld < x 
    DirectionChange = randi([0 1],1); 
    if DirectionChange == 0 
     yNew = yOld + 1; 
     xNew = xOld; 
    else 
     xNew = xOld + 1; 
     yNew = yOld; 
    end 
    line ([xOld xNew],[yOld yNew],'LineWidth',3);hold on 
    yOld = yNew; 
    xOld = xNew; 
end 
line ([xNew x],[yNew y],'LineWidth',3);hold off 

Kod ma while loop, a kończy się, gdy jeden z x lub y osiągnie to ograniczenie.

Więc działa poprawnie pod warunkiem x = y.

Jednak, gdy y > x jest bardziej prawdopodobne, że ścieżka osiągnie wcześniej numer xlim.

do 12 przebiegów x = 10, y = 10 dostać (ja zrobiłem to kolorowy wyglądać lepiej!),

Ustawianie x = 10, y = 20, mam,

Jak widać Tracę przypadkowość w ostatnim przypadku, ponieważ zwiększa się prawdopodobieństwo osiągnięcia x osiągania limitu.

Wszelkie sugestie, jak zachować losowość w przypadku x~=y?

Dzięki.

Answer 1

Zawsze trzeba dokonać x kroki w prawo, a y kroki w górę. Stwórz więc tablicę zawierającą te kroki jako zakodowane instrukcje (prosta tablica będzie w tym przypadku dobra, możemy użyć 0 dla poziomego kroku i 1 dla pionu). Następnie przetasuj tablicę. Gwarantuje to trafienie w róg bez żadnych korekt, a także wszystkie możliwe ścieżki będą równie prawdopodobne (tak losowe, jak tylko możesz).

x = 10; 
y = 20; 
steps = [ zeros(1,x) ones(1,y) ]; 
steps = steps(randperm(x+y)); 

figure 
hold on; 

xOld = 0; 
yOld = 0; 
axis([0 x 0 y]) 
for step = steps, 
    if (step == 1) 
     yNew = yOld + 1; 
     xNew = xOld; 
    else 
     xNew = xOld + 1; 
     yNew = yOld; 
    end 
    line ([xOld xNew],[yOld yNew],'LineWidth',3); 
    yOld = yNew; 
    xOld = xNew; 
end 
line ([xNew x],[yNew y],'LineWidth',3); 
hold off 

Answer 2

To, co chcesz zrobić, to zrobić tak, aby P(x increases) = x/(x+y) i P(y increases) = y/(x+y). W ten sposób prawdopodobieństwo, że x osiągnie swój limit, jest takie samo, jak prawdopodobieństwo osiągnięcia przez swój limit wartości y.

przykład: Dla danego xlim 5 i Daną ylim 10, generuje liczbę losową z ciągłym przedziale [0,1]. Jeśli ta liczba losowa jest mniejsza niż 0,333, czyli xlim/(xlim+ylim), powinieneś zwiększyć wartość xOld. W przeciwnym razie zwiększ wartość yOld.

Użyj rand zamiast randi.

Answer 3

Jedną opcją byłoby określenie kierunku wyboru stosunku wymiarów, np.

DirectionChange = rand(1); 

if DirectionChange < y/(x+y) 
    yNew = yOld + 1; 
    xNew = xOld; 
else 
    xNew = xOld + 1; 
    yNew = yOld; 
end 

Czy są jakieś wymagania, które powinny być na bieżąco? na przykładStała krok rozmiar

EDIT: Bardziej skuteczna strategia, aby uniknąć uderzenia „ściany”:

DirectionChange = rand(1); 

% distance left to the end 
xLeft = x - xOld; 
yLeft = y - yOld; 

if DirectionChange < yLeft/(xLeft+yLeft) 
    yNew = yOld + 1; 
    xNew = xOld; 
else 
    xNew = xOld + 1; 
    yNew = yOld; 
end