27

問題文

N 人の面接を希望する雇用主が 1 人いるため、N 人の面接枠を作成します。すべての人は、それらのスロットの空き時間スケジュールを持っています。可能であれば N 人を N スロットにスケジュールするアルゴリズムを与え、それが不可能な場合はフラグ / エラー / などを返します。可能な限り最速の実行時の複雑さは?

これまでの私のアプローチ

ナイーブ: N あります! N 人をスケジュールする方法。それらすべてを調べて、順列ごとに実行可能かどうかを確認します。の上！ ）

バックトラッキング:

  1. 1 人しか参加できない面接の時間枠を探します。その人をスケジュールし、候補者のリストから削除し、スロットを削除します。
  2. 1 つのスロットにのみ入ることができる候補者を探します。その人をスケジュールし、候補者のリストから削除し、スロットを削除します。
  3. そのような組み合わせがなくなるまで、1と2を繰り返します。
  4. 人を選び、利用可能なスロットの 1 つにランダムにスケジュールします。この操作を覚えておいてください。
  5. スケジュールが決まるまで、または解決できない競合が発生するまで、1、2、3 を繰り返します。スケジュールがある場合は、それを返します。解決できない競合がある場合は、バックトラックします。

これは O( n! ) の最悪のケースだと思います - これ以上良くはありません。

DP ソリューションもあるかもしれませんが、まだ見ていません。

他の考え

問題は NxN マトリックスで表すことができます。行は「スロット」、列は「人」、値は空きの「1」とビジーの「0」です。次に、この行列内で行と列が入れ替わった恒等行列を探します。ステップ 1 と 2 は、「1」が 1 つしかない行または列を探しています。(行列の階数が = N の場合、I は解があることを意味します。しかし、その逆は成立しません) 別の見方として、行列を重み付けされていない有向グラフ エッジ行列として扱うこともできます。次に、ノードはそれぞれ 1 つの候補と 1 つのスロットを表します。次に、グラフ内のすべてのノードが 1 つの出力エッジと 1 つの入力エッジを持つようにエッジのセットを探します。または、ノードが 2 つある場合は、2 部グラフになります。

マトリックスの例:

1 1 1 1
0 1 1 0
1 0 0 1
1 0 0 1
4

4 に答える 4

13

あなたが指摘したように、問題は二部グラフで最大の一致を見つける問題と同等です（頂点の1つのセットは人のセットであり、もう1つの頂点のセットはスロットのセットであり、人とスロットの間にエッジがありますその人がこのスロットに対応できる場合)。

この問題はHopcroft-Karp アルゴリズムで解決できます。

複雑さ O(n^(5/2)) 最悪の場合、グラフがまばらな場合はより良い。

于 2012-06-21T18:12:41.627 に答える
12

制約プログラミング アプローチに関しては、マトリックス アプローチやセット ベース アプローチなど、さまざまな方法でモデル化できます。

セットベースのアプローチは、高レベル CP 言語MiniZincで以下に示されています。s は、各タイムスロットに対応できる人です (セット表記を使用)。決定変数は配列 x (毎回どの人物に割り当てられるべきか) です。

「globals.mzn」を含めます。
整数: n = 4;

時間枠ごとの無料人数の割合
int のセットの配列 [1..n]: s =  
[{1,2,3,4}、
 {2,3}、
 {1,4}、
 {1,4}];


% 決定変数
% スロットへの人の割り当て (予約番号 1..n)
変数 1..n の配列 [1..n]: x;

解決する;満足する;

制約
  % 時間帯に指定された人が空いていることを確認してください
  forall(i in 1..n) (
    x[i] in s[i]
  )
  /\ % 各人が個別の時間枠を確保するようにします
  alldifferent(x)
;

出力 [ show(x) ];

モデルはこれらの 4 つのソリューションを (0.5 ミリ秒で) 出力します。たとえば、時間 1 は人 3 に割り当てられます。

×：[3、2、4、1]
----------
x: [2, 3, 4, 1]
----------
×：[3、2、1、4]
----------
×：[2、3、1、4]

MiniZinc モデルは次のとおりです。

マトリックス アプローチ モデルはここにあり (出力セクションなし)、標準の整数プログラミング アプローチを使用します:予定_スケジューリング.mzn 。

整数: n = 4;

% 行はタイムスロットです
% 列は人です
int の配列 [1..n, 1..n]: m = array2d(1..n, 1..n,
[
1、1、1、1、
0、1、1、0、
1、0、0、1、
1、0、0、1、
]);

% 決定変数
% スロットへの人の割り当て (予約番号 1..n)
変数 0..1 の配列 [1..n, 1..n]: x;

解決する;満足する;

制約
  forall(i in 1..n) (
    % 空きスロットを確保する
    sum([m[i,j]*x[i,j] | j in 1..n]) = 1

    /\ % 1 スロットおよび 1 人につき 1 つの割り当てを確保する
    sum([x[i,j] | j in 1..n]) = 1
    /\
    sum([x[j,i] | j in 1..n]) = 1
  )
;

このモデルの解決策は同じですが、別の (そしてより冗長な) 方法で提示されており、たまたま、セットベースのアプローチと同じ順序で示されています。

スロット 1: 3
スロット 2: 2
スロット 3: 4
スロット 4: 1
----------
スロット 1: 2
スロット 2: 3
スロット 3: 4
スロット 4: 1
----------
スロット 1: 3
スロット 2: 2
スロット 3: 1
スロット 4: 4
----------
スロット 1: 2
スロット 2: 3
スロット 3: 1
スロット 4: 4
于 2012-06-21T18:38:15.640 に答える
3

ネットワーク フローを使用できると思います。

  • u_i候補iの頂点v_jとスロットの頂点を作成しますj。
  • ソース ノードを作成し 、容量 1 のそれぞれにs(有向) エッジを配置します。su_i
  • シンク ノードを作成し、容量 1 の各totからエッジを配置します。v_jt
  • 候補者がスロット で面接できる場合は、 からu_iを優位に立てます。v_jij
  • O(N)頂点とエッジがあり、可能なO(N^2)最大フローはです。N
  • たとえば、Ford-Fulkerson アルゴリズムを使用して最大フローを見つけますO(E*f)。ここEで、 はエッジの数、fは最大フローの値であるため、 になりますO(N^3)。
  • 最大フローが の場合N、スケジュールがあります。エッジにフロー 1 がある場合、スロットで(u_i,v_j)候補者に面接します。それ以外の場合は不可能です。ij

積分フロー定理により、最大フローはエッジに整数フロー (0 または 1) を持つため、有効なスケジュールが得られます。

于 2012-06-21T18:05:09.550 に答える
3

これが最大二部一致問題です。

グラフの密度にもよりますが、最速のソリューションはおそらくHopcroft-Karp アルゴリズムで、これは最大 O(N^(5/2)) 時間で実行されますが、おそらくはるかに高速です。

于 2012-06-21T18:14:28.677 に答える