Zásada odloženého rozhodnutí - Principle of deferred decision

Tento článek obsahuje seznam obecných Reference, ale zůstává z velké části neověřený, protože postrádá dostatečné odpovídající vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Červenec 2016) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Zásada odložených rozhodnutí je technika používaná při analýze randomizované algoritmy.

Definice

A randomizovaný algoritmus provede sadu náhodných voleb. Tyto náhodný možnosti mohou složitě souviset, takže je obtížné je analyzovat. V mnoha z těchto případů Zásada odložených rozhodnutí se používá. Princip spočívá v tom, že celá sada náhodných voleb se neprovádí předem, ale spíše pevně, jen když jsou odhaleny algoritmu.

Aplikace

Hodinová solitaire hra

Princip se používá k vyhodnocení a stanovení pravděpodobnosti „výhry“ z a balíček karet. Myšlenkou je nechat se náhodná rozhodnutí rozvinout, dokud iterace neskončí na 52, kde pokud je čtvrtá karta vytažena ze skupiny označené „K“, hra končí.^{[Citace je zapotřebí ]}

Reference

Zdroje

• M. Mitzenmacher a E. Upfal. Pravděpodobnost a výpočet: Randomizované algoritmy a pravděpodobnostní analýza. Cambridge University Press, New York (NY), 2005. Oddíl 1.3, strana 9.

Tento algoritmy nebo datové struktury související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.