Implementacja metody Monte Carlo w C++
Tak jak w przypadku algorytmu z powrotami, również implementacja algorytmu Monte Carlo sprowadza się
do zaprojektowania dwóch metod. Pierwsza z nich, nazwijmy ją oszacowanie_MonteCarlo, odpowiada za
tworzenie zbioru węzłów obiecujących, realizację procesu losowania pojedynczego węzła oraz szacowanie
ilości węzłów sprawdzonych. Aby jednak funkcja wiedziała, które węzły zaklasyfikować do zbioru węzłów
obiecujących, potrzebna jest druga metoda czy_Obiecujacy, zaczerpnięta
z algorytmu z powrotami rozwiązującego problem n-królowych.
Metodę oszacowanie_MonteCarlo można zaprogramować za pomocą języka C++ w następujący sposób:
long double oszacowanie_MonteCarlo (int n) { int i, j; int liczba_ob_potomkow; long double suma_ob_potomkow, ilosc_spr_wezlow; Set < int, 1, 101 > obiecujacy_potomek; // deklaracja struktury danych i = 0; ilosc_spr_wezlow = 1; liczba_ob_potomkow = 1; suma_ob_potomkow = 1; while (liczba_ob_potomkow != 0 && i != n) { suma_ob_potomkow = suma_ob_potomkow * liczba_ob_potomkow; ilosc_spr_wezlow = ilosc_spr_wezlow + suma_ob_potomkow * n; i++; liczba_ob_potomkow = 0; obiecujacy_potomek.Clear(); // czyszczenie struktury danych for (j = 1; j <= n; j++) { col[i] = j; if (czy_Obiecujacy (i)) { liczba_ob_potomkow++; obiecujacy_potomek << j; // dodanie numeru obiecującego } // potomka do struktury danych } if (liczba_ob_potomkow != 0) { do // losowanie obiecującego potomka j = random(n+1); while (obiecujacy_potomek.Contains(j) == false); col [i] = j; } } return ilosc_spr_wezlow; }
Najważniejszym elementem metody oszacowanie_MonteCarlo jest pętla "while". Jest ona wykonywana dopóki na
danym poziomie drzewa przestrzeni stanów istnieją obiecujące węzły potomne (warunek: liczba_ob_potomkow != 0)
oraz póki algorytm nie znajduje się na ostatnim poziomie drzewa (warunek: i != n). Po każdym obrocie pętli
obliczana jest całkowita ilość obiecujących węzłów potomnych i sprawdzonych. Następnie algorytm czyści
strukturę danych obiecujacy_potomek, aby przygotować ją do zapisania informacji o obiecujących węzłach
na poziomie i. W pętli "for", algorytm ustawia we wszystkich polach wiersza i po jednej królowej (col[i] = j)
i sprawdza które ustawienia są bezpieczne. Pola nie będące w zasięgu żadnej innej królowej (spełniające zatem
warunek (if (czy_Obiecujacy(i)), są odnotowywane w strukturze obiecujacy_potomek, a ich ilość zapisywana w
zmiennej liczba_ob_potomków. Jeśli istnieje chociaż jeden obiecujący potomek na danym poziomie
(warunek: if (liczba_ob_potomkow !=0 )) to kolejnym krokiem jest wylosowanie jednego węzła z puli obiecujących potomków.
W tym celu należy wytypować liczbę z przedziału od 1 do n (j = random(n+1)), a następnie sprawdzić czy odpowiada
ona numerowi węzła w zbiorze obiecujących potomków. Jeśli tak, to uznajemy, że wylosowaliśmy bezpieczne pole na
szachownicy i ustawiamy tam królową (col[i] = j) w innym wypadku kontynuujemy losowanie aż do skutku (czyli do
momentu wylosowania liczby odpowiadającej numerowi węzła ze struktury obiecujących potomków). Aby losowanie odbywało
się w sposób prawidłowy, należy przed uruchomieniem algorytmu zainicjować generator liczb losowych (funkcja:
randomize()). Po zakończeniu symulacji, algorytm zwraca ilość sprawdzonych węzłów. Liczba ta może się okazać
bardzo duża, dlatego przechowywana jest w zmiennej typu long double.
PLIKI DO POBRANIA |
|