Matematické Fórum

slender

Ahoj,
řeším následující úlohu:

Stručné zadání: Mějme kurzovní lístek, na kterém je celkem $n$ měn a pro každé dvě měny $i$ a $j$ máme určen jejich směnný kurz $r_{i,j}$ (tedy za jednu jednotku měny $i$ dostaneme $r_{i,j}$ jednotek měny $j$ ). Navrhněte algoritmus, který pro zadaný kurzovní lístek zjistí, zda existuje způsob, jak postupným směňováním zbohatnout.

Dospěl jsem k následujícímu řešení, prý v něm ale mám chybu (algoritmus údajně detekuje jen výhodné cykly délky 2). Nemáte někdo prosím nějaký protipříklad, pro který by můj algoritmus nefungoval?

//forum.matweb.cz/upload3/img/2016-06/82494_kurzovni_listek.png

Edit: na argument, že detekuje jen cykly délky 2 mám protipříklad:

$\begin{matrix} & A & B & C & D\\ A & 1 & 0 & 0 & 2\\ B & 2 & 1 & 0 & 0\\ C & 0 & 2 & 1 & 0\\ D & 0 & 0 & 2 & 1 \end{matrix}$

Kondr · 13. 07. 2016 23:00

Pokud zlogaritmujeme délky hran, redukuje se úloha na detekci nagativních cyklů, pro tu lze požít Bellman-Fordův algoritmus:
https://en.wikipedia.org/wiki/Bellman%E … _algorithm

Matematické Fórum

#1 16. 06. 2016 15:09 — Editoval slender (16. 06. 2016 15:19)

Správnost algoritmu (hledání v ohodnoceném grafu)

#2 13. 07. 2016 23:00

Re: Správnost algoritmu (hledání v ohodnoceném grafu)

Zápatí