問題タブ [hungarian-algorithm]

ここで私は私の問題の最小限の完全な検証可能な例を提供しています:

サイズ 3 X 17 の長方形行列が考慮されます: 行 = [10,6,9] が考慮されます。ここで、列はそれぞれ値に関連付けられたパターンです

現在、列の値と行の値の差は、マトリックス 3 X 17 のコストと見なされ、コストが負であることが判明した場合は、すべての列の値の合計に置き換えられます (大きな値を確保するためだけに具体的なことは何もありません)。ここで、最小コストの割り当てを行う必要があります。Sudo apt-get install python-munkresを使用してライブラリmunkresをインストール し、次のコードを実行しました。

次の出力が生成されます。

問題は、[2,5]、[1,5]、[3,4] が、最小コストに対応する最終的に割り当てられたパターンであることです。ここで、パターン [2,5]、[1,5] は相互に排他的ではありません。「5」は共通です。r1 が [2,5] 割り当てられると、割り当てられた要素のいずれかを含むパターンの残りの部分、つまりここでは 2,5 は割り当てに使用できなくなります。または、マトリックス内の対応するパターン関連コストを非常に高い値に更新する必要があります。次の行と見なされなくなったものは、このように続行する必要があります。

最終的には、割り当てが可能な場合、対応するパターンは本質的に相互に排他的である必要があります。

誰でもこれに取り組む方法を提案できますか?

私は現在、学生をコースにマッピングするプログラムを書いています。現在、私はSATソルバーを使用していますが、次のサブ問題を解決する多項式時間/貪欲でないアルゴリズムを実装しようとしています:

• 学生あり（50～150人）
• 「数学」、「生物学」、「芸術」などの科目 (10 ～ 20) があります。
• 科目ごとにコースがあります (少なくとも 1 つ)。たとえば、「数学 1」、「数学 2」、「生物学 1」、「芸術 1」、「芸術 2」、「芸術 3」などです。
• 学生はいくつかの (固定された) 科目 (10 ～ 12) を選択し、各科目について、既存のコースの 1 つに学生を割り当てる必要があります (可能な場合)。「数学1」「数学2」どちらの科目を選択しても問題ありません。
• コースには許可された最大数の学生（20-34）があります
• 各コースは固定ブロック（＝タイムスロット1～13）
• 学生は、同じブロックにあるコースに割り当てられない場合があります

今までやってきたことを紹介しています。

(1) 受講者制限の無視

ハンガリーのアルゴリズム/二部マッチングでこれを解決できました。各生徒は、次のようにモデル化することで個別に計算できます。

• 左のノードは、科目「数学」、「生物学」、「芸術」 (生徒の) を表します
• 右側のノードは、ブロック '1'、'2'、.... '13' を表します
• 「科目」から「ブロック」までのコースごとにエッジが挿入されます

このようにして、学生は同じブロックにあるコースに参加していなくても、コースのすべての科目に割り当てられます。ただし、コース制限は無視されます。

(2) 学生の選択科目無視

max-flow-algorithm でこれを解決できました。各学生について、以下がモデル化されます。

• レイヤー 1: 13 の流れでソースから各生徒へ
• レイヤー 2: 各生徒から個人ブロックまで、フロー 1
• レイヤー 3: 各学生ブロックからそのブロック内の各コースへのフロー 1
• レイヤ 4: 各コースから「max-student-limit」を使用してシンクまで

このようにして、学生は任意のコースを選択し、コース制限が満たされます。しかし、運が悪く、科目「生物学」と「芸術」を無視して「数学 1」「数学 2」「数学 3」に割り当てられるかもしれません。

(3)貪欲なハンガリー人

私が持っていた別のアイデアは、一度に 1 人の学生をハンガリーのアルゴリズムと一致させ、「より空のコース」が優先されるように重みを調整することでした。たとえば、次のモデルを作成できます。

• 左のノードは生徒の科目です
• 右のノードはブロック
• コースごとに、重み = 自由席の数で、コースのブロックにサブジェクトからエッジを挿入します

次に、Maximum-Weight-Matching を計算します。

提案/ヘルプをいただければ幸いです。

ありがとうございました！

しばらくの間、私を悩ませている問題があります。

「ワーカー」w_0、w_1 ... w_n、およびタスク t_0、t_1、... t_m、および期間 D_ij があり、w_i はその時間数で t_j を完了することができます。各ワーカーには、最大 m_0,m_1... m_n 勤務できる時間数もあります。

複数の作業者が、比例配分された工数で同じタスクに取り組むことができます。たとえば、D_11 = 2 かつ D_21 = 4 の場合、ワーカー 1 はタスク 1 でワーカー 2 の 2 倍効率的です。したがって、たとえば、1 時間の 1 時間と 2 時間の 2 時間でタスクを完了することができます。

すべてのタスクを完了できる最小時間数をどのように決定できますか。

貪欲な手法を使用して、各タスクに最適なワーカーを選択しようとしましたが、それはすべてのケースで機能しません。たとえば、ワーカー 1 がタスク 1 を 2 時間で、タスク 3 を 4 時間で完了できるとします。ワーカー 1 がタスク 1 に取り組むために選択されることは明らかですが、タスク 3 は他のワーカーにとって非常に時間がかかり、ワーカー 1 はその仕事に最適だったとしましょう。

問題を割り当て問題に減らすことを考えましたが、方法を見つけることができませんでした。

この問題はどのように解決できますか?

各行と列から 1 つだけの要素を選択する必要があるように、n*n 2D 行列の要素の最小合計を見つけますか? 例えば

4行から選択すると、行から も列からも1選択できず、行 2 列 2 から 6 つしか選択できません。1211

同様に、最小合計は4 + 6 = 10、62 行目から 2 列目です。

2 行目の 1 列目の6 + 12 = 18場所ではありません6

また4 + 12、両方が同じ行からのものであるため、許可されません

行と列から要素を選択すると、別の要素を選択できないブルートフォースを考えましたが、このアプローチはO(n!) .

ハンガリアン アルゴリズムを C で実装しました。ほとんどの場合、うまく機能します。ときどき、私のコードが一部の行列の解を見つけられないことがあります。ソリューションの確認 マトリックスがどのようにカバーされているかが重要であると考え始めています。次に例を示します。

これは、最初の 2 つのステップが実行されたときの行列です (行ごとに min を減算し、列ごとに min を減算します)。

私のコードを使用してカバーした場合（2意味の要素が2回交差しています）：

ここで同じ元のマトリックスを使用して解決策を探しましたが、マトリックスのカバーが異なっていました。最後の 2 列を選択する代わりに、最後の 2 行を選択しました。さらに 2 つのマトリックス削減により、それらは一致することになります。一方、私はしません。

どの回線の組み合わせが優れているかを判断する方法はありますか?