算法 是为了求解问题而给出的指令序列
正确性 ：对于符合输入类型的任意输入数据，都能产生正确的输出
有效性 ：每一步指令能够被有效的执行，并且规定了指令的执行效果和结果应该具有的数据类型，而且是可以预期的
确定性 ：每一步之后都要有确定的下一步指令
有穷性 ：在有限步内结束
分治法
将一个问题分割成几个规模小、性质相同、独立的子问题
通常通过递归方法解决子问题
合并每个子问题的解得到整个问题的解
Solve ( l)
n= size ( l)
if ( n<= smallsize)
solution= directlySolve ( l) ;
else
divide l into l1, . . . , lk.
for each i in{ 1 , . . . , k}
Si= solve ( li) ;
solution= combine ( S1, . . . , Sk) ;
return solution; 动态规划
子问题非独立：子问题求解依赖其子问题的解
描述最优解的结构特征
定义最优解决方案的递归形式
以自底向上的方式计算最优解决方案的值
从计算信息构造出最优解决方案
01背包
P ( i , w ) = m a x { v i + P ( i − 1 , w − w i ) , P ( i − 1 , w ) } 从 1 挑到 i ，背包容量为 w P(i,w)=max\{v_i+P(i-1,w-w_i),P(i-1,w)\}\\
从1挑到i，背包容量为w
P ( i , w ) = ma x { v i + P ( i − 1 , w − w i ) , P ( i − 1 , w )} 从 1 挑到 i ，背包容量为 w
矩阵链相乘 m [ i , j ] = { 0 if i = j min i ≤ k ≤ j { m [ i , k ] + m [ k + 1 , j ] + P i − 1 P k P j } if i < j m[i,j]=
\begin{cases}
0 &\text{if $i=j$}\\
\min \limits_{i\leq k\leq j}\{m[i,k]+m[k+1,j]+P_{i-1}P_kP_j\} &\text{if $i<j$}
\end{cases}
m [ i , j ] = ⎩ ⎨ ⎧ 0 i ≤ k ≤ j min { m [ i , k ] + m [ k + 1 , j ] + P i − 1 P k P j } if i = j if i < j
最长公共子序列 c [ i , j ] = { 0 if i = 0 or j = 0 c [ i − 1 , j − 1 ] + 1 if x i = y j , i , j > 0 max ( c [ i , j − 1 ] , c [ i − 1 , j ] ) if x i ≠ y j , i , j > 0 c[i,j]=
\begin{cases}
0 &\text{if $i=0$ or $j=0$}\\
c[i-1,j-1]+1 &\text{if $x_i=y_j$ , $i,j>0$}\\
\max(c[i,j-1],c[i-1,j]) &\text{if $x_i\neq y_j$ , $i,j>0$}
\end{cases}
c [ i , j ] = ⎩ ⎨ ⎧ 0 c [ i − 1 , j − 1 ] + 1 max ( c [ i , j − 1 ] , c [ i − 1 , j ]) if i = 0 or j = 0 if x i = y j , i , j > 0 if x i = y j , i , j > 0
装配线排程 f ∗ = min ( f 1 [ n ] + x 1 , f 2 [ n ] + x 2 ) f 1 [ j ] = { e 1 + a 1 , 1 if j = 1 min ( f 1 [ j − 1 ] + a 1 , j , f 2 [ j − 1 ] + t 2 , j − 1 + a 1 , j ) if j ≥ 2 f 2 [ j ] = { e 2 + a 2 , 1 if j = 1 min ( f 2 [ j − 1 ] + a 2 , j , f 1 [ j − 1 ] + t 1 , j − 1 + a 2 , j ) if j ≥ 2 f^*=\min(f_1[n]+x_1,f_2[n]+x_2)\\
f_1[j]=
\begin{cases}
e_1+a_{1,1} &\text{if $j=1$}\\
\min(f_1[j-1]+a_{1,j},f_2[j-1]+t_{2,j-1}+a_{1,j}) &\text{if $j\geq2$}
\end{cases}\\
f_2[j]=
\begin{cases}
e_2+a_{2,1} &\text{if $j=1$}\\
\min(f_2[j-1]+a_{2,j},f_1[j-1]+t_{1,j-1}+a_{2,j}) &\text{if $j\geq2$}
\end{cases}
f ∗ = min ( f 1 [ n ] + x 1 , f 2 [ n ] + x 2 ) f 1 [ j ] = { e 1 + a 1 , 1 min ( f 1 [ j − 1 ] + a 1 , j , f 2 [ j − 1 ] + t 2 , j − 1 + a 1 , j ) if j = 1 if j ≥ 2 f 2 [ j ] = { e 2 + a 2 , 1 min ( f 2 [ j − 1 ] + a 2 , j , f 1 [ j − 1 ] + t 1 , j − 1 + a 2 , j ) if j = 1 if j ≥ 2
贪婪算法
首先作出贪婪选择
求解贪婪选择后产生的唯一子问题
后续贪婪选择与前面的选择有关，但与子问题的解无关
自顶向下，问题规模逐步缩小
论证贪婪算法的正确性：用反证法：假设存在一个更优解…
最短路径
单源最短路径
Bellan-Ford：遍历所有边∣ V − 1 ∣ |V-1| ∣ V − 1∣
DAG(有向无环图)：先对图进行拓扑排序，依照拓扑序，对于每一个顶点，对始于该顶点的每条边进行缩短操作
Dijkstra(不能有负权边)：每次从剩余顶点的集合Q = V − S Q=V-S Q = V − S
全成对最短路径
APSP
l i j ( m ) = min 1 ≤ k ≤ n { l i k ( m − 1 ) + w k j } l_{ij}^{(m)}=\min \limits_{1\leq k\leq n}\{l_{ik}^{(m-1)}+w_{kj}\}
l ij ( m ) = 1 ≤ k ≤ n min { l ik ( m − 1 ) + w kj }
Floyd-Warshall
d i j ( k ) = { w i j if k = 0 min { d i j ( k − 1 ) , d i k ( k − 1 ) + d k j ( k − 1 ) } if k ≥ 1 d_{ij}^{(k)}=
\begin{cases}
w_{ij} &\text{if $k=0$}\\
\min\{d_{ij}^{(k-1)},d_{ik}^{(k-1)}+d_{kj}^{(k-1)}\} &\text{if $k\geq 1$}
\end{cases}
d ij ( k ) = { w ij min { d ij ( k − 1 ) , d ik ( k − 1 ) + d kj ( k − 1 ) } if k = 0 if k ≥ 1