Local Search & the Local Structural of NP-Complete Problems

本地搜索

• 批准号: 8918780
• 负责人: Lov Grover
• 金额: --
• 依托单位: Cornell University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1990
• 资助国家: 美国
• 起止时间: 1990-04-01 至 1993-03-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8918780&HistoricalAwards=false
• 关键词: Local; Search; & Structural; NP

The local structure of complex problems is being studied. It has been shown that certain NP-complete problems satisfy a linear difference equation that is similar to the wave equation of mathematical physics; some immediate consequences of this have already been deduced. It has been proved that local search algorithms starting from an arbitrary poor configuration, under certain conditions, converge to the average cost of the system in O(n) iterations. The solution of the equation and its application to the analysis and design of local search algorithms like simulated annealing and Kernighan-Lin search are being studied. Extensions of these techniques to interior point methods are being developed. A hypothesis has been proposed regarding these neighborhood structures for which local search algorithms will generally be most successful. Several tests are being conducted to verify this hypothesis. These include a new local search algorithm for the traveling salesman problem that, unlike existing algorithms of the same neighborhood size, is expected to be successful even when the triangle inequality is not satisfied and/or the distances between cities are asymmetric.

正在研究复杂问题的局部结构。 已经 表明某些NP完全问题满足线性差 方程类似于数学波动方程 物理学;这一点的一些直接后果已经被 推导 已经证明，局部搜索算法 从任意的不良配置，在某些条件下， 算法的时间复杂度为O（n）。 的 方程的解及其在分析和 设计局部搜索算法，如模拟退火和 Kernighan-Lin搜索正在研究中。 这些扩展 正在开发内点方法的技术。 一 关于这些邻域结构提出了一个假设 局部搜索算法通常最成功。 目前正在进行几项测试以验证这一假设。 这些 包括一个新的局部搜索算法的旅行推销员 问题是，与相同邻域大小的现有算法不同， 即使三角不等式不成立， 满意和/或城市之间的距离不对称。