回溯法

维基百科,自由的百科全书
跳转至: 导航搜索

回溯法英语backtracking)是暴力搜尋法中的一种。

回溯法采用试错的思想,它尝试分步的去解决一个问题。在分步解决问题的过程中,当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候,它将取消上一步甚至是上几步的计算,再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现,在反复重复上述的步骤后可能出现两种情况:

  • 找到一个可能存在的正确的答案
  • 在尝试了所有可能的分步方法后宣告该问题没有答案

在最坏的情况下,回溯法会导致一次复杂度指数时间的计算。

典型应用[编辑]

八皇后问题是应用回溯法求解的典型案例。

相关链接[编辑]