headerphoto

Problem n-królowych - Szacowanie wydajności algorytmu z powrotami

Metoda Monte Carlo

Algorytm Monte Carlo zaliczany jest do rodziny algorytmów probabilistycznych, czyli algorytmów, w których następna wykonywana instrukcja określana jest czasami w sposób losowy. Często stosuje się tą metodę do określania wydajności algorytmów z powrotami. Dzięki niej, jesteśmy w stanie oszacować z dosyć dużą dokładnością jak wiele elementów z określonej struktury danych musi zostać przeanalizowanych przez testowany algorytm. Przekładając to na teorię grafów, powiemy że metodą Monte Carlo możemy oszacować ilość sprawdzonych węzłów przez algorytm z powrotami w całym drzewie przestrzeni stanów.

Właściwie jedyną informacją, jaką dostarcza nam metoda Monte Carlo to szacunkowa liczba odwiedzonych węzłów. Na pozór nie jest to wiele, jednak już taka wiedza pozwala skuteczne monitorować zachowanie testowanego algorytmu w starciu z dowolnie dużą strukturą danych. W ten sposób, możliwe jest dokładne oszacowanie wydajności algorytmu z powrotami tylko i wyłącznie na podstawie jego strategii działania.

Omówienie algorytmu szacowania dla problemu n-królowych

Aby możliwe było zastosowanie metody Monte Carlo, testowany algorytm z powrotami musi spełniać dwa podstawowe warunki:

  • we wszystkich węzłach na tym samym poziomie drzewa przestrzeni stanów powinna być używana ta sama funkcja określająca, czy węzeł jest obiecujący
  • węzły na tym samym poziomie w drzewie przestrzeni stanów muszą mieć taką samą liczbę węzłów potomnych

Algorytm z powrotami dla problemu n-królowych spełnia oba powyższe warunki. Na każdym poziomie drzewa przestrzeni stanów używana jest ta sama funkcja określająca czy dany węzeł jest obiecujący czy też nie (metoda czy_Obiecujacy). Jeśli zaś chodzi o drugi warunek to każdy węzeł (nie będącym liściem) na tym samym poziomie drzewa przestrzeni stanów ma identyczną ilość węzłów potomnych. Dzieje się tak, ponieważ liczba potomków odnosi się do ilości pól w wierszu na szachownicy. Jest to oczywiście wartość stała dla każdego węzła i zawsze wynosi n.

... "Chybił-trafił" ...

Strategia metody Monte Carlo jest następująca. Najpierw algorytm określa zbiór węzłów obiecujących na pierwszym poziomie drzewa przestrzeni stanów. Zbiór ten można porównać do puli bezpiecznych miejsc w danym wierszu na szachownicy (czyli pozycji które nie znajdują się w polu rażenia żadnej innej królowej). Algorytm typuje losowo jeden węzeł z tego zbioru i ustawia tam królową. Następnie przechodzi o poziom niżej i znowu określa zbiór węzłów obiecujących, losuje kolejny węzeł i przypisuje mu następną królową. Taki schemat postępowania powtarzany jest do momentu ustawienia figur we wszystkich wierszach szachownicy lub dopóki algorytm nie dotrze do ślepego zaułka (gdy żadne z pól w danym wierszu nie umożliwia już bezpiecznego ustawienia królowej). Szczegółowe przedstawienie tego algorytmu znajdziesz w 1

Ten interesujący sposób pseudolosowego ustawiania królowych na szachownicy opiszę dokładniej na przykładzie szachownicy o wymiarach 5x5. Bezpieczne pola (węzły obiecujące) zostały zaznaczone na szachownicy zielonym kwadratem, zaś pola atakowane przez którąś z królowych (będą to węzły nieobiecujące) wyróżniłem czerwonymi kropkami.

Strategia postępowania metody Monte Carlo.

- Algorytm rozpoczyna analizę od wiersza 1. Jako że szachownica jest jeszcze pusta, wszystkie pola w tym wierszu są uznane za bezpieczne. Algorytm losuje więc jeden węzeł ze następującego zbioru węzłów: [1,1], [1,2], [1,3], [1,4], [1,5].
- Wylosowany został węzeł [1,4]. Algorytm wstawia w tym polu królową, określa jej pole rażenia i przechodzi o poziom niżej określając zbiór bezpiecznych węzłów w wierszu 2. Są to pola odpowiadające węzłom [2,1] oraz [2,2].
- Algorytm wylosował węzeł [2,2]. Umieszcza tam królową i przechodzi do wiersza 3, szukając bezpiecznego pola dla kolejnej królowej. Tym razem jest tylko jedno takie pole (węzeł [3,5]).
- Algorytm nie mając żadnego wyboru umieszcza królową w polu [3,5]. Przechodzi do wiersza 4 i znajduje znowu jedno bezpieczne pole (węzeł [4,3]).
- Tak jak poprzednio, królowa wędruje do jedynego bezpiecznego pola (węzeł [4,3]), a algorytm analizując kolejny (ostatni) wiersz na szachownicy, znajduje bezpieczne pole w węźle [5,1].
- Ostatnia królowa umieszczona zostaje w polu [5,1].

Efektem działania algorytmu Monte Carlo jest ścieżka składająca się z węzłów obiecujących, wytypowanych drogą losowania. Dzięki temu możliwe jest oszacowanie, na podstawie ilości węzłów obiecujących na każdym etapie, ilości wszystkich węzłów sprawdzonych przez algorytm z powrotami (dla dowolne dużej szachownicy). Aby jednak oszacowanie było dokładne, należy przeprowadzić co najmniej 15 prób dla danej szachownicy, a potem wyznaczyć średnią arytmetyczną z uzyskanych wyników.



1 Vijay V. Vazirani, Algorytmy aproksymacyjne, Wydawnictwo Naukowo - Techniczne.