プログラミングが難しい問題のあるスケジューリングプログラムを書いています。いくつかのイベントがあり、それぞれに複数の会議時間があります。各イベントの複数の会議時間の1つを使用して、各スケジュールに特定のイベントが1回だけ含まれるように、会議時間の配置を見つける必要があります。
明らかにブルートフォースを使用することはできますが、それが最善の解決策になることはめったにありません。これは比較的基本的なコンピュータサイエンスの問題だと思います。コンピュータサイエンスのクラスを受講できるようになったら、この問題について学びます。それまでの間、これについて読むことができるリンク、またはGoogleで検索できる名前をお勧めします。
これを行うにはいくつかの方法があります
1 つのアプローチは、制約プログラミングを行うことです。これは、feanor によって提案された動的計画法の特殊なケースです。境界付けと分岐を行うことができる専用のライブラリを使用すると便利です。(ライブラリを見つけるための「gecode」または「comet-online」の Google)
数学に傾倒している場合は、整数計画法を使用して問題を解決することもできます。ここでの基本的な考え方は、問題を一連の線形不等式に変換することです。(「整数計画スケジューリング」の Google で多くの実際の例を見つけ、「Abacus COIN-OR」の Google で便利なライブラリを見つけます)
私の推測では、制約プログラミングが最も簡単なアプローチですが、整数プログラミングは、ある時点で問題に実際の変数を含めたい場合に役立ちます。
問題の説明は完全には明確ではありませんが、イベントが重複していないスケジュールを見つけようとしているだけであれば、これは単純な2 部マッチングの問題です。
イベントと時間の 2 つのノード セットがあります。各イベントから、考えられる各会議時間にエッジを引きます。次に、拡張パスを使用して、マッチング (ノード間のエッジの可能な最大セット) を効率的に構築できます。これが機能するのは、2 部グラフを同等のフロー グラフにいつでも変換できるためです。
これを行うコードの例はBIMです。GOBLINやNetworkXなどの標準グラフ ライブラリにも、2 部構成のマッチングが実装されています。
これは、動的計画法の解決策、特に間隔スケジューリング問題に似たものの良い候補のように思えます。
ここには、具体的にはインターバル スケジューリングの問題に関するいくつかのビジュアルがあり、概念がより明確になる可能性があります。 これは、動的計画法全体に関する優れたチュートリアルです。