一、贪心

自顶向下解决问题，使问题规模减小。

1.1 埃及分数

$7/8=1/2+1/3+1/24$

对于分数 $A/B$ ( $A<B$ )，$B=A*C+D$，则 $B/A=C+D/A<C+1$，则 $A/B>1/(C+1)$

则 $1/(C+1)$ 是包含于 $A/B$ 中最大的埃及分数。

令 $E=C+1$，则 $A/B-1/E=((AE)-B)/(BE)$

算法：

1.2 活动选择问题

贪心算法：选择结束时间最早的活动（假设活动1为最早结束的活动）

假设 $A\subseteq S$ 是最优解，将活动按照结束时间进行排序，在 $A$ 中的第一个活动是 $k$：

若 $k=1$，则 $A$ 以贪心选择开始
若 $k\neq 1$，则存在一种方法 $B$ 以贪心解开始（活动1）
- 令 $B=A-{k} \cup{1}$，$f_m=min{f_k:a_k\in S_{ij}}(其中a_m为S_{ij}中最早结束的活动)$，则有 $f_1\leq f_k$
- $B$ 中的活动是不相交的(相容的)
- $B$ 中活动的数量与 $A$ 相同，因此 $B$ 是最优的。

将活动按照最早结束时间排序，然后执行以下算法：

思考题1116：任务调度

1.3 背包问题

每件物品 $i$ 都有一定的重量 $w_i$ 和效益值 $b_i$ (所有的 $w_i$、 $b_i$ 和最大容量$W$ 都是整数值)，按照 $v_i/w_i$ 排序来装入物品可以使所装物品的总价值最大。

1.4 最佳合并模式算法(Optimal Merge Patterns)

1.4.1 算法

二叉合并树：外部节点表示实体，内部节点表示这些实体的合并的二叉树。

假设节点 $i$ 对成本的贡献为 $p_i$，从根节点到该节点的路径长度为 $L_i$，则 $L=\sum_{i=1}^{n} p_{i} L_{i}$

算法：

将 $list$ 及其长度插入到小根堆中
重复从堆中移除两个最小长度的列表 $(p_i,p_j)$。
合并长度为 $(p_i,p_j)$ 的列表，形成一个长度为 $p_{ij} = p_i+ p_j$ 的新列表
将 $p_{ij}$ 及其插入堆中，直到所有符号合并成一个最终的列表

1.4.2 应用：哈夫曼编码

$WPL$：带权路径长度

跟踪从根到每个叶(符号)的路径，以形成该符号的位串
连接“0”表示左分支，连接“1”表示右分支

1.5 最小生成树(MST)

对于带权连通无向图 $G=(V,E)$，生成树不同，每棵树的权（即树中所有边上的权值之和）也可能不同。设 $R$ 为 $G$ 的所有生成树的集合，若 $T$ 为 $R$ 中边的权值之和最小的生成树，则 $T$ 称为 $G$ 的最小生成树（MST）。

生成树的一些概念：

深度优先生成树与广度优先生成树（前面一节有讲怎么构成）

生成森林：非连通图每个连通分量的生成树一起组成非连通图的集合叫做生成森林。

[说明]

一个图可以有许多棵不同的生成树，所有生成树具有以下共同特点：

生成树的顶点个数与图的顶点个数相同

生成树是图的极小连通子图

一个有 $n$ 个顶点的连通图的生成树有 $n-1$ 条边

生成树中任意两个顶点间的路径是唯一的

在生成树中再加一条边必然形成回路

含 $n$ 个顶点 $n-1$ 条边的图不一定是生成树

最小生成树有以下重要性质：==[注意红、蓝、紫的颜色标记]==

假设 $(u,v)$ 具有最小权，其中 $u\in U[red],v\in V-U[blue]$，则必定 $\exists MST; contains; (u,v)[purple]$。

下面的算法将用到这一性质。

Prim算法

从某一个顶点开始构建生成树；每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。算法的步骤如下：

Step 1: $x\in V$, $Let;A = {x}, B = V - {x}$
Step 2: Select $(u, v)\in E$, $u\in A, v\in B$ such that $(u, v)$ has the smallest weight between A and B
Step 3: $(u, v)$ is in the tree. $A = A\cup {v}, B = B - {v}$
Step 4: If $B =\varnothing$, stop; otherwise, go to Step 2.

其时间复杂度为 $O\left( n^{2} \right)$（其中 $n=\left| V \right|$），适合用于边稠密图。

Red、Blue点可用以下方式标记：

Color Mark O(n)
set 集合 O(n)
BitString 位串

代码实现：

有两个需要注意的变量：

lowcost[v]
adjvex[v]记录是哪里来的结点

typedef struct {
    VertexType adjvex;
    VRType lowcost;
}closedge[MAX_VERTEX_NUM];

// USING Matrix
// closedge[k].lowcost=0 	// red point notation
void MiniSpanTree_Prim(MGraph G, VertexType u) {
    k = LocateVex(G, u);	// u为开始结点
    for (j = 0; j < G.vexnum; ++j)
        if (j != k)
            closedge[j] = { u, G.arcs[k][j].adj };
    closedge[k].lowcost = 0; 						// U = {u}
    for (i = 0; i < G.vexnum; ++i) {
        k = Minimum(closedge);						// 求出下一个结点
        printf(closedge[k].adjvex, G.vexs[k]);		 // 求出生成树的边
        closedge[k].lowcost = 0; 					// 加入red point set
        for (j = 0; j < G.vexnum; ++j) {
            if (G.arcs[k][j].adj < closedge[j].lowcost && closedge[j].lowcost != 0)
                // 新节点并入后重新表示蓝点的最短路径
                closedge[j] = { G.vexs[k], G.arcs[k][j].adj };
        }
    }
}

Kruskal算法

每次选择一条权值最小的边，使这条边的两头连通（原先已经连通的就不选），直到所有结点都连通。

在这个算法中需要关注的问题是：

一个点能否遍历到另一个点
两端点是否在连通分量（集合）中（该算法使用）——->避圈法

在该算法中运用到的是并查集（Union-Find Set，存在查找集合和合并集合），并查集使用树的双亲表示法。

作为“双亲”，初始双亲指向自己；双亲可以直接指向根（通过经历的边寻找），并即是一个树的根=另一个树的根（双亲）。

在算法中，当 n - 1 条边全部进入生成树中时则结束。算法的时间复杂度为$O\left( \left| E \right|{log}\left| V \right| \right)$，适合用于边稀疏图。

算法流程是：

将所有边按权重从小到大排序(调用sort函数，是该算法的瓶颈)
枚举每条边a - b，权重是c，如果a - b不连通，将这条边加入集合中去—>并查集

思考题1118：团伙数量

1.6 最小环基问题

The minimal cycle basis problem

寻找最小循环基的贪婪算法：

确定最小环基的大小，记为 $k= |E| - |V| + 1$。
找到所有的环。按权重对所有环排序。
将环逐个添加到环基中。检查添加的周期是否是基中已经存在的一些周期的组合。是，删除该环。
如果环基有 $k$ 个环，停止。

1.7 旅行商问题

设一个由 $N$ 个城市 $v_1,v_2,…,v_n$ 组成的网络，$c_{i,j}$ 为从 $v_i$ 到 $v_j$ 的代价不妨设 $c_{i,j}$ = $c_{j,i}$ ，且 $c_{i,i}=\infty$。一推销员要从某城市出发经过每城市一次且仅一次后返回出发地问如何选择路线使代价最小。

算法策略：

最近邻点策略：从任意城市出发，每次在没有到过的城市中选择最近的一个，直到经过了所有的城市，最后回到出发城市。
最短链接策略：每次在整个图的范围内选择最短边加入到解集合 $S$ 中，但是，要保证加入解集合中的边最终形成一个哈密尔顿回路。

1.8 二部图的着色

详见算法笔记-搜索与图论。

二、动态规划

自底向上解决问题，决策依赖于当前状态。

2.1 动态规划基本问题

动态规划的基本要素：

最优子结构
子问题重叠（Not Necessary）

基本框架：

划分阶段：子问题（时间、空间）
选择状态
确定决策并写出状态转移方程
写出规划方程（包括边界条件）

解决方法分类：

自顶向下（递归）

自顶向下+备忘录

Lookup_C(int n, int k)
{
	if k = 0 or k = n then return 1
	if k < 0 or k > n then return 0
	if c[n,k] < 0 then
	   c[n,k] = Lookup_C(n-1,k-1) + Lookup_C(n-1,k) )
	return c[n,k]
}

自底向上（DP）

2.2 0/1背包

有 $N$ 件物品和一个容量是 $V$ 的背包。每件物品只能使用一次。

**第 $i$ 件物品的体积是 $v_{i}$，价值是 $w_{i}$**。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输出最大价值。

2.2.1 公式推导与笔算

状态表示$f(i,j)$：
- 集合
  - 所有选法
  - 条件：(1)只从前 $i$ 个物品中选; (2)总体积$\leq j$
- 属性：$Max$(✔),$Min$,数量
状态计算：集合划分——$f(i,j)$
- 不含 $i$：$f(i-1,j)$
- 含 $i$：$f(i-1,j-v_i)+w_i$

故有：$f(i,j) = Max(f(i-1,j),f(i-1,j-v_i)+w_i)$

==[笔算题]==用动态规划法求如下0/1背包问题的最优解：有5个物品，其容量分别为(3,2,1,4,5)，价值分别为(25,20,15,40,50)，背包容量为6，写出求解过程（设计和填写表格）。

设计一个二维表 $V(i,j)$ 表示将前 $i$ 个物品装进容量为 $j$ 的背包所能获得的最大价值。根据以下递归式填表：

若 $w_i>j$，则 $V(i,j)=V(i-1,j)$
若 $w_i\leq j$，则 $V(i,j)=max{V(i-1,j),V(i-1,j-w_i)+v_i}$

找上一行同位置点及上一行减去容量位置点+当前物品价值的最大值

	j=1	j=2	j=3	j=4	j=5	j=6
i=0	0	0	0	0	0	0
i=1	0	0	25	25	25	25
i=2	0	20	25	25	45	45
i=3	15	20	35	40	45	60
i=4	15	20	35	40	55	60
i=5	15	20	35	40	55	65

$V(5,6)$ 即为问题的最优解，最大价值为65，经过回溯得到物品组合为第3和第5个物品装入背包。

2.2.2 代码与优化

例：01背包问题

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n,m;
int v[N],w[N];
int f[N][N];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n;i++)  cin >> v[i] >> w[i];
    
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j <= m; j++)
        {
            f[i][j] = f[i - 1][j];
            if(j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

优化为一维的方法：需逆序

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N];

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i ++ )
        for (int j = m; j >= v[i]; j -- )
            f[j] = max(f[j], f[j - v[i]] + w[i]);	// 1	

    cout << f[m] << endl;

    return 0;
}

注：(1式)

f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);

若改为一维(滚动数组)，且j从v[i]开始递增，则算到第i层时，f[j - v[i]]已经被更新为第i层的，不符合二维情况，故j应递减遍历。

2.3 矩阵连乘问题

在科学计算中经常要计算矩阵的乘积。矩阵 $A$ 和 $B$ 可乘的条件是矩阵 $A$ 的列数等于矩阵 $B$ 的行数。若 $A$ 是一个 $p×q$ 的矩阵，$B$ 是一个 $q×r$ 的矩阵，则其乘积 $C=AB$ 是一个 $p×r$ 的矩阵。

其标准计算公式为：

$C_{i j}=\sum_{k=1}^{q} A_{i k} B_{k j} \quad \text { 其中 } 1 \leq i \leq p, \quad 1 \leq j \leq r$

由该公式知计算 $C=AB$ 总共需要 $pqr$ 次的数乘。

现在的问题是，给定 $n$ 个矩阵 ${A_1,A_2,…,A_n}$。其中 $A_i$ 与 $A_{i+1}$ 是可乘的，$i=1,2,…,n-1$。要求计算出这 $n$ 个矩阵的连乘积$A_1A_2…A_n$。

我们设二维数组 $m[N][N]$ 表示当前矩阵的连乘次数，一维数组 $p[N]$ 表示各矩阵的维度（其中 $p[0]$ 表示第一个矩阵的行数，$pi$ 表示第 $i$ 个矩阵的列数），则有以下递归公式：

$m[i][j]=\left{\begin{array}{cc}
0 & i=j \
\min \limits_{i \leq k<j}\left{m[i][k]+m[k+1][j]+p_{i-1} p_{k} p_{j}\right} & i<j
\end{array}\right.$

我们先将 $m$ 数组的对角线初始化为0，然后依次计算第 $i$ 个矩阵与第 $i + r - 1$ 个矩阵到最后一个矩阵连乘的最优解情况；依次在 $r − 1$ 个分隔位置中依次检测最优分隔点：对于每个分隔点，变换一次分隔位置，再进行逐一测试，如果有更优的分隔点，就替换掉当前的分隔点。

由此，我们输出 $m[1][n]$，即得到最少的连乘计算次数；记录间隔位置，则可以输出计算连乘的顺序，即最佳添加括号的方式。

void MatrixChain(int n)
{
	int r, i, j, k;
	for (i = 0; i <= n; i++)				// 初始化对角线
	{
		m[i][i] = 0;
	}
	for (r = 2; r <= n; r++)				// r 个矩阵连乘
	{
		for (i = 1; i <= n - r + 1; i++)	 // 依次计算每r个矩阵相连乘的最优解情况
		{
			j = i + r - 1;
			m[i][j] = m[i][i] + m[i + 1][j] + p[i - 1] * p[i] * p[j];
			s[i][j] = i;					// 分隔位置
			for (k = i + 1; k < j; k++)		 // 变换分隔位置，逐一测试
			{
				int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
				if (t < m[i][j])			// 如果变换后的位置更优，则替换原来的分隔方法
				{
					m[i][j] = t;
					s[i][j] = k;
				}
			}
		}
	}
}

void print(int i, int j)		// 输出连乘顺序
{
	if (i == j)
	{
		cout << "p[" << i << "]";
		return;
	}
	cout << "(";
	print(i, s[i][j]);
	print(s[i][j] + 1, j);
	cout << ")";
}

2.4 最长公共子序列问题(`LCS`问题)

2.4.1 公式推导与笔算

例：最长公共子序列

给定两个长度分别为 $N$ 和 $M$ 的字符串 $A$ 和 $B$，求既是 $A$ 的子序列又是 $B$ 的子序列的字符串长度最长是多少。

4 5
acbd
abedc

输出为3。

DP问题：

状态表示$f(i,j)$：
- 集合
  - 所有在第一个序列的前$i$个字母中出现，且在第二个序列的前$j$个字母中出现的子序列
- 属性：$Max$
状态计算：
- 集合划分——$f(i,j)$
- 以$a[i],b[j]$是否出现进行划分：
  
  注：
  
  $f(i-1,j)$包含01情况，可以直接以其作为代表；
  
  $f(i-1,j)$和$f(i,j-1)$包含00情况$f(i-1,j-1)$，则可以不计算$f(i-1,j-1)$.
- 规划方程：$c[i, j]=\left{\begin{array}{ll}
  c[i-1, j-1]+1 & \text { if } x[i]=y[j] \
  \max (c[i, j-1], c[i-1, j]) & \text { otherwise }
  \end{array}\right.$

==[笔算题]==计算ABCB与BDCAB的最长公共子序列的长度。

i/j	1B	2D	3C	4A	5B
0	0	0	0	0	0
1A	0	0	0	1	1
2B	1	1	1	1	2
3C	1	1	2	2	2
4B	1	1	2	2	3

故长度为3。

2.4.2 代码实现

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
char a[N], b[N];
int f[N][N];

int main()
{
    scanf("%d%d", &n, &m);
    scanf("%s%s", a + 1, b + 1);			// 从下标为1开始读

    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= m; j ++ )
        {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            if (a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
        }
    }

    printf("%d\n", f[n][m]);

    return 0;
}

2.5 最长上升子序列问题(`LIS`问题)

例：最长上升子序列(Longest Increasing Subsequence)

给定一个长度为 $N$ 的数列，求数值严格单调递增的子序列的长度最长是多少。

7
3 1 2 1 8 5 6

答案是4($[1,2,5,6]$)。

DP问题：

状态表示$f(i)$：
- 集合：所有以第 $i$ 个数结尾的上升子序列
- 属性：$Max$
状态计算：集合划分——$f(i)$
- 划分依据：最后一个不同的点
- 以上一个数的位置进行划分(0表示没有上一个数，序列长度为1)
- 若$a_j<a_i$，则$f[i] = max(f[j] + 1),j=0,1,2,…,i-1$

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n;
int a[N], f[N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

    for (int i = 1; i <= n; i ++ )
    {
        f[i] = 1; 							// 只有a[i]一个数
        for (int j = 1; j < i; j ++ )
            if (a[j] < a[i])
                f[i] = max(f[i], f[j] + 1);
    }

    int res = 0;
    for (int i = 1; i <= n; i ++ ) res = max(res, f[i]);

    printf("%d\n", res);

    return 0;
}

时间复杂度为$O(n^2)$

2.6 最短编辑距离

例：最短编辑距离

给定两个字符串 A 和 B，现在要将 A 经过若干操作变为 B，可进行的操作有：

删除–将字符串 A 中的某个字符删除。
插入–在字符串 A 的某个位置插入某个字符。
替换–将字符串 A 中的某个字符替换为另一个字符。

求将 A 变为 B 至少需要进行多少次操作。

DP问题：

状态表示$f(i,j)$：
- 集合：所有将$a[1\sim i]$变成$b[1\sim j]$的操作方式
- 属性：$Min$
状态计算：
- 以对 $a$ 中的第 $i$ 个字母操作不同进行集合划分——$f(i,j)$
- 考虑最后一步操作，有三种操作方式，取最小值即可：
  - 删（未删除前 $a$ 中前 $i-1$ 已经和 $b$ 的前 $j$ 个已经相同）：$f(i-1,j)+1$
  - 增（未添加前 $a$ 的前 $i$ 个已经和 $b$ 的前 $j-1$ 个已经相同）：$f(i,j-1)+1$
  - 改：$f(i-1,j-1)+1;or;0$

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
char a[N], b[N];
int f[N][N];

int main()
{
    scanf("%d%s", &n, a + 1);
    scanf("%d%s", &m, b + 1);

    // 初始化
    for (int i = 0; i <= m; i ++ ) f[0][i] = i;		// a中0个字母和b中i个字母匹配,增i次
    for (int i = 0; i <= n; i ++ ) f[i][0] = i;		// a中i个字母和b中0个字母匹配,删i次

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
        {
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
            if (a[i] == b[j]) 
                f[i][j] = min(f[i][j], f[i - 1][j - 1]);
            else 
                f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
            // 或直接写成f[i][j] = min(f[i][j], f[i - 1][j - 1] + (a[i] != b[j]));
        }

    printf("%d\n", f[n][m]);

    return 0;
}

2.7 最大子段和问题

我们记a[i]表示第i个元素，dp[i]表示以a[i]结尾的最大子段和，有以下两种情况：

若dp[i-1] > 0，则 dp[i] = dp[i-1] + a[i]
若dp[i-1] < 0，则 dp[i] = a[i]

则有dp[i] = max{a[i], dp[i-1] + a[i]}

思考题1028：最大子矩阵和问题

三、分支限界

3.1 分支搜索

分支搜索法是一种在问题解空间上进行搜索尝试的算法。

在生成的结点中，抛弃那些不满足约束条件的结点，其余结点加入活结点表。然后从表中选择一个结点作为下一个E-结点。

选择下一个E-结点方式的不同导致几种分支搜索方式：

FIFO搜索
LIFO搜索
优先队列式搜索

FIFO搜索：

一开始，根结点是唯一的活结点，根结点入队。
从活结点队中取出根结点后，作为当前扩展结点。
对当前扩展结点，先从左到右地产生它的所有儿子，用约束条件检查，把所有满足约束函数的儿子加入活结点队列中。
再从活结点表中取出队首结点（队中最先进来的结点）为当前扩展结点，……，直到找到一个解或活结点队列为空为止。

LIFO搜索：

一开始，根结点入栈。
从栈中弹出一个结点为当前扩展结点。
对当前扩展结点，先从左到右地产生它的所有儿子，用约束条件检查，把所有满足约束函数的儿子入栈;
再从栈中弹出一个结点（栈中最后进来的结点）为当前扩展结点，……，直到找到一个解或栈为空为止。

优先队列式搜索（LC检索）：

为了加速搜索的进程，可以采用有效的方式选择E-结点进行扩展。

优先队列式搜索方法对每一活结点计算一个优先级（某些信息的函数值）
根据这些优先级，从当前活结点表中优先选择一个优先级最高（最有利）的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。

3.2 分支限界法基本思想

3.2.1 概述

分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。

在分支限界法中，每一个活结点只有一次机会成为扩展结点；活结点一旦成为扩展结点，就一次性产生其所有儿子结点。

在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中；从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程，该过程一直持续到找到所求的解或活结点表为空时为止。

两个重要机制：

产生分支（解空间树）
产生一个界限，能够终止许多分支（剪枝）

3.2.2 回溯法与分支限界法的比较

方法	对解空间树的搜索方式	存储结点的常用数据结构	结点存储特性	求解目标
回溯法	深度优先搜索	栈	活结点的所有可行子结点被遍历后才被从栈中弹出	找出满足约束条件的所有解
分支限界法	广度优先或最小消耗优先搜索	队列、优先队列	每个结点只有一次成为扩展结点的机会	找出满足约束条件的一个解或特定意义下的最优解

3.3 结点成本函数

$C(·)$ 是“有智力”的排序函数，依据成本排序，优先选择成本最小的活结点作为下一个扩展的E结点，$C(·)$ 又称为“结点成本函数”。

结点成本函数 $C(X)$ 的定义：

如果 $X$ 是答案结点，则 $C(X)$ 是由状态空间树的根结点到 $X$ 的成本(即所用的代价，可以是级数、计算复杂度等)
如果 $X$ 不是答案结点且子树 $X$ 不包含任何答案结点，则 $C(X)＝∞$
如果 $X$ 不是答案结点但子树X包含答案结点，则 $C(X)$ 等于子树 $X$ 中具有最小成本的答案结点的成本

结点成本的估计函数包括两部分：

$\hat{g}(X)$：由 $X$ 到达一个答案结点所需成本
$f(h(X))$：根结点到结点 $X$ 的成本
- $f(·)$ 是一个非降函数，非零的 $f(·)$ 可以减少算法作偏向于纵深检查的可能性，它强使算法优先检索更靠近答案结点但又离根较近的结点

15-谜问题状态空间树的构造：

定义成本估计函数 $\hat{c}(X)=f(X)+\hat{g}(X)$

$f(X)$ 是由根到结点 $X$ 的路径长度
$\hat{g}(X)$ 是以 $X$ 为根的子树中由 $X$ 到目标状态的一条最短路径长度的估计值，至少应是能把状态 $X$ 转换成目标状态所需的最小移动数，我们令其为不在其目标位置的非空白牌数目

使用 $\hat{C}(X)$ 的LC-检索可以使检索过程很快地定位到结点23。

3.4 0/1背包问题

首先确定一个合理的限界函数，并根据限界函数确定目标函数的界 $[down,up]$，然后按照广度优先策略遍历问题的解空间树。在分支节点上，一次搜索该节点的所有孩子节点，分别估算这些孩子节点的目标函数的可能取值，如果某孩子节点的目标函数可能取得的值超出目标函数的界，则将其丢弃，因为从某个节点生成的解不会比目前已经得到的解更好；否则，将其加入待处理节点表(简称为$PT$)中。依次从表 $PT$ 中选取使目标函数的值取得极值的节点成为当前的扩展节点，重复上述过程，直到找到最优解。

假设有4个物品，其重量分别为(4, 7, 5, 3)，价值分别为(40, 42, 25, 12)，背包容量W=10。将给定物品按单位重量价值从大到小排序，结果如下：

物品	重量(w)	价值(v)	价值/重量(v/w)
1	4	40	10
2	7	42	6
3	5	25	5
4	3	12	4

问题的解可表示为 $n$ 元向量 ${x_1, x_2, … x_n }$，$x_i\in {0,1}$，则可用子集树表示解空间, 在树中做广度优先搜索。

约束条件：$\sum_{i=1}^{n} w_{i} x_{i} \leq W$
目标函数：$V=\max \sum_{i=1}^{n} v_{i} x_{i}$

我们得到问题解的下界和上界：

下界$V_{db} =40; (1, 0, 0, 0)$——贪心思想；
上界$V_{ub} =0+(W-0)×(v_1/w_1)=0+(10-0)×10=100$

目标函数的界为 $[40, 100]$。

上限界函数：$u b=v(前i个物品获得的价值)+(W-w) \times\left(v_{i+1} / w_{i+1}\right)(剩余容量全部装入物品i+1,最多能够获得的价值)$

注：

为了对每个扩展结点保存该结点到根结点的路径，将部分解 $(x_1,…, x_i)$ 和该部分解的目标函数值都存储在待处理结点表 $PT$ 中，在搜索过程中表 $PT$ 的状态如下图所示：

3.5 多段图的最短路径问题

设图 $G=(V, E)$ 是一个带权有向连通图，如果把顶点集合 $V$ 划分成 $k$ 个互不相交的子集 $V_i(2≤k≤n, 1≤i≤k)$，使得 $E$ 中的任何一条边 $(u, v)$，必有 $u∈V_i$，$v∈V_{i+m}(1≤i＜k, 1＜i+m≤k)$，则称图 $G$ 为多段图，称 $s∈V_1$ 为源点，$t∈V_k$ 为终点。

多段图的最短路径问题是求从源点到终点的最小代价路径。

由于多段图将顶点划分为 $k$ 个互不相交的子集，所以，多段图划分为 $k$ 段，一旦某条路径的一些段被确定后，就可以并入这些信息并计算部分解的目标函数值的下界。一般情况下，对于一个正在生成的路径，假设已经确定了 $i$ 段（$1≤i≤k$），其路径为$(r_1, r_2,…, r_i, r_{i+1})$，此时，该部分解的目标函数值的计算方法即限界函数如下：

$l b=\sum_{j=1}^{i} c\left[r_{j}\right]\left[r_{j+1}\right]+\min {\left\langle r{i+1}, v_{p}>\in E\right.}\left{c\left[r_{i+1}\right]\left[v_{p}\right]\right}+\sum_{j=i+2}^{k} \text { 第 } j \text { 段的最短边 }$(走过路径长度+该节点到下一段的最小距离+剩余各段之间的最小距离之和)。

对图中所示多段图应用贪心法求得近似解为 $0→2→5→8→9$，其路径代价为 $2+7+6+3=18$，这可以作为多段图最短路径问题的上界。把每一段最小的代价相加，可以得到一个非常简单的下界，其路径长度为 $2+4+5+3=14$。于是，得到了目标函数的界 $[14, 18]$。

对于上图，具体的搜索过程如下：

（1）在根结点0，根据限界函数计算目标函数的值为14；

（2）在结点1，第1段选择边$<0, 1>$，目标函数值为 $lb=4+8+5+3=20$，超出目标函数的界，将结点1丢弃；在结点2，第1段选择边$<0, 2>$，目标函数值为 $lb=2+7+5+3=17$，将结点2加入待处理结点表 $PT$ 中；在结点3，第1段选择边$<0, 3>$，目标函数值为 $lb=3+4+5+3=15$，将结点3加入表 $PT$ 中；

（3）在表 $PT$ 中选取目标函数值极小的结点3优先进行搜索；

（4）在结点5，第2段选择边$<3, 5>$，目标函数值为 $lb=3+4+6+3=16$ ，将结点5加入表 $PT$ 中；在结点6，第2段选择边$<3, 6>$，目标函数值为 $lb=3+7+5+3=18$，将结点6加入表 $PT$ 中；

（5）在表 $PT$ 中选取目标函数值极小的结点5优先进行搜索；

（6）结点7，已确定路径是 $0→3→5→7$，可直接确定第4段的边 $<7,9>$，目标函数值为 $lb=3+4+8+7=22$，超界丢弃；在结点8，已确定路径是 $0→3→5→8$，可直接确定第4段的边 $<8, 9>$，目标函数值为 $lb=3+4+6+3=16$，为一个可行解；由于结点8是叶子结点，并且其目标函数值是 $PT$ 中最小的，所以它是最优解，搜索结束。

四、NP完备性理论

4.1 计算模型

3个基本计算模型：

随机存取机RAM(Random Access Machine)
随机存取存储程序机RASP(Random Access Stored Program Machine)
图灵机(Turing Machine)

4.2 几类问题

P ：多项式时间可解
NP：多项式时间可验证
NP-Hard：所有NP问题可以用多项式时间约化到一个问题上，则此问题是NP-hard问题
NPC：同时是NP问题和NP-Hard问题，即多项式时间可验证的NP-hard问题

性质：

只要多项式时间可解，必定多项式时间可验证，即P问题一定是NP问题
是否有属于NP-Hard但不属于NP-Complete的问题呢？答案是肯定的。例如停机问题，也即给出一个程序和输入，判定它的运行是否会终止。停机问题是不可判的，那它当然也不是NP问题。但对于SAT这样的NP问题，却可以多项式归约到停机问题。因为我们可以构造程序A，该程序对输入的公式穷举其变量的所有赋值，如果存在赋值使其为真，则停机，否则进入无限循环。这样，判断公式是否可满足便转化为判断以公式为输入的程序A是否停机。所以，停机问题是NP-Hard而不是NP-Complete。
SAT问题和逻辑电路是一一对应的，是NP-Hard问题，也是NPC问题
NP-Hard仅仅是NP问题的约化问题，其本身不一定具有NP问题的多项式时间可验证性。但是当NP-Hard具有可验证时，其就是一个NPC问题了；如果其不具又可验证性，则其只能称之为是NP-Hard问题；如果其多项式时间可解，则它也自然就是一个NPC问题了，而且当NPC问题也是多项式时间可解时，可以证明所有NP问题多项式时间可解。

ShiQuLiZhi

https://www.qqzzss.top/2023/01/23/ds-algorithm/suan-fa-ke-cheng-02-suan-fa-fen-xi-yu-she-ji-2/

本博客所有文章除特别声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 ShiQuLiZhi !

算法理论知识程序设计

嵌入式系统课程作业

2023-04-24 作业

算法程序设计

软件安全实验完整记录

2023-01-20 信息安全专业课程

信息安全软件安全

	j=1	j=2	j=3	j=4	j=5	j=6
i=0	0	0	0	0	0	0
i=1	0	0	25	25	25	25
i=2	0	20	25	25	45	45
i=3	15	20	35	40	45	60
i=4	15	20	35	40	55	60
i=5	15	20	35	40	55	65

	j=1	j=2	j=3	j=4	j=5	j=6
i=0	0	0	0	0	0	0
i=1	0	0	25	25	25	25
i=2	0	20	25	25	45	45
i=3	15	20	35	40	45	60
i=4	15	20	35	40	55	60
i=5	15	20	35	40	55	65

算法分析与设计2：贪心、动规、分支限界、NP完备性理论

一、贪心

1.1 埃及分数

1.2 活动选择问题

1.3 背包问题

1.4 最佳合并模式算法(Optimal Merge Patterns)

1.4.1 算法

1.4.2 应用：哈夫曼编码

1.5 最小生成树(MST)

Prim算法

Kruskal算法

1.6 最小环基问题

1.7 旅行商问题

1.8 二部图的着色

二、动态规划

2.1 动态规划基本问题

2.2 0/1背包

2.2.1 公式推导与笔算

2.2.2 代码与优化

2.3 矩阵连乘问题

2.4 最长公共子序列问题(LCS问题)

2.4.1 公式推导与笔算

2.4.2 代码实现

2.5 最长上升子序列问题(LIS问题)

2.6 最短编辑距离

2.7 最大子段和问题

三、分支限界

3.1 分支搜索

3.2 分支限界法基本思想

3.2.1 概述

3.2.2 回溯法与分支限界法的比较

3.3 结点成本函数

3.4 0/1背包问题

3.5 多段图的最短路径问题

四、NP完备性理论

4.1 计算模型

4.2 几类问题

2.4 最长公共子序列问题(`LCS`问题)

2.5 最长上升子序列问题(`LIS`问题)

	j=1	j=2	j=3	j=4	j=5	j=6
i=0	0	0	0	0	0	0
i=1	0	0	25	25	25	25
i=2	0	20	25	25	45	45
i=3	15	20	35	40	45	60
i=4	15	20	35	40	55	60
i=5	15	20	35	40	55	65