パソコン家庭教師とは？！
平成16年度学生生活調査結果(５表)
家庭教師. 事 務. 軽労働. 重労働.・ 危険作業. 特殊技能.・ その他. 計. 従事時期別. 割合. 長期休暇中のみ従事. 16.3. 10.4. 57.8. 6.7. 8.9. 100.0. 26,434 ...
http://www.jasso.go.jp/statistics/gakusei_chosa/documents/04_table5.pdf
記者説明会資料 平成 16 年 7 月 7 日 独立行政法人 国民生活センター
「浄水器」等に続き常に上位に位置している(表 1)。なかでも家庭教師や学習塾等の指導を ... その背景には、勧誘時に「家庭教師の質がよい」 「教材は教科書に合っている」等と販売 ... あるいは家庭教師の指導を受けてみて初めて不満をも ...
http://www.kokusen.go.jp/pdf/n-20040707_2.pdf
「家庭教師の予約の組み合わせ」を行うプログラムの開発を行うことになりました。
しかしこれが難問で、予約の件数が増えると、計算が終了しません。
NP困難という奴でしょうか？
先輩諸兄のお知恵をお貸しください。
「家庭教師の予約の組み合わせ」とは、以下のような「家庭教師派遣サービス」において、予約と家庭教師の組み合わせを求める作業のことです。
【前提】家庭教師が生徒に教えることを「授業」と呼ぶ。
家庭教師の移動時間は考慮しない。
【内容】・家庭教師は、それぞれ教えることができる教科（以下、専門教科）を1つ以上もつ。
・生徒は、教えてほしい教科と教えてほしい時間帯を指定する（以下、予約）。
家庭教師派遣サービスは、条件に合う家庭教師を派遣する。
この場合の「条件に合う家庭教師」とは、 「指定された時間帯に、その家庭教師には他の予約が入っておらず、 かつその家庭教師の専門教科に指定された教科が含まれる」 ことを意味する。
・生徒は、特定の家庭教師を指名できない。
・生徒は同じ日に何回でも、授業を受けることができる。
その際は、同じ家庭教師とは限らない。
また異なる家庭教師とも限らない。
・家庭教師は、同じ日に何回でも授業を行うことができる。
・1人の家庭教師が同じ時間に複数の授業を行うことはできない。
・1人の生徒が同じ時間に複数の授業を受けることはできない。
次々に入る予約の依頼に対して、瞬時に「その予約は可能か不可能か」を返す必要があります。
少ない件数であれば、最悪でも家庭教師と予約の組み合わせを総当たりすれば、「可能か不可能か」は分かります。
しかし、件数が増えるにつれて組み合わせの数は膨大なものになるため、解が得られません。
総当たり以外の効率のよい方法を用いる必要があると思うのですが、どのような方法が考えられるのでしょうか？
