アポイントメントスケジューリングアルゴリズム（N人の空き時間スロットを持つN人、制約充足）に似た何かをしたいです。Hopcroft-Karp アルゴリズムを使用します。しかし、私の追加の要件は、時間間隔が重複していることです。例えば。時間枠は、午前 10 時から午前 11 時まで、または午前 10 時 15 分から午前 11 時 15 分までです。したがって、午前 10 時から午前 11 時までのスロットを選択した場合、午前 10 時 15 分から午前 11 時 15 分までのスロットは選択したくありません。パフォーマンスに悪影響を与えることなくこれを達成することは可能ですか?
質問する
3354 次
1 に答える
1
ある種のフロー エキスパンダーを使用してタイム スロットを区別する別のレベルを追加すると、Hopcroft-Karp で提案したものと同様のフロー アルゴリズムを使用できます。
したがって、ソースが人に接続され、人がタイム スロットに接続され、タイム スロットがタイム ブレークダウンに接続され、ブレークダウンがシンクに接続されます。
内訳をさらに説明するために、10:00、10:15、10:30、および 10:45 に開始するタイムスロットがあるとします。時間内訳は 15 分です。すべての会議の長さが 1 時間の場合、10:00 のタイム スロットは 10:00-10:15 の内訳と、10:15-10:30、10:30-10:45、および 10:45 に接続されます。 -11:00故障。
タイムスロットと内訳の間の接続で、いくつかの変更されたロジックが必要になります。これは、タイムスロットの入力とブレークダウンへの接続との間でフロー値が変化する必要があるためです。これは、1 人の人物がタイム スロットに割り当てられると (タイム スロットの流入 = 1)、内訳への複数のフローが存在するためです (タイム スロットの流出 = 上記の例では 4)。
私がこれを試していない1つの免責事項。もしそうなら、それがどのように機能するか/どのように機能するか教えてください.
于 2014-06-10T12:52:23.907 に答える