私は自分の本から次の演習を行っています。
最短経路アルゴリズムは、通貨取引に適用できます。c 1、c 2、。。。、cnはさまざまな通貨です。たとえば、c 1はドル、c 2ポンド、c3リラです。任意の2つの通貨ciとcjには、為替レートr i 、jがあります。これは、1単位のciと引き換えにri、j単位の通貨cjを購入できることを意味します。これらの為替レートは、r i、j・r j、i <1の条件を満たすため、通貨の単位ciから始める場合、それを通貨c jに変更してから、通貨c iに戻すと、最終的には1単位未満の通貨c iになります(違いはトランザクションのコストです)。(a)次の問題に対して効率的なアルゴリズムを提供します。一連の為替レートr i、j 、および2つの通貨sとtが与えられた場合、通貨sを通貨tに変換するための最も有利な一連の通貨交換を見つけます。この目標に向けて、通貨とレートを、エッジの長さが実数であるグラフで表す必要があります。
つまり、基本的に私たちがやりたいのは、最小化するのではなく、利益を最大化する必要があるということです。したがって、sからtまでの最長のパスを見つける必要があります。sからtへの最短経路の存在を主張します。
この問題を解決するために私が考えた方法は、このアルゴリズムに従うことです。
- グラフのすべてのエッジを無効にします
- 有向非巡回グラフの最短経路アルゴリズムを実行します。
これでうまくいくと思いますが、よくわかりません。グーグルで私は別のステップを含むいくつかの解決策を見つけました:対数を使用してレートの乗算を加算に変換します。このステップは彼女にとって必要ではないと思いますが、それでもわかりません。