層状ネットワークにおける段階的な最適化問題に関する研究

本研究では，層状のネットワーク上における組合せ最適化問題に取り組むことを目的としている．例えば，文字列で表されるデータ（例えばユーザの行動に関する時系列データや発見したDNAの列など）が２台のデバイスからサーバに送られて，サーバ側では，それらの共通部分を求めたいことがある．このように複数の文字列データから共通部分を求める場合には，何をもって共通な部分であると捉えるかによって，様々な問題設定がある．例えば，共通な部分文字列のうち最長なものだったり，さらに最長な共通部分文字列に出現する文字数を制限したい場合もあったりなどする．今年度は，それらのうち，2つの文字列から出現文字数が制限された最長な共通部分文字列を探す問題，2つの文字列のうち片方の文字列にいくつかの文字を追加することで他方の文字列との共通部分列をできるだけ長くする問題，2つの文字列から共通な部分文字列を探したいが，そのときその共通部分列に含まれる文字を事前に指定された文字集合とできるだけ重複させたい問題，などの問題について考察した．得られた結果としては，これらの問題は厳密には異なる問題であるが，多項式時間をかけて問題間の変形操作を行うことで，ある一つの指数時間アルゴリズムですべての問題を解決できることを示した．またその指数時間アルゴリズムとして，既知のものよりも，高速なアルゴリズムを開発した．以上のような研究成果を，査読付き国際会議 Annual Symposium on Combinatorial Pattern Matching ならびに国内研究集会 電気・情報関係学会九州支部連合大会において公表した．

本研究では，層状のネットワーク上における組合せ最適化問題に取り組むことを目的としている．例えば，文字列で表されるデータ（例えばユーザの行動に関する時系列データや発見したDNAの列など）が２台のデバイスからサーバに送られて，サーバ側では，それらの共通部分を求めたいことがある．このように複数の文字列データから共通部分を求める場合には，何をもって共通な部分であると捉えるかによって，様々な問題設定がある．例えば，共通な部分文字列のうち最長なものだったり，さらに最長な共通部分文字列に出現する文字数を制限したい場合もあったりなどする．今年度は，それらのうち，2つの文字列から出現文字数が制限された最長な共通部分文字列を探す問題，2つの文字列のうち片方の文字列にいくつかの文字を追加することで他方の文字列との共通部分列をできるだけ長くする問題，2つの文字列から共通な部分文字列を探したいが，そのときその共通部分列に含まれる文字を事前に指定された文字集合とできるだけ重複させたい問題，などの問題について考察した．得られた結果としては，これらの問題は厳密には異なる問題であるが，多項式時間をかけて問題間の変形操作を行うことで，ある一つの指数時間アルゴリズムですべての問題を解決できることを示した．またその指数時間アルゴリズムとして，既知のものよりも，高速なアルゴリズムを開発した．以上のような研究成果を，査読付き国際会議 Annual Symposium on Combinatorial Pattern Matching ならびに国内研究集会 電気・情報関係学会九州支部連合大会において公表した．