Główna zawartość
Programowanie
Kurs: Programowanie > Rozdział 5
Lekcja 2: Losowość- Błądzenie przypadkowe
- Wyzwanie: Losowy wędrowiec
- Prawdopodobieństwo i rozkłady niejednostajne
- Wyzwanie: Wędrowiec
- Rozkład normalny liczb losowych
- Wyzwanie: gaussowskie błądzenie przypadkowe
- Specjalny rozkład liczb losowych
- Wyzwanie: lot Levy'ego
- Projekt: spryskiwacz do farb
© 2023 Khan AcademyWarunki użytkowaniapolitykę prywatnościInformacja o plikach cookie
Specjalny rozkład liczb losowych
Przyjdzie taki okres w waszym życiu, gdy nie będziecie chcieli równomiernego rozkładu wartości, albo rozkładu Gaussa. Wyobraźmy sobie na chwilę, że błądzicie w poszukiwaniu jedzenia. Przemieszczanie się w losowym kierunku po pewnym obszarze wydaje się raczej rozsądną taktyką na szukanie czegoś do jedzenia. W końcu nie macie pojęcia, gdzie znajduje się jedzenie, możecie więc po prostu szukać je w sposób losowy dopóki go nie znajdziecie. Problemem jednak jest to, że nasze poprzednie programy miały tendencję do wracania wiele razy do tego samego miejsca(co jest znane jako “nadpróbkowanie”). Jedną ze strategii na ominięcie tego problemu jest co jakiś czas robienie bardzo dużego kroku. To pozwoli naszemu Walkerowi przemierzać losowo określoną lokację, co jakiś czas przeskakując bardzo daleko w celu zmniejszenia częstotliwości nadpróbkowania. Ta odmiana błądzenia(znana jako lot Lévy'iego) wymaga niestandardowego zbioru prawdopodobieństw. Chociaż nie jest to dokładna implementacja lotu Lévy'iego, możemy rozkład tego prawdopodobieństwa opisać tak: im dłuższy krok, tym mniej prawdopodobne jest, że zostanie wybrany; im krótszy, tym bardziej prawdopodobne.
Wcześniej w tym rozdziale widzieliśmy, jak można utworzyć własny rozkład prawdopodobieństwa wypełniając tablicę wartościami (z paroma powtórkami, aby pewne wartości występowały częściej) albo testując wynik funkcji
random()
. Możemy zaimplementować lot Lévy'iego stwierdzając, że szansa na zrobienie dużego kroku wynosi 1%.var r = random(1);
// A 1% chance of taking a large step
if (r < 0.01) {
xstep = random(-100, 100);
ystep = random(-100, 100);
} else {
xstep = random(-1, 1);
ystep = random(-1, 1);
}
To jednak ogranicza prawdopodobieństwo do stałej liczby możliwości. Co mamy zrobić, jeżeli chcemy bardziej ogólną zasadę—im wyższy numer, tym większe prawdopodobieństwo, że zostanie wybrany? 3.145 będzie częściej wybierany niż 3.144, nawet jeżeli różnica pomiędzy tymi dwoma prawdopodobieństwami będzie minimalna. Innymi słowy, jeżeli
x
jest wartością losową, możemy odwzorować jego prawdopodobieństwo na osi w następujący sposób: y
= x
.Jeżeli będziemy w stanie odkryć jak wygenerować rozkład losowych liczb na podstawie powyższego wykresu, wtedy będziemy w stanie zrobić to dla każdej krzywej, której wzorem dysponujemy.
Jednym z rozwiązań jest wybór dwóch losowych wartości zamiast jednej. Pierwsza wartość losowa to po prostu wartość losowa. Natomiast druga będzie tak zwaną “kwalifikacyjną wartością losową.” Powie nam ona, czy powinniśmy użyć tej pierwszej, czy może wyrzucić ją i wybrać inną. Liczby, które łatwiej jest zatwierdzić będą wybierane częściej, a liczby które rzadziej się nadają nie będą wybierane zbyt często. Oto poszczególne kroki (na razie załóżmy tylko wartości losowe z przedziału od 0 do 1):
- Wybierz losową liczbę: R1
- Oblicz prawdopodobieństwo P zdarzenia, że R1 się kwalifikuje. Powiedzmy, że P = R1.
- Wybierz kolejną liczbę: R2
- Jeżeli R2 jest mniejsze niż P, znaleźliśmy naszą liczbę - R1!
- Jeżeli R2 nie jest mniejsze od P, wróć do kroku pierwszego i zacznij od nowa.
W powyższej sytuacji prawdopodobieństwo wybrania losowej wartości jest równe tej wartości. Powiedzmy, że wybierzemy R1 równe 0.1. Oznacza to, że R1 ma 10% szans na to, że zostanie uznane. Jeżeli wybierzemy R1 równe 0.83, szansa na uznanie wynosi 83%. Im wyższa wartość, tym wyższe prawdopodobieństwo, że zostanie użyta.
Oto funkcja (nazwana od Metody Monte Carlo, która z kolei jest nazwana na część Kasyna Monte Carlo), która implementuje powyższy algorytm, zwracając wartość losową z przedziału od 0 do 1. Ten program używa tych wartości by ustalać rozmiar elips, ale możemy używać tych wartości do wielu innych celów.
Ten kurs "Symulacje Natury" jest pochodną z "Natury Kodu " stworzonej przez Daniela Shiffmana, użytej pod licencją Creative Commons Attribution-NonCommercial 3.0 Unported License.
Chcesz dołączyć do dyskusji?
- Nie umiem tego zrobic, a wiec zaczne tu wypisywac trudne slowa w przeswiadczeniu, ze jestem madry(2 głosy)
- A jak się to robi, pomocy, dam piwko jak ktos pomoze(1 głos)