MISSION #05
  • 最適化問題
  • 本格派

席替え大作戦

このミッションのチュートリアルは、まだ公開していません。
「考え方」を参考に自分でプロジェクトを作ってやってみましょう♪

小学生のたかし君

たかし君のクラスでは、2か月に1回くらい席替えをします。
くじ引きで決めたり、班のグループを先に決めたりといろいろな方法で決めています。 どんな方法で決めても、喜んだり、悲しんだり大騒ぎです。

そこで

席替え用のプログラムを作ってみることにしました。

ミッション

必須条件を満たし、各自の希望をできるだけ叶える席配置を求めよ。

必須条件

  1. 視力が悪い人は前から2列目まで。
  2. 背が高い人のすぐ後ろが背の低い人にならないようにする。
  3. 隣り合わせNGの組み合わせが数組ある。その人たちが隣り合わせにならないようにする。
    (通路を挟んでの隣はOK)

机配置と希望エリア

机配置は以下の通りです。
各自、以下のいずれかのエリアを希望しています。
・最前列
・最後列
・窓際2列
・中央2列
・廊下側2列

メンバー表

ID背の高さ視力隣NG希望エリア
01低い22最前列
02低い-最前列
03低い-最後列
04低い-最後列
05低い10窓際2列
06低い-窓際2列
07低い-窓際2列
08低い-廊下側2列
09低い-中央2列
10低い05中央2列
11ふつう-最前列
12ふつう-最前列
13ふつう-最後列
14ふつう-最後列
15ふつう20窓際2列
16ふつう-窓際2列
17ふつう-廊下側2列
18ふつう-廊下側2列
19ふつう-中央2列
20ふつう15中央2列
21高い-最前列
22高い01最前列
23高い-最前列
24高い-最後列
25高い-最後列
26高い-窓際2列
27高い-廊下側2列
28高い-廊下側2列
29高い-中央2列
30高い-中央2列


考え方

30人の席順の組み合わせの数は30!(1から30まですべて掛け合わせた値)。10の32乗を超えます。
すべての席順を比較するのは現実的ではありません。

そこで、このミッションでは、局所探索法というアプローチを使ってみることにします。
具体的には、以下のアルゴリズムで最適解を見つけていきます。

  1. 番号順に並べる。
  2. 必須条件違反は-10点、要望を叶えたら+1点として点数を計算。
  3. ランダムに3人選んで席を入れ替えて、点数を計算。
  4. 入れ替える前と比べて、悪化していたり、点数が変わらなければ入れ替えない。
  5. 3,4を20,000回繰り返す。

ヒント

キーとなるアルゴリズムの実装例です。
ヒント1:3つの重複しないランダムな数字を作る
ヒント2:3つの要素の順番を入れ替える

自分でプログラムを作成するのは、ここから。
[+]ボタンを押すと新たに作成できます。