|
|
|
|
回溯法也称试探法,该方法首先暂时放弃关于问题规模大小的限制,并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时,就选择下一个候选解;如果当前候选解除了不满足问题规模要求外,满足所有其他要求,继续扩大当前候选解的规模,并继续试探;如果当前候选解满足包括问题规模在内的所有要求时,该候选解就是问题的一个解。
|
|
|
在回溯法中,放弃当前候选解、寻找下一个候选解的过程称为回溯;扩大当前候选解的规模并继续试探的过程称为向前试探。
|
|
|
|
n皇后问题是源于国际象棋的一个问题,n皇后问题要求在一个n×n格的棋盘上放置n个皇后,使得它们彼此不受攻击。按照国际象棋的规则,一个皇后可以攻击与之在同一行或同一列或同一条斜线上的其他任何棋子。因此n皇后问题等价于要求在一个n×n格的棋盘上放置n个皇后,使得任何两个皇后不能被放在同一行或同一列或同一条斜线上。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|