2

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

最短経路アルゴリズムは、通貨取引に適用できます。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への最短経路の存在を主張します。

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

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

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

4

1 に答える 1

1

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

于 2012-10-08T05:41:43.370 に答える