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

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

前々回と前回のエントリで書いた問題を、Perlで総当りで解こうとしてみた。使ったコードは最後に添付。

実行開始から7時間半経過したけど未だに終わる気配がない。馬鹿正直に40人の参加希望者と10個の実験枠を組み合わせたら組み合わせは10^40通り。今回のコードでは、参加可能枠の配列を使って解空間を狭めたけれど、それでもやはり9 * 8 * 9 * 6 * 6 * 5 * 4 * 6 * 7 * 9 * 6 * 8 * 9 * 6 * 7 * 5 * 9 * 4 * 4 * 5 * 3 * 8 * 6 * 8 * 6 * 8 * 7 * 3 * 7 * 9 * 5 * 9 * 5 * 6 * 8 * 7 * 8 * 8 * 7 * 5 = 1.4271125147448316e+32通りの解がある。もっと解空間を狭めるアルゴリズムを考えるか、確率的なアルゴリズムを考えるしかないようだ。

ちなみに、7時間半走らせたところ、最適解は最大実験枠が4個で最大参加者数が12人になっている。明らかにまだまだ。

総当りコード

use strict;

#各参加者の参加可能枠の配列に、不参加を意味する-1を追加
my @list = ([-1,0,1,2,3,5,6,8,9],[-1,0,2,3,5,7,8,9],[-1,1,2,3,4,5,7,8,9],[-1,0,2,3,5,8],[-1,0,1,5,8,9],[-1,0,2,5,8],[-1,0,3,9],[-1,2,3,6,7,8],[-1,1,4,5,6,8,9],[-1,0,2,3,4,5,6,7,9],[-1,1,4,6,8,9],[-1,0,1,2,4,6,8,9],[-1,1,2,3,4,6,7,8,9],[-1,2,6,7,8,9],[-1,0,1,2,3,5,8],[-1,2,5,6,9],[-1,0,1,3,5,6,7,8,9],[-1,0,4,9],[-1,1,2,3],[-1,1,2,7,8],[-1,1,8],[-1,0,2,3,4,6,7,9],[-1,4,5,7,8,9],[-1,1,2,3,6,7,8,9],[-1,0,4,6,7,8],[-1,0,1,2,3,4,5,6],[-1,0,2,4,6,8,9],[-1,2,9],[-1,0,2,3,5,6,9],[-1,0,1,2,3,4,5,7,9],[-1,1,2,4,9],[-1,0,1,2,3,6,7,8,9],[-1,1,2,5,8],[-1,0,3,4,6,8],[-1,0,3,4,5,6,8,9],[-1,0,1,3,4,8,9],[-1,0,2,4,5,6,8,9],[-1,0,1,4,5,6,7,8],[-1,0,1,4,6,7,8],[-1,1,2,7,9]);

#各実験枠に割り当てられた人数の数
my @exp = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0);

#実行可能な実験数の最大値と実行可能な実験に参加できる人数の最大値
my ($maxExp, $maxSum) = (0, 0);

#$maxExp, $maxSumの最大値を実現する割り当て
my @set = ();

my $start = time;

for my $x0 (@{$list[0]}) { $exp[$x0]++;
for my $x1 (@{$list[1]}) { $exp[$x1]++;
for my $x2 (@{$list[2]}) { $exp[$x2]++;
for my $x3 (@{$list[3]}) { $exp[$x3]++;
for my $x4 (@{$list[4]}) { $exp[$x4]++;
for my $x5 (@{$list[5]}) { $exp[$x5]++;
for my $x6 (@{$list[6]}) { $exp[$x6]++;
for my $x7 (@{$list[7]}) { $exp[$x7]++;
for my $x8 (@{$list[8]}) { $exp[$x8]++;
for my $x9 (@{$list[9]}) { $exp[$x9]++;
for my $x10 (@{$list[10]}) { $exp[$x10]++;
for my $x11 (@{$list[11]}) { $exp[$x11]++;
for my $x12 (@{$list[12]}) { $exp[$x12]++;
for my $x13 (@{$list[13]}) { $exp[$x13]++;
for my $x14 (@{$list[14]}) { $exp[$x14]++;
for my $x15 (@{$list[15]}) { $exp[$x15]++;
for my $x16 (@{$list[16]}) { $exp[$x16]++;
for my $x17 (@{$list[17]}) { $exp[$x17]++;
for my $x18 (@{$list[18]}) { $exp[$x18]++;
for my $x19 (@{$list[19]}) { $exp[$x19]++;
for my $x20 (@{$list[20]}) { $exp[$x20]++;
for my $x21 (@{$list[21]}) { $exp[$x21]++;
for my $x22 (@{$list[22]}) { $exp[$x22]++;
for my $x23 (@{$list[23]}) { $exp[$x23]++;
for my $x24 (@{$list[24]}) { $exp[$x24]++;
for my $x25 (@{$list[25]}) { $exp[$x25]++;
for my $x26 (@{$list[26]}) { $exp[$x26]++;
for my $x27 (@{$list[27]}) { $exp[$x27]++;
for my $x28 (@{$list[28]}) { $exp[$x28]++;
for my $x29 (@{$list[29]}) { $exp[$x29]++;
for my $x30 (@{$list[30]}) { $exp[$x30]++;
for my $x31 (@{$list[31]}) { $exp[$x31]++;
for my $x32 (@{$list[32]}) { $exp[$x32]++;
for my $x33 (@{$list[33]}) { $exp[$x33]++;
for my $x34 (@{$list[34]}) { $exp[$x34]++;
for my $x35 (@{$list[35]}) { $exp[$x35]++;
for my $x36 (@{$list[36]}) { $exp[$x36]++;
for my $x37 (@{$list[37]}) { $exp[$x37]++;
for my $x38 (@{$list[38]}) { $exp[$x38]++;
for my $x39 (@{$list[39]}) { $exp[$x39]++;
    #実行可能な実験数とその参加者数を数える
    my ($exe, $sum) = (0, 0);
    for (my $i = 0; $i < 10; $i++) {
        if (2 < $exp[$i] && $exp[$i] < 6) {
            $exe++;
            $sum += $exp[$i];
        }
    }

    #最大値と比較
    if ($maxExp < $exe && $maxSum < $sum) {
        $maxExp = $exe;
        $maxSum = $sum;
        @set = ($x0, $x1, $x2, $x3, $x4, $x5, $x6, $x7, $x8, $x9, $x10, $x11, $x12, $x13, $x14, $x15, $x16, $x17, $x18, $x19, $x20, $x21, $x22, $x23, $x24, $x25, $x26, $x27, $x28, $x29, $x30, $x31, $x32, $x33, $x34, $x35, $x36, $x37, $x38, $x39);
        print STDERR "$maxExp, $maxSum, \n", join(', ', @set), "\n";
    }
$exp[$x39]--; }
$exp[$x38]--; }
$exp[$x37]--; }
$exp[$x36]--; }
$exp[$x35]--; }
$exp[$x34]--; }
$exp[$x33]--; }
$exp[$x32]--; }
$exp[$x31]--; }
$exp[$x30]--; }
$exp[$x29]--; }
$exp[$x28]--; }
$exp[$x27]--; }
$exp[$x26]--; }
$exp[$x25]--; }
$exp[$x24]--; }
$exp[$x23]--; }
$exp[$x22]--; }
$exp[$x21]--; }
$exp[$x20]--; }
$exp[$x19]--; }
$exp[$x18]--; }
$exp[$x17]--; }
$exp[$x16]--; }
$exp[$x15]--; }
$exp[$x14]--; }
$exp[$x13]--; }
$exp[$x12]--; }
$exp[$x11]--; }
$exp[$x10]--; }
$exp[$x9]--; }
$exp[$x8]--; }
$exp[$x7]--; }
$exp[$x6]--; }
$exp[$x5]--; }
$exp[$x4]--; }
$exp[$x3]--; }
$exp[$x2]--; }
$exp[$x1]--; }
$exp[$x0]--; }

print "$maxExp, $maxSum, \n", join(', ', @set), "\n";

my $t = time - $start;
printf '%dsec. = %dmin. = %dhour', $t, $t / 60, $t / 3600;
スポンサーサイト



関連記事

トラックバック URL

http://liosk.blog103.fc2.com/tb.php/104-eba8e8f4

トラックバック

コメント

コメントの投稿

お名前
コメント
編集キー