席替え大作戦

小学生のたかし君

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

そこで

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

ミッション

必須条件

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

机配置と希望エリア

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

メンバー表

考え方

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

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

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

ヒント

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

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

チュートリアル

完成形

完成形のプログラム例はこちら。
プログラム例：席替え大作戦

席替え大作戦チュートリアル

利用規約に同意して

はじめる

ブラウザはGoogle Chrome最新版推奨です。