Developing a Theory of Heuristics

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

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.