headerphoto

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

(PLIKI DO POBRANIA NA KOŃCU STRONY)

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
Nazwa
OS
Rozmiar Pobierz plik
Screenshot
Oszacowanie Monte Carlo
dla Problemu n-królowych (exe + src)
Windows 610 kb.
Oszacowanie Monte Carlo
dla Problemu n-królowych (exe + src)
AmigaOS 120 kb.