A*算法； 近似算法第一讲，介绍了近似算法的概念，近似算法的关键。
编辑中
A*算法
待编辑
近似算法
回顾
NP完全问题
在第一节课的时候，老师讲了计算问题的分类，总的可分为NP问题和Non-NP问题，其中NP-H问题又是独立于此分类的。落在NP这边的NP-H问题我们称为NP完全问题。
NP完全问题是指使用确定的图灵机在多项式时间内不能求解的问题。就是说，用我们现在的计算机，只能在关于输入的指数时间消耗内求得精确解。
引出近似算法
小规模的数据，我们还可以尝试在指数时间内求出精确解。不过对于大规模数据，指数代价是不可接受的。
所以，在这种情况下，我们可以使用多项式时间消耗的近似算法来得到一个近似解。
第二页PPT里引用了亚里士多德的一句话：
受过教育的人的一个标志就是，他满足于接受事物自身所具有的精确程度，而当能得到近似值时，他不去追求无法获得的精确值。
概览
将从以下几个方面来讲。
-
基于组合优化的近似算法
-
基于贪心策略的近似算法
-
基于局部优化的近似算法
-
基于动态规划的近似算法
-
基于线性规划的近似算法
在本节中，我们讨论的通常都是优化问题，即需要找到所有可行解中的最大值或最小值。当这些最优化问题是NP完全问题时，我们设计一种近似算法在多项式时间内找到一个近似的优化解。本节讲的近似算法往往比较直观，但是对近似算法的分析却是难点。我们不仅需要分析这个近似算法本身的时间开销，还需要考虑近似的结果与实际的最优结果之间的差距——近似度。
通常我们用以下方法来衡量近似解代价与优化解代价的差距：
-
Ratio Bound
-
相对误差
-
$(1 \pm \epsilon)$-近似
接下来依次介绍各衡量方法。
需要注意的是，这里的代价不是指算法时间开销上的代价，而是指解本身在问题上的代价。比如最短路径中，这种差距表示近似算法找出的最短路径与实际最短路径的差值，而非这两种算法的时间开销。
Ratio Bound
设A是一个优化问题的近似算法，设该问题的输入大小为$n$，优化解的代价为$C^*$ ， 近似解的代价为$C$ ， 则Ratio Bound定义为$p(n)$，满足：
\[\max\{ \frac{C^*}{C} , \frac{C}{C^*} \} <= p(n)\]之所以有个$max$，因为我们要保证Ratio Bound值大于1 ， 而对于最小化问题，应该是$C$除以$C^*$，而最大化问题则反过来。
Ratio Bound越大，近似解越坏。Ratio Bound评价了近似算法求出的解相对于最优解的最坏情况。
相对误差
相对误差定义比较直观，就是
\[\frac{| C - C^* |}{C^*}\]相对误差界
定义相对误差界：
\[\frac{|C - C^*|}{C^*} \le \epsilon (n)\]同样相对误差界评价了近似解的最坏情况。
一些结论
-
$\epsilon (n) \le p(n) - 1$
这个，分别考虑最大化问题和最小化问题：
\[\epsilon (n) = \frac{| C - C^*|}{C^*} = |\frac{C}{C^*} - 1|\]对最小化问题，$\frac{C}{C^*} = p(n)$ , 所以有$\epsilon (n) = p(n) - 1$
对最大化问题，$\frac{C^*}{C} = p(n)$ ， 所以有$\epsilon (n) = 1 - \frac{C}{C^*} = 1 - \frac{1}{\frac{C^*}{C}} = \frac{\frac{C^*}{C} - 1 }{\frac{C^*}{C}} = \frac{p(n)-1}{p(n)} \le p(n) - 1 $
故得证。
这表明了Ratio Bound和相对误差界的关系，说明求出了Ration Bound ， 就求出了相对误差界（的范围）。
证明中直接用了等于…不要在意这些细节吧…
-
对于某些问题，$p(n)$ , $\epsilon(n)$独立于$n$，可以使用$p$和$\epsilon$表示。
-
某些NP完全问题的近似算法满足，当运行时间增加时，Ratio Bound和相对误差将减少。
近似模式
一个优化问题的近似模式是一个以问题实例$I$和$\epsilon \gt 0$为输入的算法族 ，表示为$A(I,\epsilon)$ 。
如果$A(I , \epsilon)$的运行时间是关于输入实例$I$大小$I$的多项式，则称此近似模式为多项式时间近似模式(PTAS , Polynomial Time Approximation Scheme) 。
如果$A(I , \epsilon)$的运行时间是关于输入实例$I$大小$I$和$\frac{1}{\epsilon}$的多项式，则称此近似模式为完全多项式时间近似模式(FPAS,FPTAS ,Fully Polynomial Time Approximation Scheme) 。