状況は以下です。
私は何十人もの生徒がいる家庭教師です。私の時間にはいくつかの制限があり (たとえば、金曜日の午後は教えられません)、学生も時間に多くの制限を受けています。それに基づいて、できるだけ多くのプライベートレッスンを行い、同時に時間を最適化できるようにアジェンダを作成しようとしています. 理想的には、私から学生までの距離も考慮に入れるでしょう (一部の学生は別の都市にいます)。クラスには可変期間もあります。理想的には、私は時間 (曜日ごと) を設定できるようにしたいと考えています。各生徒がレッスンを受けることができる時間 (曜日ごと) を教えて設定することができます。つまり、週に 2 回）。
アルゴリズムは既にあると思いますが、この問題の名前がわかりません。それは安定した結婚の場合ではないと思いますし、この場合もそうではないと思います:教師のタイム スケジュール アルゴリズム
もしアルゴリズムが存在しない場合は、それを詳しく説明するために研究できるアルゴリズムや資料を教えていただければ幸いです。
どうもありがとうございました。良い一日を！
適切な多項式時間解を適用するには、問題が複雑すぎるようです。たとえば、学生がどこにいるか、時間の断片化などを気にしない場合は、最大フロー アルゴリズムを使用して解決できます。ただし、これはおそらく、最も満足できるスケジュールにはなりません。現実世界の状況をモデル化したい場合、学生数が少なく (例: 10 人未満)、利用できる時間が少ない (例: 40 時間未満) と仮定すると、バックトラックを行う必要があります(つまり、ブルート フォース)。さまざまな割り当てを試して、あなたが持っている制約を最適化するために。実行時間は指数関数的であるため、最終的には分岐限定の最適化が必要になる場合があります。
どのようなアプローチを取るにしても、問題をより具体的な方法で単純化または指定する必要があります。たとえば、授業が常に 2 時、4 時、6 時、または 8 時に始まると決めた場合、問題の解決ははるかに簡単になります。また、ソリューションの質を示す式を定義する必要があります (例: 教育の合計時間から移動の合計時間を差し引いたもの)。このような問題のモデル化と解決策の作成は、通常、特にプログラミングやアルゴリズムの愛好家にとっては楽しいものです。