课题基金 / 基金详情

探索アルゴリズムの理論とその実働化に関する研究

探索アルゴリズムの理論とその実働化に関する研究
搜索算法理论及其实际应用研究
批准号：
11780278
负责人：
篠原 歩
金额：
$1.34万
依托单位：
Kyushu University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Encouragement of Young Scientists (A)
财政年份：
1999
资助国家：
日本
项目状态：
已结题
起止时间：
1999 至 2000
来源：
https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-11780278/
关键词：
機械学習例からの学習最適パターン部分列探索アルゴリズム計算量計算学習理論文字列照合

项目摘要

项目成果

篠原 歩的其他基金

相关文献

中文摘要
翻译
点击翻译按钮获取中文摘要
英文摘要
人工知能の問題解決において,探索は常に鍵となる役割を果たしている.実際のアプリケーションにおいては,問題固有の知識を利用しながら探索を制御し,探索経路の組み合わせ的爆発に対する工夫を行うことが必要である.今年度は,情報を表現し保持するための最も基本的なデータ構造である文字列に関する探索問題を設定し,部分文字列の持つ性質を生かして,実用上は多くの場合において全解探索を避けられる枝刈りヒューリスティックを提案し,実験によってその効果を検証した.この問題は,実用的な観点から,与えられた2つの文字列集合SとTを分類するために最良な部分列パターンを見つけ出す方法を示すことを目標としたものであるが,NP困難であることが知られている問題と深い関連があり,最悪時には潜在的に指数的に多い候補パターンを調べあげることを余儀なくされる.すなわち基本的には,それぞれのパターンωに対して,ωを部分文字列として含む文字がSとTにそれぞれいくつ存在するかを数え上げなければならない.そこでまず,文字列集合の部分列をすべて受理する部分列オートマトンを高速に構築するアルゴリズムを開発して実装することで,この数え上げ自身を高速化した.この部分列オートマトンの構築アルゴリズムは,現在知られている中で最も効率のよいものである.さらに,可能な限り候補となる部分列を減らすために,部分列に関する包含関係と,目的関数の性質をうまく組み合わせることによって,探索空間を効率的に枝刈りするヒューリスティクスを2つ提案した.これをアミノ酸配列やDNA配列に対する実験に適用し,それぞれのヒューリスティクスの効果と,部分列オートマトンによる高速化の度合いを確認した.
期刊论文(14)
专著(0)
科研奖励(0)
会议论文
T.Kida et al.: "A Unifying Framework for Compressed Pattern Matching"Proc.6th Int.Symp.on String Processing and Information Retrieval. 89-96 (1999)
T.Kida 等人：“压缩模式匹配的统一框架”Proc.6th Int.Symp.on 字符串处理和信息检索。
DOI： --
发表时间：
期刊：
影响因子： --
作者： []
通讯作者：
S.Arikawa et al.: "Developments in computational learning and discovery theory within the framework of elementary formal systems"Machine Intelligence. 15. 227-247 (1999)
S.Arikawa 等人：“基本形式系统框架内计算学习和发现理论的发展”机器智能。
DOI： --
发表时间：
期刊：
影响因子： --
作者： []
通讯作者：
M.Hirao,H.Hoshino,A.Shinohara,M.Takeda and S.Arikawa: "A Practical Algorithm to Find Best Subsequence Patterns"Proc.of the 3rd International Conference on Discovery Science. LNAI1967. 141-154 (2000)
M.Hirao、H.Hoshino、A.Shinohara、M.Takeda 和 S.Arikawa：“寻找最佳子序列模式的实用算法”第三届国际发现科学会议论文集。
DOI： --
发表时间：
期刊：
影响因子： --
作者： []
通讯作者：
T.Takae et al.: "Knowledge discovery from health data using weighted aggregation classifiers"Proc.2nd Int.Conf.on Discovery Science 1999. LNAI1721. 359-369 (1999)
T.Takae 等人：“使用加权聚合分类器从健康数据中发现知识”Proc.2nd Int.Conf.on Discovery Science 1999。LNAI1721。
DOI： --
发表时间：
期刊：
影响因子： --
作者： []
通讯作者：
共 7 条
    Data Compression: theoretical and practical approaches to the smallest grammar problem
    • 批准号：
      21K11745
    • 项目类别：
      Grant-in-Aid for Scientific Research (C)
    • 资助金额：
      $2.75万
    • 财政年份：
      2021
    • 负责人：
      篠原 歩
    • 依托单位：
      Tohoku University
    非明示的表現に対するアルゴリズムの開発
    文字列集合からの高速パターン抽出アルゴリズムの開発と実働化
    • 批准号：
      14780226
    • 项目类别：
      Grant-in-Aid for Young Scientists (B)
    • 资助金额：
      $2.05万
    • 财政年份：
      2002
    • 负责人：
      篠原 歩
    • 依托单位：
      Kyushu University
    遺伝子ネットワークの解析と可視化システムの開発
    • 批准号：
      13208025
    • 项目类别：
      Grant-in-Aid for Scientific Research on Priority Areas (C)
    • 资助金额：
      $2.18万
    • 财政年份：
      2001
    • 负责人：
      篠原 歩
    • 依托单位：
      Kyushu University