Design and evaluation of adaptive algorithms

自适应算法的设计和评估

• 批准号: 10680337
• 负责人: NAKAMORI Mario
• 金额: $ 1.66万
• 依托单位: Tokyo University of Agriculture and Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 1998
• 资助国家: 日本
• 起止时间: 1998 至 2000
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-10680337/
• 关键词: adaptive algorithm; algorithm; computational complexity; merge sort; graph isomorphism

An adaptive algorithm is a methodology which finds the characteristics of the data and applys the best method of solution for the data. In the present research we investigated adaptive algorithms for graph isomorphism, sort and merge, shortest path, and three dimensional assignment. As for sort and merge, we improved the so cal led merge-sort and proposed a new fast algorithm that requires only a few memory.As for the shortest path, we proposed a hardware algorithm.As for the graph isomorphism, we noticed the effect of preprocessing and investigated the relation. We proposed the layered graph preprocessing which determines the isomorphism quickly.As for the three dimensional assignment, we proposed a method of combining imperfect components to make a reliable system.

自适应算法是一种方法，它发现数据的特性，并应用最佳的方法来解决数据。在本研究中，我们研究了自适应算法的图同构，排序和合并，最短路径，三维分配。在排序和归并方面，我们改进了归并排序算法，提出了一种新的快速算法，该算法只需要很少的内存;在最短路径方面，我们提出了一种硬件算法;在图同构方面，我们注意到了预处理的效果，并研究了它们之间的关系。提出了分层图预处理方法，快速确定同构关系;对于三维分配，提出了一种将不完整组件组合成可靠系统的方法。

项目成果

福田 和真: "グラフの同形性判定における層別グラフ利用の効果"電子情報通信学会論文誌(DI). 83. 804-807 (2000)

Kazuma Fukuda：“使用分层图确定图同构的效果”，电子、信息和通信工程师学会汇刊 (DI) 83. 804-807 (2000)。

萩原洋一: "作業場所が小さいマージソートと計算量の評価"情報処理学会研究報告. AL68,5. 33-40 (1999)

Yoichi Hagiwara：“小工作空间的合并排序和计算复杂性的评估”日本信息处理学会研究报告 AL68，5（1999）。

萩原 洋一: "作業場所が小さいマージソート" 電子情報通信学会研究報告. COMP. 57-64 (1998)

Yoichi Hagiwara：“小型工作空间的合并排序”IEICE 研究报告 57-64 (1998)。

萩原 斉: "整列問題のネットワークフローモデルによる解釈とその拡張"情報処理学会論文誌数理モデル化と応用. 40. 150-159 (2000)

Hitoshi Hagiwara：“使用网络流模型及其扩展解释排序问题”日本信息处理学会数学建模与应用杂志 40. 150-159 (2000)。

荻原斉: "整列問題のネットワークフローモデルによる解釈とその拡張"情報処理学会論文誌数理モデル化と応用. 40・2. 150-159 (2000)

Hitoshi Ogiwara：“使用网络流模型及其扩展的排序问题的解释”日本信息处理学会数学建模与应用杂志40・2（2000）。