2

レンタルバイクのウェブサイトを開発しています。私が抱えている問題は、ゲストをバイクに割り当てるという問題を効率的に解決する方法です。「ばかげた」方法でそれを行う方法は知っていますが、この種の問題を解決する古典的なアルゴリズムがあるかどうかを知りたいです。ホテルの客室へのゲストの割り当てと同じ問題です。この最後の例では、効率の悪いスケジューリングのために予約を拒否しないことで、最大占有率を達成することを目標としています。

この問題は、既知の解決策を持つ古典的な問題であるに違いないと確信しています。

どうもありがとう。

4

2 に答える 2

1

あなたが興味を持っているのはInterval Schedulingと呼ばれるものです。すべての予約の重みが同じであると仮定すると (どの予約も優先されません)、貪欲なアルゴリズムが必要になります。

ここ (pdf)は、このトピックに関する優れたスライドです。

基本的に、最も早い終了予約を最初にスケジュールします。

于 2010-08-17T21:15:43.037 に答える
0

これはインターバルスケジューリングですが、オンラインアルゴリズムです。さらに読みたい場合は、ここで読むことができます:

http://www-bcf.usc.edu/~dkempe/teaching/online.pdf

于 2010-08-18T05:26:56.530 に答える