PHPでの3次元バイパートマッチングアルゴリズムの実装方法

Question

3次元バイパートマッチングアルゴリズムを実装する必要があります。私はthis codeを持っています。これは、2次元の二者間マッチングアルゴリズムです。私はそれをPHPに変換することができ、それは正常に動作します。しかし、私のプログラムでは、の特定のタイムスロットの部屋にコースをマッチさせる必要があることに気付きました。 2次元二者間マッチングアルゴリズムを使用すると、すでに割り当てられた部屋は他のタイムスロットのコースには使用できません。タイムスロットが異なると同じ部屋を別のコースに再び使うことができるようにしたい。 graph [u] [v] [w]（ここで、uはもちろん指数、vは部屋のインデックス、wはタイムスロットのインデックス）の3つの次元のグラフを入力として使用するには、このコードを変更できますか？

Answer 1

このようにして、バイパートマッチングは機能しません。 「Bi」は2を意味する。ただし、グラフを二部構成に簡単に変換できます。左側のコースと右側のルームを考えてみるのではなく、このように考えてください。コースはまだ左側に残っていますが、右側にはルームとタイムスロットのノードが組み合わされています。このように - あなたは現実世界の問題に取り組んでいる場合は

Course CSE 101------Room 301 Time 10:00 - 11:00 
       \ 
       \ 
       \    
       \ 
        \ 
Course CSE 145------Room 301 Time 11:00 - 12:00 
       \ 
       \ 
       \    
       \ 
        \-Room 301 Time 12:00 - 13:00 

、同じコースの2クラスが上であってはならない、週に3コースの教室を割り当てるなどの他の制約があるでしょうそのような場合、グラフの二者モデルから一般的なフローネットワークに移動しなければならないでしょう。