局部搜索算法成功的惊人例子

计算科学 优化 算法 组合学 启发式
2021-12-21 02:59:02

在 N 皇后问题https://en.wikipedia.org/wiki/Eight_queens_puzzle中，试图通过回溯找到解决方案会很快遇到困难（即使对于 SWI-Prolog，http ://swish.swi-prolog.org/example/clpfd_queens .pl，它在 0.2 秒内解决 N=100，在上面的链接中输入 N=150 并没有在合理的时间内达到解决方案（“超出时间限制”），对于 ECLiPSe（另一个带有约束 poropagation 的 Prolog）它更早地窒息了......）。

另一方面，本地搜索在这个问题上的效果非常好（https://stackoverflow.com/questions/1863531/n-queens-probiem-how-far-can-we-go，用户 chesslover 的回答），如解决方案似乎很容易通过爬山（或者更确切地说，在这种情况下，偶尔进行短程爬山）从可能配置空间中的随机位置开始（每列恰好由一个女王占据）。

哪些其他众所周知的问题似乎具有相似的属性（例如，来自https://en.wikipedia.org/wiki/Local_search_(optimization)中给出的示例的一部分）？

1个回答

以下论文

对局部搜索与类似回溯的算法进行了彻底的比较。在介绍中，它甚至提出了一个问题：

“本地搜索和回溯之间的本质区别是什么，有时可以使本地搜索原因比回溯更好地扩展”

在描述他的混合局部搜索+回溯算法的变体时，Prestwich 对其进行了测试

  • 经典的N皇后问题
  • 图着色与“时间表、调度、频率分配、计算机寄存器分配、印刷电路板测试和模式匹配的实际应用”
  • 可满足性（SAT）

以上所有内容（可能具有专业化）都可以作为您问题的示例。

与本地搜索算法与类似回溯的比较直接相关的另一个参考是：

这还将讨论本地搜索比回溯执行更好的可能原因。

一般来说，可能的原因可以总结为（Prestwich，2001）：

  • 随机性
  • 不完整性
  • 可扩展性
  • 不同的搜索空间
  • 跟随梯度的能力
  • 回溯对早期变量赋值的承诺

我想到的最后一个参考是一篇不错的博士论文

这将具有其他几个（取决于分类）用于本地搜索的应用程序，其中回溯会受到影响。

其它你可能感兴趣的问题
上一篇通过引导发现学习计算科学 下一篇我如何确定函数何时处于“下溢边缘”？