966 字
5 分钟
ZJU ADS Algorithm Part
2024-10-22

*课程框架树#

  • Advanced DS
    • Search
      • AVL
      • RB
      • B+
      • [App]Inverted file index
    • heap
      • Leftist
      • Skew
      • Binomial
      • Fibonacci
      • Paring
  • Algorithm
    • Design Technique
      • Basic
        • Greedy
        • DP
        • Devide and Conquer
        • Backtracking
      • Opti.
        • Approximation
        • Local search
      • misc
        • Randomized
        • *Parallel
        • External Sorting
    • Analysis Technique
      • PC vs NPC
      • Amortized Analysis

Backtracking#

补充定义
  • SiS_iii步的可选域
  • game tree 又叫决策树
例一:八皇后
Si{18}xixj(ij)(xixj)(ij)1(ij)S_i\{1\cdots 8\}\\ x_i\neq x_j(i\neq j)\\ \left|\frac{(x_i-x_j)}{(i-j)}\right|\neq 1(i\neq j)
Solution 1:
Q . . . . . . .
. . . . . . Q .
. . . . Q . . .
. . . . . . . Q
. Q . . . . . .
. . . Q . . . .
. . . . . Q . .
. . Q . . . . .

Solution 2:
Q . . . . . . .
. . . . . . Q .
. . . Q . . . .
. . . . . Q . .
. . . . . . . Q
. Q . . . . . .
. . . . Q . . .
. . Q . . . . .

Solution 3:
Q . . . . . . .
. . . . . Q . .
. . . . . . . Q
. . Q . . . . .
. . . . . . Q .
. . . Q . . . .
. Q . . . . . .
. . . . Q . . .

Solution 4:
Q . . . . . . .
. . . . Q . . .
. . . . . . . Q
. . . . . Q . .
. . Q . . . . .
. . . . . . Q .
. Q . . . . . .
. . . Q . . . .
(...)

另外一个例子的阶段设计则没有那么显然

eg2. Turnpike Reconstruction
S1=[1,n]Si1=Si{li}Si1=Si{ri}S_1=[1,n] \\S_{i-1} =S_i-\{l_i\}\vee S_{i-1}=S_i-\{r_i\}\\

每个阶段的决策并不好用变量来写

具体而言我们考虑用递归的方式定义这个过程

Reconstruction(X,D,N,l,r)\mathrm{Reconstruction}(X,D,N,l,r)

表示我们已经将[1,l1],[r+1,N][1,l-1],[r+1,N]之间产生的距离全部从DD中取出,你需要安排X[lr]X[l\to r]的位置,能否产生可行解的过程

后续递归显然,剪枝即为,我们在选左和选右缩减时需要提前检查是否出现了未知的距离

Alpha-Beta prunning#

  • Minmax Strategy:以tic-tac-toe为例,A与B分别持有最大化/,最小化某一收益的前提目标,则我们可以对game tree奇偶分层分别实现最值
  • Alpha-Beta punning:基于该想法卡上下界(开始进入有奇偶两种),可以在实践中缩减规模到O(N)\mathcal O(\sqrt N)的效率(NN表示搜索树整体节点数)

Divide and Conquer#

Definition#

  • Divide :将问题规模切割成结构相似的子问题
  • Conquer : 递归解决子问题
  • Combine : 总问题的解决依赖子问题的结果,同时也需要合并

Closest Points Problem#

nn个平面上的点,求最近点对

算法描述
  • 按照xx坐标将点集分成等大小的两部分
  • 处理两侧的最近点对和跨点集的最近点对
  • 假设两侧的结果为δ\delta,则我们考虑[x0δ,x0+δ][x_0-\delta,x_0+\delta]内的点
    • 任意选取范围内一个点,则可更新区域变为[x0δ,x0+δ]×[y0,y0δ][x_0-\delta,x_0+\delta]\times [y_0,y_0-\delta]
    • 可以证明最多只有6个不重合的
      • 对左右分看看

则复杂度为T(N)=2T(N2)+O(N)=O(NlogN)T(N)=2T(\frac{N}{2})+\mathcal O(N)=\mathcal O(N\log N)

复杂度分析#

T(N)=aT(Nb)+f(N),a,bZ+T(N)=aT(\frac{N}{b})+f(N),a,b\in \mathbb Z^+

迭代求解法/递归树法#

T(N)=...=cNleavesconquer+nodeinonleafnodesf(Nnodei)combineT(N)=...=\underbrace{c N_{leaves}}_{conquer}+\underbrace{\sum_{node_i}^{non-leaf-nodes}f(N_{node_i})}_{combine}

T(N)=2T(N/2)+O(N)T(N)=2T(N/2)+\mathcal O(N)为例

T(N)=2kT(N2k)+kO(N)T(N)=2^kT(\frac{N}{2^k})+k\mathcal O(N)

k,2kT(N2k)O(N)k \to \infty ,2^kT(\frac{N}{2^k})\to \mathcal O(N)

这个基于N0[1,σ)N_0\in [1,\sigma),T(N0)=O(1)T(N_0)=\mathcal O( 1)

补充例子
T(N)=3T(N4)+Θ(N2)T(N)=3T(\frac{N}{4})+\Theta (N^2)

展开有

T(N)=i=0log4N1(316)icN2+Θ(Nlog43)<i=0(316)icN2+Θ(Nlog43)=cN21316+Θ(Nlog43)=O(N2)\begin{align*} T(N)&=\sum _{i=0}^{\log_4N-1}\left(\frac{3}{16}\right)^i cN^2+\Theta (N^{\log _43}) \\&<\sum_{i=0}^\infty \left(\frac{3}{16}\right)^icN^2+\Theta (N^{\log _4 3})\\&=\frac{cN^2}{1-\frac{3}{16}}+\Theta (N^{\log_4 3})=\mathcal O(N^2) \end{align*}

这个过程a=3,b=4,f(n)=Θ(n2)a=3,b=4,f(n)=\Theta (n^2)

代换法/归纳法#

上面这个你猜一下带入即可

T(N)=dNlogNdN(log2323)+cNdNlogNfordc/(log2323)\begin{gathered} \text{T(N)} \\ =dN\log N-dN(\log_23-\frac23)+cN\leq dN\log N \\ ford\geq c/(\log_23-\frac23) \end{gathered}

Master Method#

对于形如T(N)=aT(N/b)+f(N)T(N)=aT(N/b)+f(N)的递推式: 1.若f(N)=O(N(logba)ε)f(N)=O(N^{(\log_ba)-\varepsilon}), for ε>0\varepsilon>0,那么T(N)=Θ(Nlogba);T(N)=\Theta(N^{\log_ba}); 2.若f(N)=Θ(Nlogba)f(N)=\Theta(N^{\log_ba}),那么T(N)=Θ(NlogbalogN);T(N)=\Theta(N^{\log_ba}\log N); 3.若f(N)=Ω(N(logba)+ε)f(N)=\Omega(N^{(\log_ba)+\varepsilon}), for ε>0\varepsilon>0af(Nb)<cf(N)af(\frac Nb)<cf(N), for c<1c<1 and N>N0\forall N>N_0,那么T(N)=Θ(f(N));T(N)=\Theta(f(N));

注意
  • Merge sort
    • a=b=2a=b=2,case2, T(N)=O(NlogN)T(N)=\mathcal O(N\log N)
  • a=b=2,f(N)=NlogNa=b=2,f(N)=N\log N
    • 这个主定理没给出所有情况,且有间隙

Proof#

Case1#

f(N)=O(Nlogbaε)f(N)=\mathcal O(N^{\log_ba-\varepsilon}), 那么T(N)=Θ(Nlogba);T(N)=\Theta(N^{\log_ba});

Case2#

f(N)=(Nlogba)f(N)=\mathcal(N^{\log_ba}), 那么T(N)=Θ(NlogbalogN);T(N)=\Theta(N^{\log_ba}\log N);

证明:前面的部分和情况一的类似,我们通过相同的步骤得到相同的求和式:

T(N)=Θ(Nlogba)+j=0(logbN)1ajf(Nbj)T(N)=\Theta(N^{\log_ba})+\sum_{j=0}^{(\log_bN)-1}a^jf(\frac N{b^j})

而我们有条件f(N)=Θ(Nlogba)f(N)=\Theta(N^{\log_ba}),将它代入到上式中得到:

T(N)=Θ(Nlogba)+j=0(logbN)1ajΘ((Nbj)logba)=Θ(Nlogba)+Θ(Nlogba×j=0(logbN)1(ablogba)j)=Θ(Nlogba)+Θ(Nlogba×logbN)=Θ(NlogbalogN)\begin{aligned}T(N)&=\Theta(N^{\log_ba})+\sum_{j=0}^{(\log_bN)-1}a^j\Theta\left(\left(\frac N{b^j}\right)^{\log_ba}\right)\\&=\Theta(N^{\log_ba})+\Theta\left(N^{\log_ba}\times\sum_{j=0}^{(\log_bN)-1}\left(\frac a{b^{\log_ba}}\right)^j\right)\\&=\Theta(N^{\log_ba})+\Theta\left(N^{\log_ba}\times\log_bN\right)\\&=\Theta(N^{\log_ba}\log N)\end{aligned}

至此,情况二证明完毕。

Case3#

f(N)=f(N)=

image-20241029153231920

Form2#

Form3 Best?#

where a1,b>1\textbf{where }a\geq 1, b> 1, and p0p\geq0 is

T(N)={O(Nlogba)if a>bkO(Nklogp+1N)if a=bkO(NklogpN)if a<bk\begin{gathered}T(N)=\begin{cases}\:O(N^{\log_ba})&\mathrm{if~}a>b^k\\\:O(N^k\log^{p+1}N)&\mathrm{if~}a=b^k\\\:O(N^k\log^pN)&\mathrm{if~}a<b^k\end{cases}\end{gathered}

ZJU ADS Algorithm Part
https://zzw4257.cn/posts/cs/ads-2/
作者
zzw4257
发布于
2024-10-22
许可协议
CC BY-NC-SA 4.0