席替えマシーン

概要

　席替えをするとき、親しい人が近くの席になると嬉しいですね。席替えマシーンを使えば、たくさんの人が嬉しくなります。

具体的にできること

　こんな形してる38人クラスで、それぞれの人が近くにいてほしい友達を選んだ時に、なるべく多くの人が望みを叶えられるように席替え結果を生成してくれます。 15分くらいかかりますが、3秒しかかけてないときとあんまり結果が変わっていません。悲しいです。

入力の仕方

[出席番号]_[近くにいてほしい人の出席番号],[近くにいてほしい人の出席番号],[近くにいてほしい人の出席番号]...

こんな感じのをたくさん入れられます。 最後に0を入力すると終わります。

出力の説明

何個のケースを回したか、希望のペアのうち最終的に席が近いペアの割合、席替え結果を出力します

[回した数]回調べました。
[割合]
[1番の席番号] [2番の席番号]...[38番の席番号]
[
ここに席替え結果
席に出席番号が書いてある感じ
空き席には-1が書いてあります
]

仕組み

　詳しくはコード読んでくれ。
　単純に言うと、ひたすらランダムなケースを試しています。
　まず席替え結果をScore関数で点数化します。各ペアについて、マンハッタン距離が1だったら10点、 それ以外だったら{3-マンハッタン距離}点加算します。
　その後は設定された時間いっぱいに、ランダムにケースを生成して点数が高ければ更新、という操作を繰り返します。 ケースは、現在一番点数が高い席順の一部をランダムに入れ替えることで生成します。

入出力例

下に表示しているものは探索時間10秒で実行したものです。 挙げている奴は探索時間15分くらいです。

入力1

3_6,21
31_10,14,28,34
7_4,10,24,28
10_7,13,27,31
33_15,16,30,36
32_17,29,35
20_17,23,35,37

出力1

4048633回調べました
100%
12 5 10 20 16 11 13 9 26 14 0 23 15 33 25 19 30 7 3 29 2 1 22 6 24 36 21 27 32 17 28 31 18 4 34 8 35 37 
10 23 6 3 27 -1 
21 17 9 26 30 13 
20 35 12 22 19 34 
18 7 4 11 16 36 
33 2 29 24 31 25 
1 5 32 14 28 37 
-1 0 15 8 -1 -1 

入力2

1_3,37,
2_20,
3_4,
4_26,
5_13,30,
6_4,9,23,24,
7_25,35,37,
8_6,29,32,
9_4,26,27,32,
10_
11_18,
12_29,
13_7,10,29,34,
14_
15_2,20,23,35,
16_8,9,13,25,
17_
18_25,
19_12,30,33,
20_1,3,8,28,
21_33,
22_17,27,28,
23_26,37,
24_3,6,23,36,
25_8,22,33,37,
26_3,18,27,
27_4,8,38,
28_9,14,30,
29_
30_
31_4,12,19,25,
32_
33_
34_38,
35_
36_19,
37_
38_

出力2

3029655回調べました
72%
9 1 7 20 26 13 4 15 21 5 34 19 11 23 2 22 36 35 18 8 37 31 0 6 16 27 28 24 12 25 17 14 32 30 3 33 10 29 
22 23 5 3 25 -1 
1 2 31 8 26 35 
14 19 7 15 37 10 
34 0 24 13 33 17 
6 36 30 27 21 16 
9 12 18 29 32 20 
-1 28 11 4 -1 -1