6 Backtracking¶
回溯算法就是深度优先搜索
A sure-fire way to find the answer to a problem is to make a list of all candidate answers, examine each, and following the examination of all or some of the candidates, declare the identified answer.
The basic idea is to start with a partial solution \(( x_1, ... , x_i )\) where each \(x_k \in S_k\) for \(1\le k \le i < n\). Then, we add \(x_{i+1} \in S_{i+1}\) and check if \(( x_1, ... , x_i, x_{i+1}\) ) satisfies the constraints. If the answer is “yes”, we continue to add the next \(x\), else we delete the current \(x_{i+1}\) and try the next \(x_{i+1} \in S_{i+1}\). If all possible \(x_{i+1}\in S_{i+1}\) fail to satisfy the constraints, we backtrack to the previous partial solution \(( x_1, ... , x_{i-1} )\).
八皇后问题¶
Find a placement of 8 queens on an \(8\times8\) chessboard such that no two queens attack.
Rule: Two queens are said to attack iff they are in the same row, column, diagonal, or antidiagonal of the chessboard.
Step 1: Construct a game tree
相当于把解空间用树的形式展开了
Step 2: Perform a depth-first search ( post-order traversal ) to examine the paths
The Turnpike Reconstruction Problem¶
Given N points on the x-axis with coordinates \(x_1 < x_2 < …< x_N\) . Assume that \(x_1 = 0\). There are \(N ( N – 1 ) / 2\) distances between every pair of points.
Given \(N ( N – 1 ) / 2\) distances. Reconstruct a point set from the distances.
解题的关键点在于从大往小来枚举，先从已知数列中找到最大的那个，然后分两种情况（当然第一个不需要）接着将与原先存在的数的差依次从原数列中删去（如果删不了，那么产生矛盾）。然后继续枚举。
bool Reconstruct ( DistType X[ ], DistSet D, int N, int left, int right )
{
/* X[1]...X[left-1] and X[right+1]...X[N] are solved */
bool Found = false;
if ( Is_Empty( D ) )
return true; /* solved */
D_max = Find_Max( D );
/* option 1：X[right] = D_max */
/* check if |D_max-X[i]|$D is true for all X[i]’s that have been solved */
OK = Check( D_max, N, left, right ); /* pruning */
if ( OK )
{ /* add X[right] and update D */
X[right] = D_max;
for ( i=1; i<left; i++ ) Delete( |X[right]-X[i]|, D);
for ( i=right+1; i<=N; i++ ) Delete( |X[right]-X[i]|, D);
Found = Reconstruct ( X, D, N, left, right-1 );
if ( !Found )
{ /* if does not work, undo */
for ( i=1; i<left; i++ ) Insert( |X[right]-X[i]|, D);
for ( i=right+1; i<=N; i++ ) Insert( |X[right]-X[i]|, D);
}
}
/* finish checking option 1 */
if ( !Found )
{
/* if option 1 does not work */
/* option 2: X[left] = X[N]-D_max */
OK = Check( X[N]-D_max, N, left, right );
if ( OK )
{
X[left] = X[N] – D_max;
for ( i=1; i<left; i++ ) Delete( |X[left]-X[i]|, D);
for ( i=right+1; i<=N; i++ ) Delete( |X[left]-X[i]|, D);
Found = Reconstruct (X, D, N, left+1, right );
if ( !Found )
{
for ( i=1; i<left; i++ ) Insert( |X[left]-X[i]|, D);
for ( i=right+1; i<=N; i++ ) Insert( |X[left]-X[i]|, D);
}
}
/* finish checking option 2 */
} /* finish checking all the options */
return Found;
}
//上述代码应该只能给出一种结果，靠右的那种
Alpha-Beta Pruning¶
Games – how did AlphaGo win, 以Tic-tac-toe为例
Use an evaluation function to quantify the "goodness" of a position. For example:
where \(W\) is the number of potential wins at position \(P\).
如何计算\(f(p)?\)
将所有位置上填满相应的符号，获胜的条数就是相应的\(W\)
The human is trying to minimize the value of the position \(P\), while the computer is trying to maximize it.
\(α-β\) pruning: when both techniques are combined. In practice, it limits the searching to only \(O(\sqrt N)\) nodes, where \(N\) is the size of the full game tree.
that the best-case performance is \(O((2b)^{d/2})\) where \(b\) is thebranching factor and \(d\) is the depth.
上述定理的证明：
回溯算法模板¶
bool Backtracking ( int i )
{
bool Found = false;
if ( i > N )
return true; //返回N维的解
for ( each xi in Si ) {
//检验加入了xi后满不满足条件
OK = Check((x1, …, xi) , R );
if ( OK ) {//满足
Count xi in;//加入解集
Found = Backtracking( i+1 );//找下一个解
if (!Found )//没找到
Undo( i ); //undo,回到i-1维解集,算下一个xi
}
if ( Found ) break;
}
//全找完了也没找到返回false
return Found;
}
评论区
对你有帮助的话请给我个赞和 star =>
欢迎跟我探讨！！！