Fórum Root.cz
Hlavní témata => Vývoj => Téma založeno: Cajova_Houba_2 28. 04. 2015, 13:15:00
-
Zdravim, mám následující problém.
Mám několik událostí (na těch nezáleží) a kadžá z nich má přiřazenou určitou pravděpodobnost. Součet pravděpodobností je 1. V programu budu náhodně generovat čísla v <0;1) a podle vygenerovaného čísla se vykoná událost. Nejsem si uplně jistej, jak to udělat. Zatim mě napadlo následující
mam události a k nim pravděpodobnosti např A(p_a), B(p_b), C(p_c), .....
Budu generovat náhodná čísla r z intervalu <0;1*max(p)).
Pak budu r postupně porovnávat s pravděpodobnostma od nejnižší a pokud bude r<=p, vykoná se příslušná událost.
Když bych to měl ukázat na konkrétním příkladu:
A(0.1), B(0.2), C(0.7) r je z intervalu <0;0.7)
r= 0.47 => C
r= 0.1 => A
r= 0.15 => B
...a tak dál
Nejsem si ale uplně jistej správností mýho řešení, takže bych vás rád požádal o nějakou radu.
Díky
-
Jestli to správně chápu, chceš něco jako (pseudokod):
double nahoda = get_random_between_0_and_1();
double jevy[pocet_jevu] = get_all_cases_probabilities(); // soucet vsech jevu je 1.0
double mezisoucet = 0.0;
foreach jev in jevy {
if (nahoda - mezisoucet <= jev) zasah(); // muzes pouzit < misto <=
else mezisoucet += jev;
}
Neříkám že je to nejjednodušší nebo nejhezčí, ale dá se to tak ;)
-
Jo, trochu sem se v tom rejpal a nakonec sem došel k stejnmýu principu, jenom tak nějak z druhý strany :D Vypadá to, že je to ono, takže díky za pomoc
-
asi nejrychlejsi a pritom relativne jednoduche je si vytvorit serazene pole tech jevu. Takze napr:
pole[0]=jev<0.0;0.1)
pole[1]=jev<0.1;0.3)
pole[2]=jev<0.3;0.5)
...
A pak vyber pulenim:
1. dostanu pole,
2. strelim na stred
3. jsem tam, kde chci byt?
a. ano - konec
b. chci mensi, vezmi vsechno nalevo ode me jako pole a jdi do bodu 1.
c. chci vetsi, vezmi vsechno napravo ode me jako pole a jdi do bodu 1.
-
Tyhle řešení nebudou fungovat, když budu mít A(0.25), B(0.25), C(0.25), D(0.25). Správné řešení je udělat to přes diskrétní rozložení pravděpodobnosti:
http://www.cplusplus.com/reference/random/discrete_distribution/
-
Jen takovy dotaz, proc by ten vas pripad nefungoval? Jen proste nageneruju tu tabulku takhle:
pole[0]=A<0.0;0.25) pro A(0.25)
pole[1]=B<0.25;0.5) pro B(0.25)
pole[2]=C<0.5;0.75) pro C(0.25)
pole[3]=D<0.75;1.0) pro D(0.25)
-
Proc nestaci jednoduse vygenerovat nahodne cislo r z (0,1) a podle jeho velikosti rozhodnout?
r < 0.1 => A (delka intervalu je 0.1)
0.1 < r < 0.3 => B (delka intervalu je 0.2)
0.3 < r < 1 => C (delka intervalu je 0.7)
Tedy pokud toto opravdu odpovida zadani. Z toho, co je napsano v puvodni prispevku neni uplne jasne, ceho vlastne chce dosahnout.
-
To je to, co presne delam. Jen potrebujete nejak najit ten sprany prvek. Tzn. musim je mit nekde ulozeny a pak je projit. Prvni moznost je zkusit postupne vsechny a vybrat ten, ktery odpovida (linearni slozitost). Druha moznost je ta moje, je trochu slozitejsi, ale pro velka pole zarucene rychlejsi (logaritmicka slozitost).
-
Ono to bude fungovat za předpokladu, že vygenerované náhodné číslo má uniformní rozložení pravděpodobnosti (což je většinou pravda, ale obecně to neplatí). Řešení none_ selže, pokud bude existovat událost s pravděpodobností 0, protože má uzavřený interval <0, N), takže mu to bude generovat i události s pravděpodobností 0. Obecně je lepší nevynalézat znovu kolo a použít ověřené řešení, které netrpí podobnými neduhy.
-
To diskrétní rozdělení pravděpodobnosti vypadá (a nejspíš taky bude) nejspolehlivěji, takže použiju to. Díky za rady :)
-
Součet pravděpodobností je 1.
...
Budu generovat náhodná čísla r z intervalu <0;1*max(p)).
Když bych to měl ukázat na konkrétním příkladu:
A(0.1), B(0.2), C(0.7) r je z intervalu <0;0.7)
r= 0.47 => C
r= 0.1 => A
r= 0.15 => B
...a tak dál
No to si snad děláš legraci, ne? :)
Musíš generovat čísla z intervalu <0;1):
0----0.1----0.3----1
teprve teď velikosti intervalů jsou v poměru 1:2:7
Správné řešení je udělat to přes diskrétní rozložení pravděpodobnosti:
http://www.cplusplus.com/reference/random/discrete_distribution/
discrete_distribution je jenom obálka, která udělá to, co chtěla čajová houba udělat ručně v úvodním příspěvku.
"Správnost řešení" záleží na tom a pouze na tom, jestli použitý RNG (ať už se jedná o RNG použitý v discrete_distribution nebo o RNG použitý při "ručním" řešení) skutečně generuje rovnoměrné rozdělení pravděpodobnosti.
O generátorech náhodných čísel nic nevím, ale selským rozumem předpokládám, že každý generátor, který rovnoměrné rozdělení negeneruje, je považován za vadný, a čekal bych že generátory zabudované v C++ vadné nebudou.
Pokud se toho ale bojíš, pak místo generátoru který generuje typ real, použij generátor typu integer (pro tvou vzorovou úlohu s pravděpodobnostmi 0.1, 0.2, 0.7 by generoval čísla 0 až 9). Ten by snad mouchy mít neměl
-
píšu moc zkratkovitě:
discrete_distribution je jenom obálka, ve které je ten RNG. A o ten jde.
-
discrete_distribution je jenom obálka, která udělá to, co chtěla čajová houba udělat ručně v úvodním příspěvku.
Ano, udělá to přesně to, co chtěl autor udělat ručně v úvodním příspěvku. To je ta pointa, nemusí to dělat ručně :)
O generátorech náhodných čísel nic nevím, ale selským rozumem předpokládám, že každý generátor, který rovnoměrné rozdělení negeneruje, je považován za vadný, a čekal bych že generátory zabudované v C++ vadné nebudou.
Tak to předpokládáš špatně, jen na ukázku:
http://en.cppreference.com/w/cpp/numeric/random/normal_distribution
http://en.cppreference.com/w/cpp/numeric/random/poisson_distribution
http://en.cppreference.com/w/cpp/numeric/random/binomial_distribution
-
Tak to předpokládáš špatně, jen na ukázku:
http://en.cppreference.com/w/cpp/numeric/random/normal_distribution
http://en.cppreference.com/w/cpp/numeric/random/poisson_distribution
http://en.cppreference.com/w/cpp/numeric/random/binomial_distribution
A to dokládá co? To jsou rozdělení, nikoli RNG
Mimochodem, všechna ta rozdělení budou pravděpodobně fungovat úplně stejně jako discrete_distribution: budou využívat ten stejný vestavěný RNG jako využívá discrete_distribution.
-
A to dokládá co? To jsou rozdělení, nikoli RNG
std::normal_distribution není žádné rozdělení, je to *generátor* náhodných čísel s normálním (Gaussovým) rozložením pravděpodobnosti. Jak je to implementováno je nepodstatné, může to být adaptér nad generátorem s uniformním rozdělením nebo cokoliv jiného. Důležité je, k čemu se to používá, a to je generování náhodných čísel s normálním (Gaussovým) rozložením pravděpodobnosti.
-
std::normal_distribution není žádné rozdělení, je to *generátor* náhodných čísel s normálním (Gaussovým) rozložením pravděpodobnosti.
Ne.
C++ neznám, jenom vím, že je to ten programovací jazyk co se s nimi programují počítače. Přesto mi teď stačila minuta, abych našel toto:
Generators: Objects that generate uniformly distributed numbers.
Distributions: Objects that transform sequences of numbers generated by a generator into sequences of numbers that follow a specific random variable distribution, such as uniform, Normal or Binomial.
Takže generátory opravdu (aspoň podle dokumentace na cplusplus.com) generují čísla "uniformly" (tj. generují rovnoměrné rozdělení), a je jedno, jestli čajová houba použije discrete_distribution nebo si těch pár řádek napíše sama.
-
C++ neznám, jenom vím, že je to ten programovací jazyk co se s nimi programují počítače.
Když něco neznáš, tak se k tomu raději nevyjadřuj. Kdyby sis tu dokumentaci přečetl celou, tak by ses dozvěděl že:
http://en.cppreference.com/w/cpp/numeric/random/normal_distribution
Generates random numbers according to the Normal (or Gaussian) random number distribution.
-
:) samozřejmě, že náhodná čísla může generovat nejenom "generator". Ale už to není "generator" ve smyslu
Generators: Objects that generate uniformly distributed numbers.
Ale to se bavíme o ne tolik podstatné věci, tj. o definici slovíček.
podstatné je, že to, co jsi tvrdil na začátku, je nesmysl: není pravda, že je třeba použít discrete_distribution, lze použít jakýkoli "generator" (ve smyslu definice na cplusplus) a napsat si kód na něm založený.
-
Slowthinker ma pravdu. Distribuce nejsou generatory nahodnych cisel ale obalky nad nima - a kdyz se rekne vygeneruj nahodne cislo, tak kazdy dusevne zdravy clovek, ktereho nebavi si honit ego, predpoklada pouziti generatoru nahodnych cisel - a ten uniformni proste je. Howgh.
-
:) tak v zásadě lze sousloví "generátor náhodných čísel" chápat dvěma způsoby
a) jako terminus technicus, tedy TEN generátor co je uniformní
b) jako cokoli co generuje čísla náhodným způsobem (ale rozumně uvažující člověk to takto nepoužije, aby se to nepletlo s a)
gamer míchá a) a b)
-
Tohle mě nebaví, ale zkusím to ještě jednou. std::normal_distribution neslouží k výpočtu rozložení pravděpodobnosti, ale k výpočtu náhoných čísel s normálním rozložením pravděpodobnosti. Je to věc, která je navržená jako generátor náhodných čísel, vypadá jako generátor náhodných, funguje jako generátor náhodných čísel a používá se jako generátor náhodných čísel. Prohlásit o tom, že to není generátor náhodných čísel je poněkud... nemoudré. Ano, dalo by se to použit i k výpočtu hustoty pravděpodobnosti, ale není to k tomu navrženo a nepoužívá se to tak.
Pokud si pod pojmem generátor náhodných čísel představíte jen věc, která generuje integery s uniformním rozložením pravděpodobnosti, tak máte dost omezené obzory. Každý generátor náhodných čísel má nějaké vlastnosti a rozložení pravděpodobnosti je jedna z těch klíčových.