アルゴリズムの平均計算量に関する基礎的研究

算法平均计算复杂度的基础研究

• 批准号: 05680270
• 负责人: 平田 富夫
• 金额: $ 1.34万
• 依托单位: Nagoya University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for General Scientific Research (C)
• 财政年份: 1993
• 资助国家: 日本
• 起止时间: 1993 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-05680270/
• 关键词: アルゴリズム; 平均計算量; 確率モデル; 充足可能性問題; 頂点被覆問題

近年の平均計算量の解析においては、複素解析や積分変換などが導入され、その解析技法は著しく発展しつある。また、計算複雑さの理論においても、平均計算量に基づく新しい理論が構築されつつある。いずれの場合も、最も重要なのは、入力モデル(入力分布、確率モデル)を適切に定めることである。すなわち、実際的な意味でのアルゴリズムの性能をよく反映し、しかも、解析が可能であるようなモデルを見つけることが重要である。本研究の目的は、平均計算量の解析技法をさらに展開するための基礎的研究として、幾つかの重要な離散構造問題について適切な入力モデルを探すことである。本研究では、まず、知られている平均計算量解析技法のサイーベイを行なった。これについては準備がととのいしだい発表する予定である。このサーベイの一環として、Handbook of Theoretical Computer.Science,Vol.A,Elseveir Science Publishersの第9章(アルゴリズムとデータ構造の平均計算量解析)の翻訳をおこなったが、それは「コンピュータ基礎理論ハンドブック」(丸善)として刊行された。次に、NP完全問題としてよく知られている充足可能性問題およびグラフの頂点被覆問題をとりあげ、これらの問題の平均的な性質を調査した。これらの問題を解くアルゴリズムとして、分枝限定法に基づくものと遺伝子アルゴリズムに基づくものを作成し、種々の入力モデルについて計算機実験を行ない妥当性を検討した。この結果、実際的な意味でのアルゴリズムの性能を反映する有力な入力モデルが得られ本研究の初期の目的を達した。設備備品として購入したワークステーションは上記の計算機実験に使用された。また、この上に数式処理システムを導入し理論解析の補助としても用いた。

In recent years, the analysis of average calculation quantity has been introduced, and the analysis technique has been developed. The theory of calculation is based on the theory of average calculation. In the case of the most important factor, the input force is determined appropriately. The real meaning of the word is that it is important to reflect, analyze, and analyze the performance of the word. The purpose of this study is to develop analytical techniques for average computation and to explore the basis for the study of important discrete structural problems. In this study, the average calculation amount analysis technique is used to analyze the behavior of the system. This is the first time that I have ever been in a situation where I've been in a situation Chapter 9 of Handbook of Theoretical Computer.Science, Vol. A, Elsevier Science Publishers (Analysis of Average Computational Quantity of Structure) was published in "Basic Theory"(Maruzen). NP-complete problems are investigated in terms of sufficient probability problems, vertex coverage problems, and average properties. This problem is solved by branch restriction method, and the correctness of computer operation is discussed. The results and practical implications of this study are reflected in the performance of the system, and the initial objectives of this study have been achieved. The equipment was purchased and used in the computer system. The above formula is used to solve the problem.

项目成果

譚学厚: "Designing efficient geometric searching algorithms using persistent binary-binary search trees" Transactions of IEICE on Information and Systems. E76(発表予定). (1994)

谭学厚：“使用持久二元搜索树设计高效的几何搜索算法”，IEICE 信息与系统汇刊（1994 年）。

譚学厚: "An incremental algorithm for constructing shortest watchman routes" International Journal of Computational Geometry & Applications. 3. 351-365 (1993)

谭学厚：“构建最短看守路线的增量算法”国际计算几何与应用杂志3. 351-365 (1993)。

平田富夫: "Constructing Shortest watchman routes by divide and conquer" Proceedings of International Symposium on Algorithms and Computation(LNCS). 762. 68-78 (1993)

Tomio Hirata：“通过分而治之构建最短守望者路线”国际算法与计算研讨会论文集（LNCS）762. 68-78（1993）。