文献

J-GLOBAL ID：202202261251526623   整理番号：22A1104982

近似期待長計算により導かれた最短共通スーパーシーケンス問題のためのビーム探索【JST・京大機械翻訳】

A Beam Search for the Shortest Common Supersequence Problem Guided by an Approximate Expected Length Calculation

著者 (4件)： Mayerhofer Jonas (TU Wien, Vienna, Austria) ,  Kirchweger Markus (TU Wien, Vienna, Austria) ,  Huber Marc (TU Wien, Vienna, Austria) ,  Raidl Guenther (TU Wien, Vienna, Austria)
資料名： Lecture Notes in Computer Science  (Lecture Notes in Computer Science)
巻： 13222  ページ： 127-142  発行年： 2022年 
JST資料番号： H0078D  ISSN： 0302-9743  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 最短共通スーパーシーケンス問題(SCSP)は,特にデータ圧縮,計算分子生物学およびテキスト編集において,多くのアプリケーションを有するよく知られたNP困難問題である。それは,セットからのあらゆるストリングが計算ストリングのサブシーケンスであるように,入力ストリングの与えられたセットを見つけることを目的とする。そのNP硬度のため,SCSPを発見的に取り組むために多くのアプローチが提案されている。現在最良性能のものはビーム探索(BS)に基づいている。本論文では,ランダムストリングのSCSPの期待長さを近似し,マルチレベル確率的ビーム探索(MPBS)に提案した発見的埋め込みを埋め込む,BSを導くための新しい発見的(AEL)を提案した。誘導ヒューリスティックの生じるスケーラビリティ問題を克服するために,大きなインスタンスをより小さなものに縮小するカットオフアプローチを提示した。提案手法をベンチマークインスタンスの2つの確立されたセットで試験した。AELによって導かれるMPBSは,実際の実例の集合に関して,平均で,今までの先導方法より優れている。多くの場合,新しい最適解を得ることができた。Copyright The Author(s), under exclusive license to Springer Nature Switzerland AG 2022 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *近似法 ,  発見的方法 ,  応用プログラム ,  分子生物学 ,  データ圧縮 ,  問題 ,  硬度 ,  ベンチマーク ,  NP困難
準シソーラス用語： 最適解 ,  マルチレベル ,  ヒューリスティック ,  カットオフ ,  ビーム探索 ,  テキスト編集 , 【Automatic Indexing@JST】

著者キーワード (2件)： 最短共通スーパーシーケンス問題 ,  ビーム探索

分類 (2件)： 人工知能  (JE08000Z) ,  分子・遺伝情報処理  (JE15040B)

タイトルに関連する用語 (6件)： 近似 ,  期待 ,  計算 ,  シーケンス ,  問題 ,  ビーム探索