4L-04
バンディットアルゴリズムを利用したLCSやLCSTの近似計算
○森光太朗，吉仲　亮，山本章博（京大）
　文字列データ同士の最長共通部分列(LCS)や木データ同士の最大共通部分木(LCST)はWebページなどのテキスト文書の比較のみならずバイオインフォマティクス分野においてDNAやRNAなどの配列の比較に応用されている.
　LCSやLCSTは動的計画法により計算できるが,一般には多くの計算量を必要とする.そこでLCSやLCSTを近似的に計算することで高速化することが考えられる.近似計算手法として本研究ではバンディットアルゴリズムに注目する.バンディットアルゴリズムは近年,ゲーム木探索のような探索手法にも応用されている.本研究では,バンディットアルゴリズムを用いてLCSやLCSTを近似的に計算する手法を提案し,その性能を既存手法との比較実験によって示す.
footer 情報処理学会 セキュリティ プライバシーポリシー 倫理綱領 著作権について