テキスト第3話 3.2節「現実的計算不可能性」の補足

 

 「コンピュータサイエンス入門」のテキストの補足を述べる.

 

(1)NP問題の別の説明

 yesnoのいずれかを求める問題のことを決定問題という.

  NP問題とは,非決定性(nondeterministic)アルゴリズムを用いることにより,問題のサイズの多項式時間(polynomial time)で解ける決定問題の集合である.ここでいう非決定性アルゴリズムとは,途中のステップで取りうる道がいくつかに枝分かれしていても,神様がすべての枝分かれを並列に(同時に)実行して先に進む,というものである.全体としてみると,計算の手順が何本にも(何百,何万本にも)枝分かれしているのである.

 

              (並列に実行)     (並列に実行)

                        no

            枝分かれ   …    no

    枝分かれ           …    no

                   …    no    けっきょく

            枝分かれ   …    yes    yesだった

                        no

       多項式時間で解ける

 

 これまで扱ったふつうのアルゴリズムは決定性アルゴリズムと呼ばれる.これは枝分かれ(たとえばif文)があったらそのうちの一つだけを選ぶものである.

 神ならぬ人間や計算機としては,非決定性アルゴリズムをふつうの決定性アルゴリズムで真似る(すべての枝分かれを順々ににたどる)ことにより解くことになる.このような「シラミつぶし」法でやると,指数関数的な時間がかかる.

 

 注意 NP問題の中にはやさしい問題もある.たとえば2数の公約数を求める問題などは多項式時間で解ける.これらは,上の枝分かれがほとんどない問題と考えられる.

 

 

 

 

 

 

 

 

 NP問題(P問題も含む)

   

             多項式時間で解けないと思われる問題       

             @ 実用的な時間で解くのが難しい問題

            (例:NP完全問題(実用的な時間で厳密解

             を求めるのが難しい),巡回セールスマン)

 

  P問題

 

             多項式時間で解ける問題

             @ 実用的な時間で解ける問題

            (例:選択ソート,公約数,一筆書き)

 

 

 

(2)NP完全問題の性質のまとめ

 NP完全問題の定義は難しいが,あらまし「NP問題の中で最も難しい問題」といってよい.

 NP完全問題については次が言える.

0.NP完全問題は,決定問題という形をしている.(前述のように,決定問題とは,yesnoのいずれかを求める問題である)

1.NP完全問題は,(決定性アルゴリズムで)多項式時間で計算できない(指数関数的に増加する時間がかかってしまう)と予想されている.

2.NP完全問題が多項式時間で計算できるか否かは,いずれも証明されていない.(2,3をPNP予想とかP=NP問題と呼び,未解決の大問題である)

3.NP完全問題の集合の中にひとつでも多項式時間で計算できるアルゴリズムが見つかったとすると,その集合に含まれるすべての問題が多項式時間で解ける.

 

[参考書]Garey, M. R. and Johnson, D. S.: Computers and Intractability, A Guide to the

 Theory of NP-Completeness, Freeman, 1971, 1991.

 コルメン:アルゴリズムイントロダクション,第3巻,近代科学社

 渡辺治:計算可能性・計算の複雑さ入門,近代科学社

 石畑清:アルゴリズムとデータ構造,岩波書店

 戸田誠之助:PNP予想,数学セミナー, Vol. 37, No. 9, 19989月号.

 

(3)NP完全問題の例

 NP完全問題には次のようなものがある.

 

 ハミルトン閉路の問題 (Hamilton cycle problem):与えられた地図上のすべての都市をちょうど1回だけ巡回する道(起点に戻ってくる)があるかどうかを決定する.

 

 

 

 

 

 

 

 

 


    図 ハミルトン閉路の問題 (ゴールドシュレーガー,リスターより)

 

 

 

 

 

 

 

 

 


       図 ハミルトン閉路の問題の解

 

 箱詰め問題 (bin-packing problem):重さ(W以下)が異なってもよいn 個の荷物を,Wの重さを積むことのできるT 台のトラックにすべて載せられるかどうかを決定する.(本当は,箱詰め問題の「箱」はトラックである.)

 

 


    8トン     5トン    5トン     4トン      3トン  3トン

 

                n = 6

 

 

 

 

 


         トラックT = 2台   最大積載量W = 14トン

    図 簡単な箱詰め問題 (ゴールドシュレーガー,リスターより.

       積載量が14トンのトラックがあるかどうかは深入りしないこと)

 

 

 


                 5トン     4トン      3トン  3トン

 

 

 

 

 

 

 

 

 


                最大積載量W=14トン

 

図 「大きいほうから先に積む」アルゴリズムで最初のトラックに積み終わった

  とき,残りの荷物は2台目のトラックに積みきれない

 

 

        3トン    3トン

 


8トン

 
                               4トン

 


                        5トン  5トン

 

 

 

           図 上の箱詰め問題の解

 

 

 上の箱詰め問題を例として,「NP完全問題は多項式時間で解けそうもない」ことをインフォーマルに説明する.   

 これを解こうとすると,次のようにすることになろう.

1.      8トンの荷物をトラック1に積むかトラック2に積むか      2通り

2.      5トンの荷物(その1)をトラック1に積むかトラック2に積むか 2通り

3.      5トンの荷物(その2)をトラック1に積むかトラック2に積むか 2通り

4.      4トンの荷物をトラック1に積むかトラック2に積むか      2通り

5.      3トンの荷物(その1)をトラック1に積むかトラック2に積むか 2通り

6.      3トンの荷物(その2)をトラック1に積むかトラック2に積むか 2通り

をすべて調べる.けっきょく26通り調べることになる.

 一般に,荷物がn個あると2n通り調べることになり,時間計算量はO(2n )となる.

 もちろん,もっと効率良い方法を考えることはできる.たとえば,8トンの荷物はトラック1に積むと決めてしまってもよい,とか,途中で積んだ荷物が14トンを超えたらその先は調べない,とか.

 さらに巧妙な方法を考えると,もしかしたら多項式時間で解けるかもしれない.そこで,多項式時間で解けるか否かを世界の研究者が調べているわけである.

 

[問]最大積載量W=14,トラック台数T=2,荷物の数n=8,それぞれの荷物の重さ=7.5, 5.4, 4.9, 3.3, 1.9, 1.8, 1.7, 1.5として,箱詰め問題を解いてみよ.

 

 類似の問題として,「布を裁断して服を作るとき,なるべく余りを出さないように切りたい」とか,「各種素子をVLSIチップ上に配置するとき,なるべく効率よく小さなチップに配置したい」場合などがある.

 

 巡回セールスマンの問題 (travelling salesperson problem)n個の都市の間の道路地図を与えられたセールスマンが,制限距離内で全部の都市を一度ずつ訪問して起点に戻れるかどうかを決定する.                             

 

 


          都市A ・    ・      B           

 

 

                 C   ・      ・  D

 

 この問題は,始点を固定しても同じであるから,Aから出発するとする.すると道順は,

A B C D A

A B D C A

A C B D A

A C D B A  (*)

A D B C A  (*)

A D C B A  (*)

(4-1)!通り= 6通りある.しかし良く見ると,半分 (*) は他の逆順になっているだけなので,結局,道順は(4-1)!/2 通り= 3通りである.

 一般に,n個の都市に対しては,(n-1)!/2通りの道順がある.

 1<c なるcについてO(cn ) < O(n!) であることが知られているので,巡回セールスマン問題の素朴解法は多項式時間では解けない.

 

[問]A-B=5km, A-C=4km, A-D=3km, B-C=4km, B-D=2km, C-D=3kmのとき,合計13km以内で全部の都市を一度ずつ訪問して起点に戻れるか.

 

[参考プログラム]巡回セールスマン問題を解くプログラムtravelling.c

 

 時間割の問題 (time-tabling problem):利用できる時間枠の数と,講義のリストと,それを受講する学生のリストが与えられる.問題は,学生が受講する講義がぶつからないように,講義の時間割を組むことである.

 

 命題論理式の充足可能性問題 (SAT, satisfiability problem):真偽値をとる変数からなる論理式を真にするような変数の値の割当て方があるか,という問題である.(この問題は,「3個以下の変数または変数の否定」の論理和をとったものの有限個の論理積,という形の論理式に限定してもNP完全である.これを3充足可能性問題(略して 3SAT)という.変数の数はn個である.)

[例]x1, x2, x3, x4F(偽)かT(真)をとる.「(x1 Ú not x2 Ú not x3) Ù (x1 Ú x2 Ú x4) Ù (x1 Ú x2 Ú not x4) Ù (not x2Ú not x3 Ú not x4)」はTになりうるか.

(解)たとえば,x1=F, x2=T, x3=F, x4=Fとすると,上の論理式はTになる.

場合の数は,x1, x2, x3, x4 それぞれについてFTの2通りずつあるので,全部で24 通りある.一般に,変数の数がn個あると,場合の数は2n 通りある.

 

 k 彩色可能性問題 (k-coloring)k3 とするとき,無向グラフにおいて,辺で結ばれている頂点どうしは同じ色に塗られないようにして,各頂点をk種類以下の色で塗り分けられるか,という問題である.

[例]3色で塗り分けられるか(平面グラフでなくてよい)

 

     赤       赤

 

                  

 

     青       黄

 

(参考)

 NP完全問題は決定問題yes/noを尋ねる問題)であった.

 NP 完全問題のうちのいくつかの問題については,対応する最適化問題yes/noでなく最適解を求めるよう変形した問題)を考えることができる.たとえば巡回セールスマンの最適化問題は,条件を満たす最短の経路を求める問題となる.

 一方,最適化問題について,正しい解を求めるのは時間がかかりすぎるので,近似解(求める答えに近い答え)を多項式計算量で求める近似アルゴリズムを用いることも多い.たとえば,トラック台数が最小,距離が最短,色数が最小ではないが,それに近い解を求めるのである.

 たとえば,箱詰め問題の最適化問題は,いろいろな重さ(W以下)のn個の荷物,最大積載量Wが決まったトラックが何台もあるとき,すべての荷物を載せるのに必要な最小台数のトラックの台数Tを求める.これについては,次のファーストフィット法と呼ばれる近似アルゴリズムが有用である.

 ファーストフィット(first fit)法:

1.   荷物を重い順(非増加順)に並べる.

2.   最初のものから順番にトラックに載せていく.

3.   トラックの積載量を越えたら,次のトラックを使う.

4.   全部載せられたら終り.

 このアルゴリズムは,最悪の場合の計算量がO(n2)であることが知られている.また,ファーストフィット法で求まるトラックの台数は,最適な台数と比べて,最悪でも22%余分に使えば済むことが知られている.