algorithm - 外貨両替の最も有利なシーケンスを見つける

Question

私は自分の本から次の演習を行っています。

最短経路アルゴリズムは、通貨取引に適用できます。c ₁、c ₂、。。。、cn_はさまざまな通貨です。たとえば、c ₁はドル、c ₂ポンド、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への最短経路の存在を主張します。

この問題を解決するために私が考えた方法は、このアルゴリズムに従うことです。

1. グラフのすべてのエッジを無効にします
2. 有向非巡回グラフの最短経路アルゴリズムを実行します。

これでうまくいくと思いますが、よくわかりません。グーグルで私は別のステップを含むいくつかの解決策を見つけました：対数を使用してレートの乗算を加算に変換します。このステップは彼女にとって必要ではないと思いますが、それでもわかりません。

Answer 1

GoogleやStackOverflowを使用して解決策を見つけようとするのをやめ、しばらく考えてみてください。さまざまな情報源からリソース、情報、アイデアを収集することで多くの問題を解決できますが、解決できない問題もあります。コンピュータをスリープ状態にします。静かな場所を探しに行きます。アイデアが浮かぶまで考えてみてください。スクラップペーパーまたはホワイトボードにサンプルグラフを作成します。やってみよう。それが機能するかどうかを確認します。理由がわからない場合は、新しいアイデアを見つけてください。もしそうなら、それが機能しない有効なグラフを考えてみてください。すべてのグラフで機能するアルゴリズムがあることを確信したら、これで完了です。解決策を教えてもらうだけでは、多くを学ぶことはできません。