Matematické Fórum

Mějme následující situaci:

Máme orientovaný graf mající alespoň 3 uzly (a počet uzlů je pevně daný) takový, že existují právě dva uzly S a F (jako success a failure), ze kterých nevedou žádné hrany, a vede do nich vždy alespoň jedna hrana. Pro ostatní uzly U existuje vždy alespoň jedna hrana, která do nich vede, a alespoň jedna hrana, která z nich vede do nějakého jiného uzlu. Existuje i možnost vlastní smyčky, tj. pro nějaký uzel U existuje hrana, která vede do něho samotného. Každé hraně je pevně přiřazena určitá pravděpodobnost, že bude provedena. Součet pravděpodobností všech hran vycházejících z nějakého libovolného uzlu mimo uzlu S a F je roven 1, přirozeně. V grafu jsou kružnice.

Pro každý uzel mimo uzlů S a F potřebuji spočítat pravděpodobnost, že se náhodnou procházkou respektující pravděpodobnosti jednotlivých hran dostanu dostanu do uzlu S značícího úspěch. Pokud se dostanu do uzlu F, tak z něho nevede žádná hrana, takže to je neúspěch.

Zatím mám dva algoritmy, které toto řeší. První je prohledávání do hloubky s omezenou hloubkou, kdy pro daný uzel násobím pravděpodobnosti hran jak je po nich procházeno, tohle funguje pro malé grafy a některé velké pokud mají málo kružnic. Je ale velmi pomalý pro některé grafy, a někdy neskončí ani po mnoha hodinách.

Druhý algoritmus je MonteCarlo metoda, která je velmi pomalá, funguje tak že vysílá náhodné "mravence" z uzlu a počítá poměr mravenců kteří dorazili do cíle S děleno celkovým počtem vyslaných mravecnů.

Pravděpodobnosti potřebuji vypočítat alespoň s přesností na 8 desetinných míst. Výpočet potřebuji rychlý proto, protože grafy jsou evolvovány genetickým algoritmem, a hledá se takový graf s fixním počtem uzlů, u kterého je pro všechny uzly největší pravděpodobnost, že se z nich dosáhne cíle S.

V mém konkrétním případě je pravděpodobnost dosažení cíle S mírně menší než F, ale potřebuji maximalizovat šanci, že bude dosaženo S, na počtu kroků nezáleží.