この記事では、「学校の授業の時間割」をモチーフに要件定義(課題検討)の段階でどのような情報整理をするか解説します。
情報整理をすると課題の特徴が見えやすくなり、組合せ最適化であることが理解しやすくなります。
課題を最適化問題としてコンピュータに入力するために、問題を明確にしていきましょう。
学校で時間割を組んでいる先⽣たちは、専⽤のソフトウェアを使っている場合もありますが、多くは⼿を動かして⽭盾なく条件を考慮できるように検討しています。
今回はある程度複雑な条件でありながら、考えやすさを考慮した設定のため、架空の中⾼⼀貫校で教科担任制を前提として、組合せ最適化問題である「授業の時間割作成」を考えてみましょう。
「教科担任制」であるため、Aクラスの特定のコマに教科担任の先生を割り当てる必要があります。となるとその先生がそのコマで、他のクラスを担当せずに空いている状態でなければいけません。
そういった条件と制約を考慮すると、1週間に存在するすべてのコマそれぞれに、ある先生を割り当てるか($+1$)否か($-1$)の組合せ最適化問題と捉える事ができます。
続いて、この問題を解くために考慮すべき条件を考えてみましょう。
要件定義とは、現実の問題を言語化することです。最終的にコンピュータで時間割作成の処理を行いますが、ITの活⽤においては、コンピュータは⼈間ではないので曖昧な指⽰では動いてくれません。 やりたいことを正確に伝えるために、まずは現実の問題である時間割作成の前提情報について丁寧に言語化することから始めます。以下のように、与えられた情報を整理していきます。
教科は国語・英語・数学・理科・社会・体育・美術・音楽・生活の9つ。このすべてが専門教員によって実施される。国語・英語・数学は各8人の教師がいて、それ以外の教科は4人ずついる。
このように、問題を言語化することで、ルールが明確になります。ルールを言葉で明確にしておくと、教員の異動やちょっとした追加・変更があった時にも対応しやすくなります。
コンピュータに処理してほしいことを明確にする事ができました。
今回の問題を解くのに必要なビット数とアニーリングマシンは計算できる規模の上限があります。
アニーリングマシンは1つの要素に1つのスピンを充ててあるパターンのエネルギーが最も良いことを導き出す手法のため、$+1$か$-1$に割り当てる要素がいくつあるかを事前に知っておく必要があります。
ここでは、先生が40人いて、1週間のコマ数が30限あり、クラスが12あります。
この12クラスで同時に授業が行われるのが学校であるから、割り当てを行うためには$40×12×30=14,400$の要素(各クラスのコマへどの授業を割り当てるかのパターン)、つまりスピンが必要と想定する事ができます。
この記事はACWスキルロードマップの一部です。スキルロードマップを使ってACWを学んでみてください。
記事が役に立ちましたか?他の人に共有してみてください。
組合せ最適化を身近な組合せ最適化問題として分かりやすい2つの例を用いて解説します。また、IoT社会における組合せ最適化処理の高速解法の重要性について述べます。
COVID-19の流行に伴い、感染リスクを考慮した制約条件の下、研究員のシフト作成をアニーリングマシンで行うユースケースを紹介しています。
自然災害リスクに対応するため、保険会社が保有する膨大なデータを活用した再保険ポートフォリオ策定をアニーリングマシンで行うユースケースを紹介しています。
アニーリングマシンが得意とする問題の特徴である「二次」「離散」を中心に、知っておくべき数学的前提を易しく解説します。