php - ジョブを割り当てるための再帰

Question

これは具体的な質問なので、まず背景を簡単に説明します。私は、その日の特定の「仕事」に従業員を割り当てるソフトウェアに取り組んでいます。彼らが仕事をするためには訓練を受けなければならないので、システムは各従業員が何を訓練されていて何を訓練されていないかを知っています。

今私がやっていることは次のようなものです：

foreach ($jobs as $job){
   foreach($employees as $emp){
       if (job doesn't have employee && employee isn't assigned to job && employee has been trained on job){
          assign them;
          break;
       }
   }
}

これはある程度機能しますが、問題があります。次の簡単な例を考えてみましょう。

「レジ」と「カスタマーサービス」の2つの仕事があります。

「ビル」と「ルーシー」の 2 人の従業員がいます。ビルは両方の仕事を知っていますが、ルーシーはチェックアウトしか知りません。

ループが実行されると、最初に Checkout を実行する人が検索されます。最初に Bill を見て、彼が作業できることを確認し、割り当てます。彼らは顧客サービスを探すために移動します. 彼はすでに割り当てられているため、請求書をスキップし、ルーシーをチェックしますが、彼女はそれを行うことができません! これにより、不要なトレーニングが発生します。

すべての従業員を実行して誰も見つからない場合は、次のように処理するように簡単にコーディングできます。

//We didn't find anyone, let's look for a potential swap
foreach($employees as $emp){
   if (emp has been trained on job && emp is already assigned something else){
      //Find someone else to work their assigned job, so they can work this one
      foreach($employees as $emp2){
         if ($emp != $emp2 && emp2 can work emp's job && emp2 isn't already assigned anything){
            swap the two;
         }
      }
   }
}

かなり単純です。しかし、それは 2 人の従業員を扱うスワップに対してのみ機能します。スワップが非常に複雑で、4 人の移動が必要だったらどうしますか? 理想的には、$maxDepth = 5 などの値を設定できる再帰的なソリューションを考え出したいと思います。

誰かがすぐに見つからない場合は、深さ 2 に進み、前述の 2 人の交換を探します。それでもできない場合は、深さ 3 に移動して 3 人のスワップなどを探します。