家庭教師ってそもそも何？？
use: Yahoo!知恵袋Web API
家庭教師費等
D. E. F. G. H. I. 1. 2. 3. 4 (４)家庭教師費等. 5. 6. 公立幼稚園. 7. 区分. 400万円. 400万円 ... (４)家庭教師費等. 5. 6. 公立高等学校(全日制) 7. 区分. 400万円. 400万円 ...
http://www.mext.go.jp/b_menu/toukei/001/006/07120312/001/020.xls
「家庭教師の予約の組み合わせ」を行うプログラムの開発を行うことになりました。
しかしこれが難問で、予約の件数が増えると、計算が終了しません。
NP困難という奴でしょうか？
先輩諸兄のお知恵をお貸しください。
「家庭教師の予約の組み合わせ」とは、以下のような「家庭教師派遣サービス」において、予約と家庭教師の組み合わせを求める作業のことです。
【前提】家庭教師が生徒に教えることを「授業」と呼ぶ。
家庭教師の移動時間は考慮しない。
【内容】・家庭教師は、それぞれ教えることができる教科（以下、専門教科）を1つ以上もつ。
・生徒は、教えてほしい教科と教えてほしい時間帯を指定する（以下、予約）。
家庭教師派遣サービスは、条件に合う家庭教師を派遣する。
この場合の「条件に合う家庭教師」とは、 「指定された時間帯に、その家庭教師には他の予約が入っておらず、 かつその家庭教師の専門教科に指定された教科が含まれる」 ことを意味する。
・生徒は、特定の家庭教師を指名できない。
・生徒は同じ日に何回でも、授業を受けることができる。
その際は、同じ家庭教師とは限らない。
また異なる家庭教師とも限らない。
・家庭教師は、同じ日に何回でも授業を行うことができる。
・1人の家庭教師が同じ時間に複数の授業を行うことはできない。
・1人の生徒が同じ時間に複数の授業を受けることはできない。
次々に入る予約の依頼に対して、瞬時に「その予約は可能か不可能か」を返す必要があります。
少ない件数であれば、最悪でも家庭教師と予約の組み合わせを総当たりすれば、「可能か不可能か」は分かります。
しかし、件数が増えるにつれて組み合わせの数は膨大なものになるため、解が得られません。
総当たり以外の効率のよい方法を用いる必要があると思うのですが、どのような方法が考えられるのでしょうか？
