分割問題 - 伊庭研究室

分割問題
東京大学大学院
工学系研究科
伊庭斉志
分割問題


与えられた n 個の整数 a1,...,an を二つの集合に
分け、各々の集合内の数の和がもう一方の集合内
の数の和と等しくなるようにできるかどうかを判定
する問題
NP完全問題
分割問題


問題: {2,10,3,8,5,7,9,5,3,2} の10個の数の完璧
な分割は見つけられるか？
答え: 存在する。{2,5,3,10,7}と{2,5,3,9,8}


どちらも和は27
分割方法は23通り存在する（対称をのぞく）
分割問題


これはまれな例ではない。
１から１０までの自然数１０個からなる組みについ
て、完璧な分割が可能な組みは99％以上ある。

では、自然数の数が大きくなるとどうなるか？

たとえば1000個の１から１０の自然数では？？？

とても時間がかかるので、なにか効率的なアルゴリズム
はないか？
欲張りアルゴリズム



山登り法の１つ
数を大きな順にならべる
大きき順から、その時点で和が小さいほうの
組みに割り当てていく
欲張りアルゴリズム

分割すべき集合： {19,13,9,17,6}

数を大きな順にならべる

分割すべき集合： {19,17,13,9,6}
欲張りアルゴリズム

分割すべき集合： {19,17,13,9,6}

集合１

集合2

食い違い
欲張りアルゴリズム

分割すべき集合： {17,13,9,6}

集合１

集合2

食い違い
19
19
欲張りアルゴリズム

分割すべき集合： {13,9,6}

集合１
19

集合2
17

食い違い
2
欲張りアルゴリズム

分割すべき集合： {9,6}

集合１
19

集合2
17, 13

食い違い
11
欲張りアルゴリズム

分割すべき集合： {6}

集合１
19, 9

集合2
17, 13

食い違い
2
欲張りアルゴリズム

どのくらい効率的か？





速さ
正確さ
ランダムに1万個の整数を発生させて分割可
能かを確かめてみる
成功率はどのくらいか？
もっと効率的なアルゴリズムはないか？
差分法

1982年ＵＣＢ





ナレンドラ・カーマーカー
リチャード・Ｍ・カープ
速さ
正確さ
各段階で元となる集合から数を２つ選んでは、
それらの差の絶対値で置き換える
差分法





各段階で元となる集合から数を２つ選んでは、
それらの差の絶対値で置き換える
選んだ２つの整数のどちらがどの組に行くかは決
めない
とりあえず別々の組に行くことのみ決める
この作業を残る数が１個になるまで続けると、残っ
た数がその分割による食い違いになる
その後で作業を逆にたどり分割を再構成する
差分法

分割すべき集合： {19,17,13,9,6}

差

集合１
集合2

食い違い

2
0
差分法

分割すべき集合： {13,9,6,2}

差

集合１
集合2

食い違い

4
0
差分法

分割すべき集合： {6,4,2}

差

集合１
集合2

食い違い

2
0
差分法

分割すべき集合： {2,2}

差

集合１
集合2

食い違い

0
0
差分法

分割すべき集合： {0}

差

集合１
集合2

食い違い

0
差分法 (逆にたどる）

分割すべき集合： {0}

差

集合１
集合2
0

食い違い
0

差分法 (逆にたどる）

分割すべき集合： {2,2}

差
0

集合１
集合2
2
2

食い違い
0

差分法 (逆にたどる）

分割すべき集合： {6,4,2}

差
2

集合１
集合2
4,2
6

食い違い
0

差分法 (逆にたどる）

分割すべき集合： {13,9,6,2}

差
4

集合１
集合2
13,2
9,6

食い違い
0

差分法 (逆にたどる）

分割すべき集合： {19,17,13,9,6}

差
2

集合１
集合2
13,19
17,9,6

食い違い
0

差分法

差分法は本当にいいか？
１から１０００までの整数

{771,121,281,854,885,734,468,1003,83,62}





この１０個の数は完璧に分割できる
欲張りアルゴリズムではうまくいかない（差は32）
差分法でも駄目（差は26）
どうやればうまくいくか？
Flyodの問題レポート課題

1から50までの整数がある．
これをAとBの2つの集合にわけ，それぞれに
おいて平方根をとって和をとる．
この和がもっとも近くなるようにAとBを決めよ．

どうやればうまくいくか？


Flyodの問題レポート課題

例１：Aを奇数，Bを偶数の集合


差の絶対値=&3.173106321065504
例2：Aを3の倍数，Bをその他の集合

差の絶対値=&84.989984837088443
Flyodの問題レポート課題

全探索の計算量

知られている最良解の１つ


差の絶対値=10^-12
整数を含めて15桁が一致
Knuthのヒューリスティックス
レポート課題の１つ

欲張りはどうなのか？

差分法は本当にいいのか？

他にいい方法がないのだろうか？


ヒューリスティック、ＧＡ
どのようにして確かめたらいいだろうか？



ランダムに問題を生成していろいろな方法で試す
意地悪な問題をわざと作ってみる
ソートの分は損していないか？

Download Report