Menjačnica - Rešenje

Postavka

Problem možemo modelovati težinskim grafom u kom su valute čvorovi, a kursevi težine grana (grane postoje između svih parova različitih čvorova za koje je kurs strogo pozitivan). Problem se tada svodi na određivanje puta na najvećim proizvodom težina grana. Algoritmi za pronalaženje najkraćih puteva pronalaze put sa najmanjim zbirom težina grana. Da bi se proizvod sveo na zbir, moguće je upotrebiti logaritamsku funkciju (jer važi \(\log(xy) = \log{x} + \log{y}\)). Ona se može primeniti na svaku težinu grane (jer su kursevi pozitivni). Primetimo da se nakon logaritmovanja mogu dobiti i pozitivne i negativne težine grana. Ako je osnova logaritma veća od \(1\), logaritam je rastuća funkcija, pa se najveći proizvod dobija kada je najveći zbir. Mi umemo da nađemo najkraći put (kada je zbir najmanji), pa zato treba da težine grana zamenimo logaritmom za neku osnovu koja je manja od \(1\) (ili, ekvivalentno, da uzmemo negativne vrednosti logaritama za osnovu veću od \(1\)). Dakle, ako težinu svake grane \(k_{ij}\) zamenimo, na primer, vrednošću \(-\ln k_{ij}\), tada se polazni problem svodi na određivanje najkraćeg puta u grafu u kom težine grana mogu biti i negativne i on može biti rešen Belman-Fordovim algoritmom. Ako postoji arbitraža, tj. niz valuta tako da je \(k_{i_0, i_1}\cdot k_{i_1, i_2} \cdot \ldots \cdot k_{i_{m}, i_0} > 1\), tada je \(-\ln k_{i_0, i_1} - \ln k_{i_1, i_2} - \ldots - \ln k_{i_m, i_0} < 0\), tj. u transformisanom grafu postoji ciklus negativne težine, što se opet može ustanoviti Belman-Fordovim algoritmom.