回溯法是一种有组织的穷尽搜索的一般技术，为了求得一组解，它常常可以避免所有的可能性。它一般适用于求解那些又潜在的大量解，但有限个数的解已经检查过的问题。

回溯法有两个基本特征

1. 节点是用深度优先搜索的方法生成
2. 不需要存储整颗搜索树，只需要存储根到当前活动节点的路径。

一般的回溯方法

一般回溯算法可以作为一种系统的搜索方法应用到一类搜索问题中，这类问题的解由满足事先定义好的某个约束向量组成(x1, x2, …, xi)组成, i是[0, n]之间的一个数，n是取决于问题阐述的常量。这里的i既可以是固定的，也可使是不固定的（不固定的情况直接置i为n变为固定的）。

在回溯法中，解向量中每个 xi 都属于一个有限的线序集Xi,因此，回溯法按词典序考虑笛卡儿积 X1*X2*...*Xn的元素。算法从最初的空向量开始，然后选择X1中最小的元素…

一般地，假定算法已经检测到部分解为$v = (x_1, x_2, .,x_j)$，它再去考虑向量$v = (x_1, x_2, .,x_j, x_{j+1})$，有下面的情况

1
2
3
4
5
6
7
8
9

1）如果v表示问题的最后解，算法记录它作为一个解，在仅希望获得一个解时就终止否则继续寻找其他解。

2）（向前步骤）如果v表示一个部分解，算法通过选择集合Xj+2中最小的元素向前。

3）如果v既不是最终解也非部分解，则有两种情况

​	a)若果`Xj+1`还有其他元素，则设为下一个 

​	b)如果没有下一个，则把`Xj`设为下一个

用两个过程形式化地描述一般地回溯过程，一个是递归，一个是迭代。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

Algorithm 13.4 BacktrackRec
Inputs 集合X1, X2, ..., Xn的清楚或隐含的描述
Outputs 解向量 u = (x1, x2, .., xi), 0<=i<=n
    v = ()
    flag = False
    advance(1)
    if flag:	output v # v是解向量
    else: output "no solution"

def advance(k)
    for x ∈ Xk
        xk = x; xk加入v
        if v为最终解: flag=True and exit
        elif v 是部分的：advance(k+1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

迭代的形式采用了两个while循环：外层循环回溯，内层循环前进
Alg 13.5 BacktrackIter
    v = ()
    flag = False
    k = 1
    while k>=1
        while Xk 还未被完全穷举
            xk = next(Xk); xk加入v
            if v为最终解: flag=True and exit
            elif v是部分的: k = k + 1 # 前进 {Forward}
        重置 Xk，使得下一个元素排在第一位
        k = k - 1 # 回溯 {Backward}

    if flag:	output v # v是解向量
    else: output "no solution"

几何算法通常考虑的对象是二维或者高维空间的点、线、多边形和其他几何体。

平面扫描算法由两个基本部分组成：

1. 事件点进度表（Event），类似于一条道路的前后路标。在某些情况下需要动态更新。
2. 扫面线状态（State），是扫描线上几何对象的适当描述。

基本概念：

• 简单、非简单多边形
• 凸多边形、
• 点集S的凸包CH(S)、包顶点（S）的极点
• u(x1, y1), v(x2, y2), w(x3, y3)三点形成的三角形的带符号面积
• 左旋、右旋

18.3 计算线段的交点

1. 事件点进度表E　由线段的端点和交点构成，在扫描的过程中会动态地改变
2. 扫描线的状态：是线段的序关系

18.4 凸包问题

给定平面上n个点的集合S，寻找它们的凸包CH(S)。教材上所讲的Graham的几何扫描算法，以某一个点为中心以放射线的形式逆时针扫描所有点（计算极角，再排序）。

它的事件点进度表E 是各个点按照极角的排序，扫描线的状态是一个栈St

18.5 计算点集的直径

点集的直径：S中任意两点距离的最大值。

计算点集直径的朴素(naive)做法是以n方的时间遍历所有的点对。课本介绍的方法，是通过在凸包上遍历把时间复杂度降到nlgn。

定义：设p是一个多边形，P的一条支撑线是指通过P顶点的一条直线l，它使得P的内部整个地在l的一边.

定义：接纳两条平行支撑线的任意两点称为跖zhi对.

推论：在凸多边中实现直径的任何顶点对是一个跖对.

引入外部代码

1. put codes file in downloads/code/
2. insert into md file:
   for example:

reference

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1

$ hexo new "My New Post"

More info: Writing

Run server

1

$ hexo server

More info: Server

Generate static files

1

$ hexo generate

More info: Generating

Deploy to remote sites

1

$ hexo deploy

More info: Deployment