回溯法1

回溯法是一种通过探索所有可能的候选解来找出所有解的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化来舍弃该解，即“回溯”并尝试另一种可能。 个人计算机的国际象棋程序使用回溯法来发现玩家可能采取的所有步骤。基本原理来自分治法 (divide and conquer)。将问题实例分割成一些子问题，这些子问题互相独立且与原问题形式相同。递归地解决这些子问题，然后将各子问题的解合并即可得到原问题的解。