こまった専門家たち 非実践的アルゴリズム研究者 わかみず会 ( ) 前田英次郎

Transcription

1 こまった専門家たち 非実践的アルゴリズム研究者 わかみず会 ( ) 前田英次郎

2 近藤一夫先生の質問 ある種のことはよくできるが その他のことはあまり知らない こういう人を何というか 近藤一夫 東大応用物理学科数理工学コース教授 常識を超越した人 天才ですか とある学生が言った

3 先生のお答 天才は何でもできるかもしれんな そういうのは専門家と言うんじゃ 糖尿病と診断されたころ読んだ本にあった話 糖尿病患者は血糖値が高いことを発見した医者がいた 血糖値を下げれば治る と考えて 徹底した食事制限をした その結果 血糖値は下がった そして患者は

4 そして患者は痩せ細って死んだ 専門家は知らないことを無視する傾向がある 子供の骨 フロン 私は自分が何も知らないということを知っている ソクラテス

5 アルゴリズム研究者 実践的 解いた結果を仕事に使う ( 人に渡す ) 非実践的 論文を書いて発表する 研究課題 効率 ( 所要時間 所要メモリ 安定性 ) 明解なプログラム

6 計算効率 ( 計算量 ) の表現 計算時間の実測値 ハードウェアによる違い プログラムによる差 オーダーによる表示 (1970 年代初め ) 問題の大きさをnとして nの関数で表す 単純ソートはn 2 ヒープソートはnlogn 最悪計算量 平均計算量

7 P と NP P アルゴリズム (polynomial) 最悪計算量がnの多項式で抑えられる NP 問題 (nondeterministic polynomial) 変数値が制約条件を満たすかどうかを 多項式時間で判定できる P アルゴリズムはごく少数 ほとんどの問題は NP

8 NP 問題の解法 ( 分枝限定法 ) 整数線形計画問題の例 1 整数制約を無視したLPを解く ( 緩和問題 ) 2 整数条件に反した変数に制約を加える ( 分枝 ) Y=2.4 なら y 2 と y 3 を加えた 2 つの子問題を作る 3 子問題を解き 最も良い解を採用する 緩和問題の目的関数値より良い解はない ( 限定 ) 実行可能解 ( 最適解の候補 ) が見付かったら 可能性のない子問題は捨てる ( 限定 )

9 分枝限定法のオーダー 0_1 変数が n 個あれば 最大 2 n 個の子問題ができる 理論家の多くは n の指数関数的と考えているように見える ほとんどの子問題は作る前に捨てられる 末端の子問題では 緩和問題が簡単に解ける NP 問題の攻略法は問題ごとに工夫されるので 一般論は有効ではない

10 問題群 NP 完全 (complete) NP 完全な問題は NP アルゴリズムを持つ 整数線形計画問題 巡回セールスマン問題... 問題 A と B が NP 完全なら 大きさnのA 問題は 大きさmのB 問題に 大きさpのB 問題は 大きさqのA 問題に 変換できる ただし mはnの多項式 qはpの多項式で抑えられる 問題 A と B を同等と見る ( マジ???)

11 P=NP? 問題 NP 完全問題の一つに P アルゴリズムがあれば すべての問題に P アルゴリズムがある P アルゴリズムを持つ NP 完全問題は見つかっていないが 存在しないことも証明されていない P=NP? 問題には懸賞金が付いている

12 P=NP 問題? 解を必要とする者には P=NP? は無意味 P NP が証明された場合 予想通り 世の中に変化なし P=NP が証明された場合 NP 完全は n も n 10 も同等と見る理論である ここから有効なアルゴリズムが生まれるはずがない

13 こまった専門家 (1) ある研究会で 若い研究者が アルゴリズムの効率についてオーダー以外のことは言ってはいけない と言った 悪い先生に付いているのだろう オーダーは中間点 ゴールではない オーダーが同じでも効率には差がある オーダーは最悪計算量 実体ではないこともある

14 オーダーの嘘 線形計画法 (LP) の単体法のオーダーは? カーマーカーの内点法 (P アルゴリズム ) 手法の発展 => オーダー n 4 新手法オーダー n 3.5 を達成 速いんですか と訊いてみた 速くない ちゃんと n 3.5 かかるから???

15 オーダー n 4 の意味 どんなデータの問題でも n 4 以下で解けることが証明できた 実際に n 4 かかる問題があるかどうかは不明 普通の問題は n 4 もかからなかったのだろう 内点法は逐次近似法 LP は組合せ問題の側面もあるので ここまで追い詰めれば解はこれしかない という判定ができる

16 こまった専門家 (2) P 信仰 ある人曰く アルゴリズムは多項式オーダーでなければいけない 似非理論家に NP アルゴリズムは論外だとでも吹き込まれたのだろうか 問題以前に答えを決めてしまっている

17 NP 問題と P アルゴリズム NP 問題に P アルゴリズムで向かうとすれば 近似解で満足するしかない NP 問題は多種多様である 案外簡単に解けるものもあり ひどく難しいものもある 良い近似解法が知られているものもあり うまい方法が見付からないものもある 問題ごとに良い手段を選ぶ必要がある P でなければ駄目 などと決めつける必要はない

18 NP 問題と P アルゴリズム オーダーは問題の大きさの変化が計算の手間にどう影響するかを示すものである 特定のデータにどの程度の時間がかかるかを与えるものではない 解を得たい問題があるのなら その大きさに合わせて解法を選べばいい

19 こまった専門家 (3) NP 完全信仰? KDD 研究所からの依頼で衛星通信で発生する組合せ問題のプログラムを作製した 論文にすると言うので 解法の部分を書いた 査読者から この問題はNP 完全か? NP 完全なら分枝限定法の使用が正当化できる というコメントが来た 仰天!!!

20 NP 完全信仰 NP 完全の証明ができなければ 分枝限定法を使うな と言うのか P アルゴリズムを思いつかなければ あるいはそれがあっても役に立たなければ NP 問題だと思いそれなりの解法を考える 解が必要なのだから NP 完全であることの証明は簡単ではない NP 完全であることが分かっても解法を考える上で 何の役にも立たない

21 NP 完全信仰 問題を定式化し データは何でもいいとして解法を考える 分枝限定法の枠組みで こういう条件に合えばもっと制約をきつくできる といったものがスピードアップの要である データは何でもいい とは言っても 実際のデータには癖がある その癖をうまく利用したアルゴリズムになっているのが成功の秘密かもしれない 定式化だけで問題の枠組みが完全に指定できたとは限らない

22 NP 完全信仰 NP 完全は多種多様な問題の集まりである 解法の成功はそれぞれの問題の特性をうまく活かせるかどうかにかかっている NP 完全全体に通用する議論で片付くようなものではない NP 完全は論文の材料にはなるだろうが 解法に役立つものではない

23 こまった専門家 (4) 毒入りクイックソート Haskell の入門書に下のプログラムがあった qsort[] = [] qsort[x:xs] = qsort smaller ++ [x] ++ qsort larger where smaller = [a a<-xs, a<=x] larger = [b b<-xs, b> x] 一見きれいなプログラムだが 使いものになりません

24 Quicksort 一般的なデータに対するソート手法 高速ソート ( オーダー nlogn) クイックソート (qsort と略す ) ヒープソート マージソート 中速ソート シェルソート 低速ソート ( オーダー n 2 ) 挿入ソート 選択ソート バブルソート

25 Quicksort 高速ソート ヒープソート 遅い マージソート 余分なメモリーが必要 qsort 最速だが 最悪計算量はn 2 qsort は n 2 になるデータに当たると破綻するが その確率は α/n! 程度で無視できると考えられている

26 Quicksort qsort(a,n) push(0, n-1); while(stack が空でない ) pop(lb, ub); 分割 (a, lb, ub, i, j); // k<i => a[k]<=x ;; k>j => a[k]>=x if (lb < j) push(lb, j); if (I < ub) push(i, ub); ソート対象の区間を並べ替え 前方に小 後方に大とする 前方 後方をそれぞれソートすれば完成

27 Quicksort 分割 (a, lb, ub, i, j) aの要素の1つを選んで x とする i = lb; j = ub; // k<i => a[k]<=x ;; k>j => a[k]>=x while (i <= j) a[i] >= x となるまで i を増やす a[j] <= x となるまで j を減らす if (i <= j) swap(a[i], a[j]); i++; j--;

28 Quicksort 分割ではソート対象の要素の 1 つを x とし 前方には x 以下の要素 後方には x 以下の要素となるように並べ替える 前方と後方をそれぞれソートすれば完成である 前方と後方が同数になれば分割の回数が少なくて 効率が良い 一方が 1 個だけといった場合はほとんど分割になっていない

29 Quicksort 先頭の要素を x とする教科書があるが お勧めできない ソート済みのデータを食わせるとオーダー n 2 になってしまうからである ソートできていることが分かっているものをソートすることはないだろうが 比較的少数の要素の位置が違う あるいは大部分の要素の位置が少し違うといった問題はあるだろう

30 Quicksort ソートの対象を前方と後方に分けてそれぞれをソートすれば出来上がり 再帰関数にお誂え向きの問題である しかし 再帰関数を使ってはいけない Haskell プログラムでは n 2 のデータが来るとメモリー不足で落ちる C などの言語でも落ちる可能性がある

31 Qsort は速いか 所要時間 ( 秒 ) 1 万 10 万 100 万 300 万 500 万 1000 万 シェル ヒープ マージ クイック _H クイック _M

32 移動と比較の回数 移動比較移動比較移動比較移動比較 シェル _C ヒープ _C マージ _C クイック _H_C

33 Haskell プログラム qsort[] = [] qsort[x:xs] = qsort smaller ++ [x] ++ qsort larger where smaller = [a a<-xs, a<=x] larger = [b b<-xs, b> x] 一見きれいだが 全然使えません

34 リスト言語での Quicksort list qsort (list zs) { if (zs が空 list) return 空 list; x = zs の最初の要素 ; xs = zs から最初の要素を除いた list; xs を scan して smaller を作り qsort でソートする xs を scan して larger を作り qsort でソートする smaller と [x] と larger をつなぐ }

35 リスト言語での Quicksort 普通の Qsort では 未処理の区間をスタックに残しておく 前方と後方に分割した後小さい方を先に処理すれば 未処理区間が log 2 n 個を越えることはない Haskell qsort では larger を qsort する時には元の区間 zs と smaller を持っていなければならない n 段程度の再帰呼び出しがあれば 各段でその両方を持つ メモリーが苦しい

36 時計回りの怪? 大きめのカップにフリーズドライのインスタントコーヒーを入れ その上に冷えたミルクを入れる 表面に浮いたコーヒーを速く溶かそうとカップを揺する 時計回りになるように揺すっているつもりだが コーヒーは反時計回りに回る 何故だ? カップの壁に付いたコーヒーは時計回りに動いている 誰か教えてもらえませんか