LiosK-free Blog

• 2008-04-21
• カテゴリ: 雑記
• タグ: アルゴリズム 最適化

前回のエントリで、僕では解けない問題を書いてみたんだが、書き方が曖昧であまり伝っていないみたいなので、少し正確に書いてみることにした。ついでにサンプルデータも用意したから、サンプルデータでイメージしてもらえると助かる。

まず、やりたいことは前回書いたとおり、参加希望を出してくれた参加者を、効率よく実験枠に割り振るという仕事。

実験枠の数はだいたい30個前後になることが多くて、参加希望者はそのそれぞれに対して、参加可能 or 参加不可能のどちらかで回答してくれている。参加者の数は300人前後。

実験枠には最少催行人数と最大収容人数が決まっていて、割り振られた参加者の数がこの最小値と最大値を満たしていなければ、実験を実行することはできない。この最小値と最大値は、{最小: 3, 最大: 5}か、もしくは{最小: 8, 最大: 10}程度になることが多いと思う。

求める解の条件は以下の二つ。

1. 実行可能な実験の数が最大の組み合わせ
2. その中でも、実行可能な実験に参加できる参加者の数が最大のもの

最優先は実行できる実験数の最大化である。おそらく、実験数が最大値をとる組み合わせは無数にあると思われるので、その中でも実行可能な実験に参加する人数が最大の組み合わせを求めたい。

必ずしも全ての実験枠が実行可能になる必要はなく、全ての参加希望者を実験枠に割り振る必要もない。ただし、実行可能な実験数が最大で、実行可能な実験に割り振られた参加者の数が最大になるような組み合わせが欲しい。

組み合わせ数が大きくなりそうだから、決定的アルゴリズムで見つかるのかどうかは疑問。確率的なアルゴリズムでも別にいいかも。

サンプルデータ

簡単なサンプルデータを用意してみた。10個の実験枠は↓のような配列で表現できる。minが最小催行人数でmaxが最大収容人数であることは見て分かるとおり。

[
    {"min": 3, "max": 5},
    {"min": 3, "max": 5},
    {"min": 3, "max": 5},
    {"min": 3, "max": 5},
    {"min": 3, "max": 5},
    {"min": 3, "max": 5},
    {"min": 3, "max": 5},
    {"min": 3, "max": 5},
    {"min": 3, "max": 5},
    {"min": 3, "max": 5}
]

6040人の参加希望者のデータは↓のような感じ。各希望者は長さが実験枠数と同じの配列で表現されていて、その配列でtrueとなっているところは参加可能という意味。例えば、

[false, true, false, true, false, true, true, true, false, true]

という参加希望者は、実験1, 3, 5, 6, 7, 9に参加可能という意味。

[
    [true,  true,  true,  true,  false, true,  true,  false, true,  true ],
    [true,  false, true,  true,  false, true,  false, true,  true,  true ],
    [false, true,  true,  true,  true,  true,  false, true,  true,  true ],
    [true,  false, true,  true,  false, true,  false, false, true,  false],
    [true,  true,  false, false, false, true,  false, false, true,  true ],
    [true,  false, true,  false, false, true,  false, false, true,  false],
    [true,  false, false, true,  false, false, false, false, false, true ],
    [false, false, true,  true,  false, false, true,  true,  true,  false],
    [false, true,  false, false, true,  true,  true,  false, true,  true ],
    [true,  false, true,  true,  true,  true,  true,  true,  false, true ],
    [false, true,  false, false, true,  false, true,  false, true,  true ],
    [true,  true,  true,  false, true,  false, true,  false, true,  true ],
    [false, true,  true,  true,  true,  false, true,  true,  true,  true ],
    [false, false, true,  false, false, false, true,  true,  true,  true ],
    [true,  true,  true,  true,  false, true,  false, false, true,  false],
    [false, false, true,  false, false, true,  true,  false, false, true ],
    [true,  true,  false, true,  false, true,  true,  true,  true,  true ],
    [true,  false, false, false, true,  false, false, false, false, true ],
    [false, true,  true,  true,  false, false, false, false, false, false],
    [false, true,  true,  false, false, false, false, true,  true,  false],
    [false, true,  false, false, false, false, false, false, true,  false],
    [true,  false, true,  true,  true,  false, true,  true,  false, true ],
    [false, false, false, false, true,  true,  false, true,  true,  true ],
    [false, true,  true,  true,  false, false, true,  true,  true,  true ],
    [true,  false, false, false, true,  false, true,  true,  true,  false],
    [true,  true,  true,  true,  true,  true,  true,  false, false, false],
    [true,  false, true,  false, true,  false, true,  false, true,  true ],
    [false, false, true,  false, false, false, false, false, false, true ],
    [true,  false, true,  true,  false, true,  true,  false, false, true ],
    [true,  true,  true,  true,  true,  true,  false, true,  false, true ],
    [false, true,  true,  false, true,  false, false, false, false, true ],
    [true,  true,  true,  true,  false, false, true,  true,  true,  true ],
    [false, true,  true,  false, false, true,  false, false, true,  false],
    [true,  false, false, true,  true,  false, true,  false, true,  false],
    [true,  false, false, true,  true,  true,  true,  false, true,  true ],
    [true,  true,  false, true,  true,  false, false, false, true,  true ],
    [true,  false, true,  false, true,  true,  true,  false, true,  true ],
    [true,  true,  false, false, true,  true,  true,  true,  true,  false],
    [true,  true,  false, false, true,  false, true,  true,  true,  false],
    [false, true,  true,  false, false, false, false, true,  false, true ]
]

このサンプルデータを最適化するとどういう組み合わせになるんだろう？

サンプルデータ生成コード

参加希望者のデータは↓のPHPコードを走らせて作ったものです。

<?php
$data = array_fill(0, 40, array());
foreach (range(0, 39) as $i)
    foreach (range(0, 9) as $j)
        $data[$i][$j] = (bool)mt_rand(0, 1);

$json = json_encode($data);
//$jsonを整形して出力

ハチロク世代の人たちががんばってくれた＞＜

• suztomo
• Misho

サンプルデータの変形

サンプルの参加希望者配列を変形して、参加可能枠の番号を保持する配列に変えてみた。

[
    [0, 1, 2, 3, 5, 6, 8, 9],
    [0, 2, 3, 5, 7, 8, 9],
    [1, 2, 3, 4, 5, 7, 8, 9],
    [0, 2, 3, 5, 8],
    [0, 1, 5, 8, 9],
    [0, 2, 5, 8],
    [0, 3, 9],
    [2, 3, 6, 7, 8],
    [1, 4, 5, 6, 8, 9],
    [0, 2, 3, 4, 5, 6, 7, 9],
    [1, 4, 6, 8, 9],
    [0, 1, 2, 4, 6, 8, 9],
    [1, 2, 3, 4, 6, 7, 8, 9],
    [2, 6, 7, 8, 9],
    [0, 1, 2, 3, 5, 8],
    [2, 5, 6, 9],
    [0, 1, 3, 5, 6, 7, 8, 9],
    [0, 4, 9],
    [1, 2, 3],
    [1, 2, 7, 8],
    [1, 8],
    [0, 2, 3, 4, 6, 7, 9],
    [4, 5, 7, 8, 9],
    [1, 2, 3, 6, 7, 8, 9],
    [0, 4, 6, 7, 8],
    [0, 1, 2, 3, 4, 5, 6],
    [0, 2, 4, 6, 8, 9],
    [2, 9],
    [0, 2, 3, 5, 6, 9],
    [0, 1, 2, 3, 4, 5, 7, 9],
    [1, 2, 4, 9],
    [0, 1, 2, 3, 6, 7, 8, 9],
    [1, 2, 5, 8],
    [0, 3, 4, 6, 8],
    [0, 3, 4, 5, 6, 8, 9],
    [0, 1, 3, 4, 8, 9],
    [0, 2, 4, 5, 6, 8, 9],
    [0, 1, 4, 5, 6, 7, 8],
    [0, 1, 4, 6, 7, 8],
    [1, 2, 7, 9]
]

• パーマリンク
• コメント (0)
• トラックバック (1)
• 
• 

http://liosk.blog103.fc2.com/tb.php/103-b81a42be

前回と前々回のエントリーの問題を総当りで

前々回と前回のエントリで書いた問題を、Perlで総当りで解こうとしてみた。使ったコードは最後に添付。 実行開始から7時間半経過したけど未だ...

• 2008-04-22
• 発信元: 文系大学的IT系の悲哀