Developing a Theory of Heuristics

发展启发式理论

• 批准号: 9734911
• 负责人: Russell Impagliazzo
• 金额: $ 19.46万
• 依托单位: University of California-San Diego
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1998
• 资助国家: 美国
• 起止时间: 1998-07-15 至 2001-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9734911&HistoricalAwards=false
• 关键词: Developing; Theory; Heuristics

Current theory does little to predict, explain or analyze the empirically observed success of search and optimization heuristics for some domains of NP-complete problem and their failure for others. Without such a theory, implementers of heuristics have no guidance as to whether a particular heuristic method is suitable for a particular problem domain, what kind of performance to expect, or how to set the various parameters for better performance. Implementation is often done in a haphazard way based on little more than guess-work or trial-and-error. The following inter-related lines of theoretical research will be explored to address this gap: (1) Extending average-case complexity to consider reductions to and between problem distributions that arise naturally ( in real-life, testing, cryptanalysis or combinatorics). (2) Extending average-case analysis techniques to a more general characterization of the relevant combinatorial properties of random problem instances from naturally arising distributions. In particular, the properties of associated search spaces for such problems. (3) For experimentally successful heuristic methods, identify the combinatorial characteristics of problem instances that determine their performance. (4) Investigate more efficient worst-case algorithms for NP complete problems, identify those NP complete problems with nontrivial worst-case algorithms, and explore the connection between lower and upper bounds. Although the techniques used are solely mathematical, the motivation and justification come from the experimental literature.

目前的理论并没有预测，解释或分析经验观察到的成功的搜索和优化算法的一些领域的NP完全问题和他们的失败的其他人。 如果没有这样的理论，启发式算法的实现者就无法指导特定的启发式方法是否适合特定的问题域，期望什么样的性能，或者如何设置各种参数以获得更好的性能。 实现通常是以一种偶然的方式完成的，这种方式只不过是基于猜测或试错。 将探索以下相互关联的理论研究路线来解决这一差距：（1）扩展平均情况的复杂性，以考虑自然出现的问题分布（在现实生活中，测试，密码分析或组合学）之间的减少。(2)将平均情况分析技术扩展到自然产生的分布的随机问题实例的相关组合性质的更一般的表征。 特别是，这些问题的相关搜索空间的属性。(3)对于实验上成功的启发式方法，识别决定其性能的问题实例的组合特征。(4)研究NP完全问题的更有效的最坏情况算法，识别具有非平凡最坏情况算法的NP完全问题，并探索上下界之间的联系。 虽然所使用的技术完全是数学的，动机和理由来自实验文献。