4

次の問題：

エンジン（たとえば車）は、まっすぐな道を進みます。その消費量は距離に正比例します（たとえば、480 kmは1単位の燃料を使用するため、48kmは10単位の燃料を使用します）。このエンジンは、最大1単位の燃料を輸送できます。

開始点には、n0燃料ユニットの供給があります。ルート上のさまざまなポイントに燃料貯蔵庫があり（たとえば、n1 @ d1、n2 @ d2など）、ドライバーはルート上のどこにでも燃料を降ろすことができます。たとえば、1ユニットの値が480 kmの場合、ドライバーは160 kmを運転して、1/3ユニットの燃料でデポを作成し、エンジンに燃料を補給するために開始点に戻ることができます。

ルート上の開始燃料とデポに応じて達成できる最大距離を見つけるためのアルゴリズム（またはそれを見つけるためのいくつかのアイデア）を探しています。

4

2 に答える 2

1

直感的には、欲張りアルゴリズムが最適である必要があります。つまり、各デポで利用可能な燃料の量を最大化することで、可能なルートを最大化できます。これは私の意見であり、「ルート上のどこでも」は「実際にはどのデポでも」だと思います。

欲張りアルゴリズムはどのように機能しますか？それぞれの時点で、「前に進む」または「前のデポに戻って補充する」の2つの決定しかありません。貪欲は、現在のデポの予備を増やす限り、常に後退します。

于 2012-12-11T13:12:10.093 に答える
1

a *、dijkstraメソッドで使用される「<=」比較を「反転」することもできると思います。

または、ロジックパラメータ（最良、最悪）パスを追加します。

したがって、コードを繰り返さなくても同じパス検索を維持できます。

于 2012-12-11T13:15:08.220 に答える