Prawdopodobieństwo warunkowe i algorytm, który zadziwi Twoją panią od polskiego

15.06.2010 - Krzysztof Dryś
TrudnośćTrudnośćTrudność

Wielki przełom

Czy już widzicie, że jesteśmy gotowi do napisania naszego algorytmu? Umiemy już szybko liczyć $ Q[j][n+1] $, mając wcześniej policzone $ Q[i][n] $ dla wszystkich monet $ i $. To pozwoli nam zapisać następujący algorytm:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 Argumenty:
  x[1...T] = wyrzucone monety
  n = liczba wszystkich monet
  p[1...n][1...n] = prawdopodobieństwo przejścia z monety i do j
  w[orzeł, reszka][1...n] = prawdopodobieństwo wyrzucenia x za pomocą monety i
 Inicjalizacja:
  Dla wszystkich monet m:
   Q[m][1] = prawdopodobieństwo zaczęcia monetą m
   T[m][1] = Lista składająca sie tylko z monety m
 Dla k = 2...T
  Dla m = 1...n
   Policz Q[m][k]:
    Policz Q[j][k-1] * p[j][m] * w[m][ x[k] ] dla wszystkich monet j
    i = moneta dla której Q[j][k-1] * p[j][m] * w[m][ x[k] ] jest największe
    Q[m][k] = Q[i][k-1] * p[i][m] * w[m][ x[k] ]
    T[m][k] = lista T[i][k-1] z dołączoną monetą m na przedzie

Dla każdego k i dla każdej monety m wyznacza on ciąg monet , które najlepiej tłumaczy wyniki rzutów $ x_1 \ldots x_k $ przy założeniu, że ostatnim rzucie skorzystano z monety $ m $. W ten sposób udało się nam znaleźć ciąg monet, który najlepiej tłumaczy wyniki wszystkich rzutów $ x_1 \ldots x_T $.

Jak szybki jest ten algorytm? Żeby odpowiedzieć na to pytanie wystarczy przeanalizować jego główną pętlę. Żeby policzyć Q[m][k] dla konkretnego $ m $ potrzeba $ O(n) $ operacji (n to liczba monet), bo musimy policzyć $ Q[j][k-1] \cdot p[j][m] \cdot w[m][ x[k] ] $ dla wszystkich monet $ j $.

Jeżeli weźmiemy pod uwagę pętle wewnątrz których jest operacja liczenia Q[m][k], okaże się, że łączna złożoność algorytmu to $ O(n^2 \cdot T) $. Oznacza to, że jest liniowy względem liczby wyników rzutów monetą, a kwadratowy względem liczby monet.

5
Twoja ocena: Brak Ocena: 5 (1 ocena)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com