Köpfe zu zählen - Dynamische Programmierung

Problem:

Gegebenen natürlichen zahlen n und k, zusammen mit p1,p2,..., pn; where pi ε [0, 1] Sie möchten bestimmen Sie die Wahrscheinlichkeit, genau k Köpfe, wenn n voreingenommen Münzen geworfen werden unabhängig voneinander nach dem Zufallsprinzip, wobei pi ist die Wahrscheinlichkeit, dass die ith Münze kommt Köpfe. Geben Sie einen O(n2) Algorithmus für diese Aufgabe. Angenommen, Sie können multiplizieren und addieren zwei zahlen in [0, 1] in O(1) Zeit.

Kann mir jemand helfen, mit der Entwicklung des recurrence relation, so dass ich es code. (Die Frage kommt von hinten Ausübung Kapitel Dynamische Programmierung im Buch "Algorithmen, die Von Dasgupta")

InformationsquelleAutor Gaurav | 2012-10-27
  1. 13

    Betrachten Sie die situation, wenn (n-1) Münzen geworfen, zusammen und die N-te Münze geworfen wird, auseinander und berücksichtigen die gegenseitige Unabhängigkeit.

    Kombinieren Wahrscheinlichkeiten von einfacheren Fällen zu P(1..n, k) (wobei P(1..n, k) ist die Wahrscheinlichkeit, genau k-Köpfe bei n Münzen)

    Dann diese Regel anwenden, und füllen Sie alle Zellen in NxK Tabelle

    Edit:

    Gibt es zwei mögliche Wege, um genau k-Köpfe mit n Münzen -

    a) wenn (n-1) k-Münzen haben Köpfe, und der N-TEN Münze ist Schwanz, und

    b) wenn (n-1) - Münzen haben k-1 Köpfe, und der N-TEN Münze ist Kopf

    so

    P(n, k) = P(n-1, k) * (1 - p[n]) + P(n-1, k-1) * p[n]

    • So können wir dieses recurrence relation: P(N,K) = max { P(N-1,K), P(N-1,K-1)} + p<sub>ich</sub> Und starten Sie mit P(n,k)
    • sorry, ich weiß nicht, wie man Tiefgestellt schreiben hier. p<sub>ich</sub> ist p mit einem index i
    • Nein, wir brauchen nicht zu wählen Sie maximal. Sie haben zu calc) Wahrscheinlichkeit, nicht optimale irgendeiner Art.
    • Was also wird die Wiederholung Beziehung dann?
    • Ich hatte gehofft, für eine Lösung mit einigen hinweisen... OK, das Verhältnis Formel
    InformationsquelleAutor MBo
Schreibe einen Kommentar