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.