生命情报学特论-京都大学.PPTVIP

* * * * * * * * * * * * 生命情報学特論（６） 固定パラメータアルゴリズムと部分k木 阿久津　達也 京都大学　化学研究所 バイオインフォマティクスセンター 固定パラメータ?アルゴリズム [Flum, Grohe: Parameterized Complexity Theory, Springer] 固定パラメータ?アルゴリズム NP困難問題への対処法 近似アルゴリズム 固定パラメータアルゴリズム 指数時間アルゴリズム（O(an)で底aを小さくする） 平均的に高速なアルゴリズム ヒューリスティックなアルゴリズム 固定パラメータアルゴリズム あるパラメータ k があり、O(f(k)poly(n)) 時間で動作 f(k) は指数時間、poly(n) は多項式時間 k に対しては指数時間（もしくは、超指数時間） n に対しては多項式時間 頂点被覆問題 入力： 無向グラフ G(V,E)、整数 k 出力： サイズ k 以下の V の部分集合 W で 、G のすべ　 　　ての辺の少なくとも一つの端点が W に属するもの 頂点被覆問題はNP困難 再帰アルゴリズム G-v: グラフ G から頂点 v、 および、v に接続するすべての辺を削除して得られるグラフ アイデア 各辺の端点のいずれかは頂点被覆に属する よって、再帰呼び出しでそれぞれの可能性を調べる 再帰アルゴリズムの実行例 計算量の解析 定理：　頂点被覆問題は O(2k n2) 時間で解ける 証明 アルゴリズムの正当性は明らか 再帰呼び出し１回にかかる手間は、グラフのサイズのオーダー（O(n2)時間） 再帰の深さは k 以下で、１回あたり2回の再帰呼び出しが行われるので、再帰呼び出しの回数は 2k+1 以下 よって、全体の時間計算量は O(2k n2) カーネル化（１） 定理 固定パラメータアルゴリズムが存在　?　カーネル化法が存在 固定パラメータアルゴリズム設計の別なアプローチ 解に必ず含まれる部分や含まれない部分を削除するなどして、多項式時間で入力データを小さなサイズ（パラメータにのみ依存するサイズ）のデータ（カーネル）に変換 カーネルに対して全解探索を実施 頂点被覆問題に対するカーネル化 次数 k+1 以上の頂点は必ず被覆に含まれる 　　　（そうでないと 、k+1 個以上の隣接頂点を被覆に含むことが必要） 次数 k+1 以上の頂点を削除した後で、k2 個より多くの辺が残ったら被覆不可能?（孤立頂点を削除すれば）残りの頂点は 2k2 個以下 カーネル化（２） G’に孤立点が ある場合は、 それらも削除 |V’|≦2k2 (これと再帰型アルゴリズムの組み合わせも可） 計算量の解析 G’の構成はグラフのサイズのオーダー（O(n2)時間） 全解探索は O(2^{2k2} k2) 時間 ? O(2^{2k2 }k2+n2)時間 最近接文字列問題に対する固定パラメータ?アルゴリズム [Gramm et al.: Algorithmica, 2003] 最近接文字列問題 (Closest String) 入力： 同じ長さの文字列 s1,…,sk （|si|=L）、正整数 d 出力： すべての si に対しdH(s,si) ≦ d を満たす 長さ L の文字列 s dH(s,t)： 文字列 s と t の間のハミング距離（ミスマッチの数） 例：　 (d=3) この問題は NP困難 最近接文字列問題： アイデア 命題： dH(s,t) は三角不等式を満たす 補題1： dH(si,sj)2d を満たす i≠j があれば、(?si)(dH(s,si)≦d) を満たす s は存在しない 証明： そのような s が存在したとすると 2d≧dH(s,si)+dH(s,sj)≧dH(si,sj)2d　となり、矛盾 アイデア： t=s1から始めて（この時は最大距離は補題1より 2d 以下）、d が１ずつ減るように補題2を用いて t を変えていく 補題2： ddH(t,si)≦2d 、 dH(s,si)≦d とすると、t[j]≠si[j] を満たす任意の j を d+1 個選べば、少なくとも1個の j について、s[j]=si[j] が成立 証明:　もともと dH(s,si)≦d なので、任意の d+1 個を選べば明らかに少なくとも１個は s[j]=si[j] が成立。 最近接文字列問題： アルゴリズム アルゴリズム： ClosestString(s1,d) を実行 補題2 最近接文字列問題： 解析 定理： 最近接文字列問題は O((d+1)d poly(k,L))時間で解ける 証明: 正当性は補題1,2より明らか。 毎回 d+1 個の再帰