Back Tracking 回溯

一、基本思想

  • 假设有一个部分解\((x_1,...x_i)\in S_k\)
  • 首先,我们添加\(x_{i+1} \in S_{i+1}\)
  • 判断\((x_1,...,x_i,x_{i+1})\)是否符合条件
  • 如果符合条件,则接着添加\(x_{i+2}\)
  • 如果所有\(x_{i+2}\)均不符合条件,则将\(x_{i+1}\)剔除\(S_{i+1}\),然后,选择另一个\(x_{i+1}\)

二、八皇后问题

2.1 约束

  • \(S_i={1,2,3,4,5,6,7,8}\)
  • \(i \neq j\),则\(x_i \neq x_j\)
  • \(\frac{x_i-x_j}{i-j}\neq \pm1\)

2.2 搜索树

image-20240416200340070

image-20240416200352565

三、收费公路重建问题

3.1 问题描述

给定\(x\)轴上的n个点,坐标为\(x_1<x_2<...<x_n\)

此时,每对点之间有\(\frac{n*(n-1)}{2}\)个距离

假设\(x_1=0\),给定\(\frac{n*(n-1)}{2}\)个距离,计算每个点的坐标

3.2 搜索算法

  • 找出最大距离,就是整条路经的长度(\(x_0 ==> x_n\))
  • 然后找出次大距离,这是下一个点到起点/终点的距离
  • 接着在剩下的距离中找最大的距离,这是下一个点到起点/终点的距离
  • ……

在这种算法中,可以保证每一步的枚举,最多有两种可能性

image-20240416200411259

3.3 代码

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;
}

四、回溯的模板

bool Backtracking ( int i ){   Found = false;
if ( i > N )
return true; // solved with (x1, …, xN)
for ( each xi shu Si ) {
// check if satisfies the restriction R
OK = Check((x1, …, xi) , R ); // pruning
if ( OK ) {
Count xi in;
Found = Backtracking( i+1 );
if ( !Found )
Undo( i ); //recover to (x1, …, xi-1)
}
if ( Found ) break;
}
return Found;
}

搜索策略

先找更小的\(S_i\)

一、评估函数

井字棋的评估函数:

\(f(P) =W_{computer}-W_{Human}\)

​ 其中,\(W\)表示在情况\(P\)时,可能会赢的结果(横着三个/竖着三个/斜着三个)

image-20240416200504050

image-20240416200513187

二、\(\alpha\)-\(\beta\)剪枝

2.1 \(\alpha\) pruning

根节点取子节点的最大值,子节点取其子节点的最小值

当一个子节点的子节点已经算出来小于同层次的其它值时,此时该节点一定会被放弃,因此不需要计算其它子节点了

image-20240416200525786

2.2 \(\beta\) pruning

image-20240416200545800