0

A、B、C の 3 つの人気ビーチ リゾートが並んでいます。

                    A-----(1km)-----B-----(1km)------C.

リゾート間の距離は 1k です。ジョンは、ビーチ リゾート A とビーチ リゾート C にある別のアイスクリーム トラックを所有しています。明日、アイスクリームを欲しがっている子供たちでいっぱいの 2 台のバスがビーチ リゾート (A、B、C) に到着しますが、ジョンは来ません。各バスがどのリゾートに向かうか、各バスがいつ到着するかを把握します (バスは異なる時間に到着する可能性があります)。彼は、バスがビーチ リゾートに到着したらすぐに、アイスクリーム トラックを現在の場所からビーチ リゾートに派遣する予定です。各トラックは 1 つのビーチ リゾートにのみサービスを提供できます。つまり、トラックがビーチ リゾートに派遣されると、1 日中そこに留まらなければなりません。ジョンは、バスの場所に到達するためにトラックが移動する距離の合計を最小化するアルゴリズムを設計したいと考えています。

すべての決定論的アルゴリズム ALG について、ALG の下でジョンのトラックが移動する合計距離が 3OPT であるシナリオ (つまり、バスの到着予定と場所) があることを示します。ここで、OPT はそのシナリオにおける最適解の値です。

4

1 に答える 1

0

あなたはすでにコメントで1つの戦略について説明しました。少し変更します：

子供たちがその場所に到着するまでトラックはその場所にとどまり、その場所に向かってトラックを移動させるという戦略を立てましょう。次に、子供たちがBに到着するので、AにあるトラックがBに配車されます。今度は2台目のバスがAに到着するので、CにあるトラックをAに配車する必要があります。トラックの移動距離の合計は3kmです。

この戦略では、距離が3*OPT

このシナリオでは、他に意味のある戦略がいくつあるか考えてみてください (ヒント: それほど多くはありません)。それらすべてについてそのようなケースを説明すれば、完了です。

于 2012-12-02T19:04:38.537 に答える