国科大 计算机算法与分析 陈玉福
（了解）这种表示拓展答案，方便理解，但是在原考试题目中没有
背包，矩阵（要动手算，有熟练度和好的计算能力，最好带计算机）打破对称，n皇后，傅里叶变换···
这是整理的历年真题，当然有剩下的没整理题目（考频低），考的除了打破对称都包含了，但是没带计算器加复习时间太少，导致成绩一般
祝你好运！！！！！
——届沈计所学生 Sen.W
简答题
贪心算法设计的关键是什么？应该注意哪些问题？动态规划算法依据什么原理？设计算法主要有那几步，需要注意什么？关键：贪心策略的选择。
问题：
贪心算法的每一步决策都是局部最优，但不一定是整体最优解
选择的贪心策略必须具备无后效性，即某个状态以后的变化只与当前状态有关，而与以前经历的状态无关。
贪心算法和动态规划算法有什么共同点和区别？它们都有那些优势和劣势？动态规划理论依据：
动态规划是处理分段过程最优化的基本方法。基于最优性原则：无论初始决策和初始状态是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列 。最优子结构性质和子问题重叠性质是计算模型采用动态规划算法求解的两个基本要素。
基本要素：
最优子结构性质：如果问题的最优解所包含的子问题的解也是最优的，即该问题满足最优化原理
子问题重叠性质：每一个子问题只计算一次，将其解保存在一个表格中。不同的子问题个数随着输入问题的规模呈多项式增长，重复子问题求解是只需要搜索表格，时间复杂度是常数级的
注意问题：要按照动态规划的求解步骤去做（可以只背tips）
分析最优解的结构：选定要解决问题的一个具有最优子结构性质的计算模型建立递推关系式：关于目标值最优值的递推计算公式设计求最优值的迭代算法：利用子问题重叠的性质并在计算过程中记录一些信息用回溯方法给出最优解：利用计算最优值过程中记录的信息追溯最优解
回溯法和分支限界法有何异同？概述算法原理和提高算法效率的关键？共同点：
都是一种递推算法都是分解成子问题来求解都需要具有最优子结构
区别：
动态规划算法利用子问题重叠性质，将最优值的计算过程信息进行保留，极大的降低了重复计算。
贪心算法的每一步决策都是局部最优，但不一定是整体最优解
贪心算法不能保证结果是最优解，但一般计算复杂度低
动态规划可以得到最优解，但是计算复杂度一般较高
什么是多项式时间算法？相同点：都是在解空间树中搜索问题的可行解或最优解，
不同点：
回溯法一般用于求问题的一个可行解，而分枝限界可以用于求出问题的所有可行解
搜索的方式不同
回溯法：
概述：采用深度优先的方式，直到达到问题的一个可行解，或经判断沿此路径不会达到问题的可行解或最优解时，停止向前搜索，并沿原路返回到该路径上最后一个还可扩展的节点。然后，从该节点出发朝新的方向纵深搜索。然后，从该节点出发继续进行深度搜索。（了解）提高算法效率的关键：利用约束函数和限界函数避免无效搜索
分枝限界法：
概述：：采用的是宽度优先的方式，它将活节点存放在一个特殊的表中，其策略是，在扩展节点处，首先生成其所有的儿子节点，将那些导致不可行解或导致非最优解的儿子节点舍弃，其余儿子节点加入活节点表中，然后，从活节点中取出一个节点作为当前扩展节点，重复上述节点中扩展过程。（了解）提高算法效率的关键：利用约束函数和限界函数以及优先级函数避免无效搜索
多项式时间确定性算法与多项式时间非确定性算法的主要区别是什么？若存在一个常数C，使得对于所有n>=0，都有|f(n)| <= C*|g(n)|，则称函数f(n)是O(g(n))。时间复杂度是 O(p(n))的算法称为多项式时间算法，这里 p(n)是关于 n 的多项式。
一个优化问题如果已经找到了多项式时间算法，则称该问题为多项式时间可解问题，并将这类问题的集合记为 P，因此多项式时间可解问题就称为 P 类问题
eg：多项式时间算法：O(nlog(n))、O(n3)，指数时间算法：O(nlog(n))、O(n!)、O(2n)
（分治算法）设计一个计算两个n次多项式相乘的分治算法，使其时间复杂度低于O（n2）。只描述算法原理，并给出算法时间的复杂度分析（18分）（两次）一个算法存在确定性图灵机可计算的多项式时间算法，就将其算法归入 P 类
一个算法存在非确定性图灵机可计算的多项式时间算法，就将其归入 NP 类
最近点对问题使用分治法解决的时间复杂度为：𝑇(𝑛)=𝑂(𝑛𝑙𝑜𝑔𝑛)简述分治法和动态规划法的基本思想和异同利用快速傅里叶变换计算两个高次多项式乘积：
采用傅里叶变换计算出 f(x)，g(x) 在ω\omegaωj = e2 π\piπij / N处的值f(ω\omegaωj )，g(ω\omegaωj )，j = 0，1，···，N-1，这步需要O(N*logN)的计算量
构造N个数据A = [f(ω\omegaω0 )g(ω\omegaω0 )，f(ω\omegaω1 )g(ω\omegaω1 )，···，f(ω\omegaωN-1 )g(ω\omegaωN-1 )]，实际上是乘积多项式a(x)=f(x)g(x)在
ω\omegaωj = e2 π\piπij / N，j = 0，1，···，N-1处的值，需要O(N)的计算量
利用傅里叶变换的逆变换求出乘积多项式的系数ak，k = 0，1，···，N-1，这需要执行一次快速傅里叶变换即可，但ω\omegaωj = e2 π\piπi / N，这需要O(N*logN)的计算量
综上，算法复杂度为T(N) = O(NlogN)
写出下列复杂性函数的偏序关系（即按照复杂性从低到高排序）分治法：
将一个问题分解为相互独立且与原问题解法相同的子问题，然后将子问题的解合并得到原问题的解
动态规划法：
将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
相同点
都将待求解的问题分解成若干子问题，先求解子问题，然后再从这些子问题中获得原问题的解
不同点
动态规划法分解得到的子问题往往不是相互独立的，分治法求解的子问题往往是相互独立的
旅行家要旅行n个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路径最短，证明该问题满足最优性原理常见时间复杂度排序：常对幂指阶
O(1) < O(logN) < O(n) < O(NlogN) < O(n2) < O(2n) < O(n!) < O(nn)
陈述算法在最坏时间下的时间复杂度和平均时间复杂度，这两种评估算法复杂性的方法各自有什么意义？反证法：
设路线（L1, L2, ···, Ln）是最短路径，则（ L2, ···, Ln）是其子问题的最短路径，如果不是，设（ Y2, ···, Yn）是该子问题的最短路径，则说明（L1, Y2, ···, Yn）是最短路径，与题设矛盾，所以旅行家问题满足最优性原理
在对算法进行复杂性分析时，时间复杂度用什么量反映的？其间做了什么假设？渐近复杂性指什么?强调渐进复杂性的意义是什么？最坏时间复杂度
最坏情况下的时间复杂度称为最坏时间复杂度，一般讨论的时间复杂度均是最坏时间复杂度。最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，即任何情况下的最长运行时间
平均时间复杂度
所有可能的输入实例均以同等概率出现的情况下，即算法的期望运行时间
程序中关键步骤的操作计数假定每种基本操作所用时间都是一个基本单位设 T(n) 是算法A的复杂性函数。如果存在函数T~(n)\widetilde{T}(n)T(n),使得当 n→∞n\rightarrow\inftyn→∞ 时，有(T(n)−T~(n))/T(n)→∞(T(n) - \widetilde{T}(n))/T(n) \rightarrow \infty(T(n)−T(n))/T(n)→∞，称T~(n)\widetilde{T}(n)T(n)是算法A当 n→∞n\rightarrow\inftyn→∞的渐近复杂性。简化算法复杂性分析的方法和步骤，方便对各类算法进行分析和比较什么是并行算法？并行算法有那几种主要模型？衡量并行算法优劣主要用那几个指标？
在连通无向图的宽度优先搜索树和深度优先搜索树中，哪颗树的最长路径可能更长一些，说明理由。并行算法就是用多台处理机联合求解问题的方法和步骤，执行过程就是将给定的问题首先分解成若干个相互独立的子问题，然后使用多台计算机同时求解它，从而最终求得原问题的解。
模型：PRAM模型、BSP模型、LogP模型
指标：执行时间、工作负载、存储性能
简述打破对称的概念和方法深度，因为深度优先搜索是沿着顶点的邻接点一直搜索下去，直到当前被搜索的顶点不再有未被访问的邻点为止，且在搜索过程中形成的搜索树一定包含图中的最长路径。
概念：约束满足问题的求解方式有哪些对称性是约束满足问题的常见性质，对称性会导致搜索重复空间，从而降低搜索效率。特别是当问题无解的时候，完备算法需要搜索整个搜索空间，打破对称技术就至关重要。打破对称也称为消除同构。解决方法： 在问题建模时候尽量避免对称在问题求解开始时，通过添加约束来打破对称在求解过程中，动态的打破对称
归并排序算法和快速排序算法各自强调了那个方面？各自提高效率的策略是什么？系统搜索技术：是一种完备搜索技术，无论是否有解，当搜索完成时候都可以知道，也称为回溯搜索
不完备搜索技术：如果有解，可能给出结果，也可能不给出结果
归并排序 归并排序由分解和合并两个部分组成在元素较少时，可以直接使用插入排序进行排序使用链表结构，因为链表的移动比数组快 快速排序 对数据进行划分、比较和交换的排序在元素较少时，可以直接使用插入排序进行排序划分时，尽量接近中值
综合题
贪心算法
装箱问题：viv_ivi 是第i个箱子所占的体积，0<vi≤10 < v_i \le 10<vi≤1(i = 1,2,···, n ) ，箱子的容积都是 1。给出使用箱子最少的装箱方法 试用贪心算法给出一个装箱策略，并说明算法的时间复杂度 8分已知vi = 1 / (i +1) (i = 1,2,3,4,5,6,7,8)，按照你给出的算法描述装箱过程 6分试给出的贪心算法能够获得装箱问题的最优解吗？简单说明理由 2分
试用Prim算法求解下面无向赋权图的最小生成树，指出最小生成树及该树中各边被选中的先后顺序（15分）贪心策略：
把所有物品按体积降序排序，顺序取出一个物品，遍历所有已打开箱子，将该物品放入一个能放入且较早打开的箱子，若没有箱子能放下，则打开一个新箱子
时间复杂度：O(nlogn)
描述（这答案算的不真实？）
将v1装入第一个箱子，还剩1/2空间将v2装入第一个箱子，还剩1/6空间v3无法放入第一个箱子，打开第二个箱子并放入，第二个箱子剩余3/4v4无法放入第一个箱子，放入第二个箱子后剩余14/20v5装入第一个箱子，第一个箱子无剩余空间v6无法放入第一个箱子，放入第二个箱子后剩余57/140v7可以放入第二个箱子，剩余79/280v8可以放入第二个箱子，剩余431/2520，算法结束
基础知识
定理：设M=(S,I)M = (S,\mathfrak{I})M=(S,I)是赋权w的拟阵，则贪心算法Greedy（M，w）返回的子集A是M的最优独立集
证明有序对M=(S,I)M = (S,\mathfrak{I})M=(S,I)具有拟阵结构：
S是一个有限非空集合独立集的子集属于独立集，即B∈I,A⊆B⇒A∈IB \in \mathfrak{I}, A \subseteq B \Rightarrow A \in \mathfrak{I}B∈I,A⊆B⇒A∈I大独立集中存在一个元素并到小独立集中，小独立集仍为独立集
A,B∈I,∣A∣<∣B∣⇒∃x∈B/A,A∪{x}∈IA,B \in \mathfrak{I},|A|<|B| \Rightarrow \exists x \in B/ A,A \cup \{x\} \in \mathfrak{I}A,B∈I,∣A∣<∣B∣⇒∃x∈B/A,A∪{x}∈I
可以用贪心算法求出最优解的
带期限的单机作业调度问题Kruskal算法对于每一个无向连通赋权图产生一颗最优树
解答：设M=(S,I)M = (S,\mathfrak{I})M=(S,I)，S为所有物品集，I\mathfrak{I}I 为相容物品集构成的构成的子集族，？不会
从初始顶点开始，每次选与顶点集权值最小的顶点加入到顶点集，重复直到顶点
最小生成树：把用Prim算法处理后的图，整理一下一定能得到该图的最小生成树
试用Kruskal算法求解下面无向赋权图的最小生成树，指出最小生成树及该树中各边被选中的先后顺序（15分）
贪心策略：每次选取权值最小且不会形成圈的边加入树的边集
活动安排问题
贪心策略：在未安排的活动中挑选结束时间最早的活动安排
带期限的单机作业调度问题
贪心策略：尽量选取效益值大的作业优先安排
多机调度问题
贪心策略：未被安排的作业中需要时间最长，首先安排给能最早空闲下来的机器
使用贪心算法只能得到近似最优解
回溯算法
定和子集问题：给定有n个不同正整数的集合w=（w1，w2，… ,wn）和一个正数W，要求找出w的子集s，该子集中所有元素的和为W提高搜索效率的方法
约束函数：在扩展节点处剪去不满足约束的子树限界函数：剪去不能达到最优解的子树
回溯法的解题步骤：
确定问题的解空间确定易于搜索的解空间结构——状态空间树以深度优先的方式搜索状态空间树，并在搜索过程中用剪枝函数避免无效搜索
状态空间树是一颗完全二叉树（包含了所有的解），左1表示选取一个值，右0表示不选取该值
分支限界算法
设有n个物体和一个背包,物体 i 的重量为wi 价值为 pi ,背包的载荷为M, 若将物体i（1≤i≤n1\le i\le n1≤i≤n）装入背包，则有价值为pi 。 目标是找到一个方案, 使得能放入背包的物体总价值最高。（考两次） 用优先队列式分枝限界算法解如下0/1 背包问题：n = 4, p = (10, 10, 12, 18)，w = (2，4，6，9)，M = 15 画出状态空间树，并在各个节点处标出目标值的上界估值Pvu和下界估值Pvl（8分）指出状态空间树中各节点被选做当前拓展节点的顺序（标号）（6分）给出最优解相应的目标值（4分）节点的优先级计算函数算法流程
将每个物品按照 价值p / 重量v，即性价比最高的顺序从大到小排序状态空间树左1右0，1表示按照性价比顺序将物品放入，0表示不放入。上界 = 已装入背包的物品的总价值+ 剩余容量*(下一件物品价值/该物品重量)，即填满背包的最大价值下界按顺序计算最大的完整放入剩下物品的价值选择子节点中上界估值最大的作为拓展节点，不符合的进行剪枝 约束函数：当前节点背包重量 + 拓展节点物品重量 > 总背包重量，则将该拓展节点无法拓展限界函数：拓展节点上界≤\leq≤ 当前节点的下界，即该拓展节点不会获得更大收益，不进行拓展
拓展顺序124678，每次选择上界最大的子节点作为拓展节点，上界相同的，先选左儿子，6号节点左儿子不符合约束条件，右儿子是答案节点但是 小于等于 下界故舍弃
最优解为（1，1，0，1）
上界 = 已装入背包的物品的总价值+ 剩余容量*(下一件物品价值/该物品重量)
相似练习题：/article/1296236014334976000.htm
动态规划算法
矩阵连乘 20 分（考2次）已知矩阵 𝐴𝑖的大小为 𝑝𝑖-1∗𝑝𝑖，计算 𝐴1𝐴2𝐴3𝐴4𝐴5𝐴6。 𝑝0=30 𝑝1=35 𝑝2=15 𝑝3=5 𝑝4=10 𝑝5=20 𝑝6=25，用动态规划算法计算，写出矩阵加括弧次序。
某工业生产部门根据国家计划的安排, 拟将某种高效率的5台机器,分配给所属的3个工厂A,B,C,各工厂在获得这种机器后,可以为国家盈利的情况如表4-10所示。问:这5台机器如何分配给各工厂,才能使国家盈利最大?参考博客：/qq_32919451/article/details/80643118?spm=1001.2101.3001.6650.8&utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7Edefault-8.essearch_pc_relevant&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7Edefault-8.essearch_pc_relevant
+++
矩阵大小为：𝐴1：30X35 𝐴2：35X15 𝐴3：15X5 𝐴4：5X10 𝐴5：5X10 𝐴6：20*25
连乘矩阵：P=[30 35 15 5 10 20 25]
计算：(m[i][j] = min( m[i][k] + m[k+1][j] + 𝑝𝑖-1 ∗ 𝑝k ∗pj ))，m[i][j]表示第i个到第j个加括号后的矩阵连乘次数
每一个矩阵进行加括号处理：
m[1][1]=0 m[2][2]=0 m[3][3]=0 m[4][4]=0 m[5][5]=0 m[6][6]=0
每两个加括号：
m[1][2]= p0p1p2=15750
m[2][3]=p1p2p3=2625
m[3][4]=p2p3p4=750
m[4][5]=p3p4p5=1000
m[5][6]=p4p5p6=5000
每三个加括号（每三个有两种加括号方式要取最小的）
𝑚[1][3]=min{𝑚[1][1]+𝑚[2][3]+p0∗p1∗p3=7875𝑚[1][2]+𝑚[3][3]+p0∗p2∗p3=18000𝑚[1][3] = min\left\{ \begin{aligned} 𝑚[1][1] + 𝑚[2][3] + p_0*p_1*p_3 &= 7875\\ 𝑚[1][2] + 𝑚[3][3] + p_0*p_2*p_3 &= 18000 \end{aligned} \right. m[1][3]=min{m[1][1]+m[2][3]+p0∗p1∗p3m[1][2]+m[3][3]+p0∗p2∗p3=7875=18000 ，为 7875
𝑚[2][4]=min{𝑚[2][2]+𝑚[3][4]+p1∗p2∗p4=6000𝑚[2][3]+𝑚[4][4]+p1∗p3∗p4=4375𝑚[2][4] = min\left\{ \begin{aligned} 𝑚[2][2] + 𝑚[3][4] + p_1*p_2*p_4 &= 6000\\ 𝑚[2][3] + 𝑚[4][4] + p_1*p_3*p_4 &= 4375 \end{aligned} \right. m[2][4]=min{m[2][2]+m[3][4]+p1∗p2∗p4m[2][3]+m[4][4]+p1∗p3∗p4=6000=4375 ，为 4375
𝑚[3][5]=min{𝑚[3][3]+𝑚[4][5]+p2∗p3∗p5=2500𝑚[3][4]+𝑚[5][5]+p2∗p4∗p5=3750𝑚[3][5] = min\left\{ \begin{aligned} 𝑚[3][3] + 𝑚[4][5] + p_2*p_3*p_5 &= 2500\\ 𝑚[3][4] + 𝑚[5][5] + p_2*p_4*p_5 &= 3750 \end{aligned} \right. m[3][5]=min{m[3][3]+m[4][5]+p2∗p3∗p5m[3][4]+m[5][5]+p2∗p4∗p5=2500=3750 ，为 2500
𝑚[4][6]=min{𝑚[4][4]+𝑚[5][6]+p3∗p4∗p6=6250𝑚[4][5]+𝑚[6][6]+p3∗p5∗p6=3500𝑚[4][6] = min\left\{ \begin{aligned} 𝑚[4][4] + 𝑚[5][6] + p_3*p_4*p_6 &= 6250\\ 𝑚[4][5] + 𝑚[6][6] + p_3*p_5*p_6 &= 3500 \end{aligned} \right. m[4][6]=min{m[4][4]+m[5][6]+p3∗p4∗p6m[4][5]+m[6][6]+p3∗p5∗p6=6250=3500 ，为 3500
每四个加括号（每四个有三种加括号方式要取最小的）
𝑚[1][4]=min{𝑚[1][1]+𝑚[2][4]+p0∗p1∗p4=9625𝑚[1][2]+𝑚[3][4]+p0∗p2∗p4=21000m[1][3]+m[4][4]+p0∗p3∗p4=9375𝑚[1][4] = min\left\{ \begin{aligned} 𝑚[1][1] + 𝑚[2][4] + p_0*p_1*p_4 &= 9625\\ 𝑚[1][2] + 𝑚[3][4] + p_0*p_2*p_4 &= 21000\\ m[1][3] + m[4][4] + p_0*p_3*p_4 &= 9375 \end{aligned} \right. m[1][4]=min⎩⎪⎨⎪⎧m[1][1]+m[2][4]+p0∗p1∗p4m[1][2]+m[3][4]+p0∗p2∗p4m[1][3]+m[4][4]+p0∗p3∗p4=9625=21000=9375，为9375
𝑚[2][5]=min{𝑚[2][2]+𝑚[3][5]+p1∗p2∗p5=13000𝑚[2][3]+𝑚[4][5]+p1∗p3∗p5=7125m[2][4]+m[5][5]+p1∗p4∗p5=11375𝑚[2][5] = min\left\{ \begin{aligned} 𝑚[2][2] + 𝑚[3][5] + p_1*p_2*p_5 &= 13000\\ 𝑚[2][3] + 𝑚[4][5] + p_1*p_3*p_5 &= 7125\\ m[2][4] + m[5][5] + p_1*p_4*p_5 &= 11375 \end{aligned} \right. m[2][5]=min⎩⎪⎨⎪⎧m[2][2]+m[3][5]+p1∗p2∗p5m[2][3]+m[4][5]+p1∗p3∗p5m[2][4]+m[5][5]+p1∗p4∗p5=13000=7125=11375，为7125
𝑚[3][6]=min{𝑚[3][3]+𝑚[4][6]+p2∗p3∗p6=5375𝑚[3][4]+𝑚[5][6]+p2∗p4∗p6=9500m[3][5]+m[6][6]+p2∗p5∗p6=10000𝑚[3][6] = min\left\{ \begin{aligned} 𝑚[3][3] + 𝑚[4][6] + p_2*p_3*p_6 &= 5375\\ 𝑚[3][4] + 𝑚[5][6] + p_2*p_4*p_6 &= 9500\\ m[3][5] + m[6][6] + p_2*p_5*p_6 &= 10000 \end{aligned} \right. m[3][6]=min⎩⎪⎨⎪⎧m[3][3]+m[4][6]+p2∗p3∗p6m[3][4]+m[5][6]+p2∗p4∗p6m[3][5]+m[6][6]+p2∗p5∗p6=5375=9500=10000，为5375
每五个加括号（每五个有四种加括号方式要取最小的）
𝑚[1][5] = 11875
m[2][6]=10500
每六个加括号（每五个有五种加括号方式要取最小的）
𝑚[1][6]=min{𝑚[1][1]+𝑚[2][6]+p0∗p1∗p6=36750𝑚[1][2]+𝑚[3][6]+p0∗p2∗p6=21125𝑚[1][3]+𝑚[4][6]+p0∗p3∗p6=15125𝑚[1][4]+𝑚[5][6]+p0∗p4∗p6=21875𝑚[1][5]+𝑚[6][6]+p0∗p5∗p6=26875𝑚[1][6] = min\left\{ \begin{aligned} 𝑚[1][1] + 𝑚[2][6] + p_0*p_1*p_6 &= 36750\\ 𝑚[1][2] + 𝑚[3][6] + p_0*p_2*p_6 &= 21125\\ 𝑚[1][3] + 𝑚[4][6] + p_0*p_3*p_6 &= 15125\\ 𝑚[1][4] + 𝑚[5][6] + p_0*p_4*p_6 &= 21875\\ 𝑚[1][5] + 𝑚[6][6] + p_0*p_5*p_6 &= 26875\\ \end{aligned} \right. m[1][6]=min⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧m[1][1]+m[2][6]+p0∗p1∗p6m[1][2]+m[3][6]+p0∗p2∗p6m[1][3]+m[4][6]+p0∗p3∗p6m[1][4]+m[5][6]+p0∗p4∗p6m[1][5]+m[6][6]+p0∗p5∗p6=36750=21125=15125=21875=26875 ，为 15125
填入最小值数组（将上面每种情况斜着填） 括号分隔位置矩阵S（斜着填入对应m[i][j] = min( m[i][k] + m[k+1][j] + 𝑝𝑖-1 ∗ 𝑝k ∗pj )中取最小值的k）
答案（A1（A2A3））（（A4A5）A6）
括号看斜第三排以及后面对应的值k，表示k，k+1到之间加括号
递推关系：
𝑚[i][j]={0i=jmin{m[i][k]+m[k+1][j]+p[i−1]∗p[k]∗p[j]}i<j𝑚[i][j] = \left\{ \begin{array}{l} 0&i = j \\ min\{m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]\} & i<j \end{array} \right. m[i][j]={0min{m[i][k]+m[k+1][j]+p[i−1]∗p[k]∗p[j]}i=ji<j
用动态规划算法解多段图问题，即求从源点s 到目标点t 的最短路径 说明多段图问题具有最优子结构性质；写出多段图问题最优值的递推公式；给出下图问题的一个最优解并写出基本计算步骤。解：采用动态规划算法，先求出将5台机器分配给A,B工厂时产生的最大盈利情况，再将C加入，求出5台机器在A,B,C工厂分配时产生的最大盈利的情况，即为该问题的解。
设N为分配机器的台数
只考虑A和B：
N = 0：A和B均无分配机器，利益P为0
N = 1：P = max{ A(1)+B(0), A(0)+B(1) }= {3，5} = 5
N = 2：P = max{ A(2)+B(0), A(0)+B(2) , A(1)+B(1) } = {7，10，8} = 10
N = 3：P = max{ A(3)+B(0), A(0)+B(3) , A(2)+B(1)，A(1)+B(2)} = {9，11，12，13} = 13
N = 4：P = max{ A(4)+B(0), A(0)+B(4) , A(3)+B(1)，A(1)+B(3)，A(2)+B(2)} = {12，11，14，14，17} = 17
N = 5：P = max{ A(5)+B(0), A(0)+B(5) , A(4)+B(1)，A(1)+B(4) , A(3)+B(2)，A(2)+B(3)}
= {13，11，17，14，19，18} = 19
考虑C和AB：（将AB实质是上面计算的额定机器数的max，即用到前面计算的公共子问题的最优解）
N = 0：C和AB均无分配机器，利益P为0
N = 1：P = max{ C(1)+AB(0), C(0)+AB(1) }= {4，5} = 5
N = 2：P = max{ C(2)+AB(0), C(0)+AB(2), C(1)+AB(1) } = {6，10，9} = 10
N = 3：P = max{ C(3)+AB(0), C(0)+AB(3), C(2)+AB(1), C(1)+AB(2)} = {11，13，11，14} = 14
N = 4：P = max{ C(4)+AB(0), C(0)+AB(4), C(3)+AB(1), C(1)+AB(3), C(2)+AB(2)} = {12，17，16，17，16} = 17
N = 5：P = max{ C(5)+AB(0), C(0)+AB(5), C(4)+AB(1), C(1)+AB(4), C(2)+AB(3), C(3)+AB(2)}
= {12，19，17，21，19，21} = 21
最大盈利P为21，ABC分配机器的数量是023
反证法：设一个多段图有且仅有一个起点和一个终点 。设路线（L1, L2, ···, Ln）是最短路径，则（ L2, ···, Ln）是其子问题的最短路径，如果不是，设（ Y2, ···, Yn）是该子问题的最短路径，则说明（L1, Y2, ···, Yn）是最短路径，与题设矛盾，所以多段图满足最优子结构最优值递推关系式：最优二叉搜索树COST(i,j)=minl∈Vi+1,(j,l)∈E{c(j,l)+COST(i+1,l)}COST(i,j) = \min\limits_{l\in V_{i+1},(j,l)\in E}\{c(j,l) + COST(i+1,l)\}COST(i,j)=l∈Vi+1,(j,l)∈Emin{c(j,l)+COST(i+1,l)}证明：
/video/BV16f4y1h7P7?from=search&seid=7046006546979166438&spm_id_from=333.337.0.0
CuvC_{\mathsf{uv}}Cuv表示顶点uv间边的权值，d(s, t)表示从节点s到节点t间的最短路径（假设的后面会求出来）
自顶向下分解
V1到V5
d(1, 12) = min{C12C_{\mathsf{12}}C12+d(2, 12)，C13C_{\mathsf{13}}C13+d(3, 12)，C14C_{\mathsf{14}}C14+d(4, 12)，C15C_{\mathsf{15}}C15+d(5, 12)}V2到V5
d(2, 12) = min{C26C_{\mathsf{26}}C26+d(6, 12)，C27C_{\mathsf{27}}C27+d(7, 12)，C28C_{\mathsf{28}}C28+d(8, 12)}
d(3, 12) = min{C36C_{\mathsf{36}}C36+d(6, 12)，C37C_{\mathsf{37}}C37+d(7, 12)}
d(4, 12) = min{C48C_{\mathsf{48}}C48+d(8, 12)}
d(5, 12) = min{C57C_{\mathsf{57}}C57+d(7, 12)，C58C_{\mathsf{58}}C58+d(8, 12)}V3到V5
d(6, 12) = min{C69C_{\mathsf{69}}C69+d(9, 12)，C6.10C_{\mathsf{6.10}}C6.10+d(10, 12)}
d(7, 12) = min{C79C_{\mathsf{79}}C79+d(9, 12)，C7.10C_{\mathsf{7.10}}C7.10+d(10, 12)}
d(8, 12) = min{C8.10C_{\mathsf{8.10}}C8.10+d(10, 12)，C8.11C_{\mathsf{8.11}}C8.11+d(11, 12)}V4到V5
d(9, 12) = C9.12C_{\mathsf{9.12}}C9.12 = 4
d(10, 12) = C10.12C_{\mathsf{10.12}}C10.12 = 2
d(11, 12) = C11.12C_{\mathsf{11.12}}C11.12 = 5
自底向上求解
V4到V5
d(9, 12) = C9.12C_{\mathsf{9.12}}C9.12 = 4
d(10, 12) = C10.12C_{\mathsf{10.12}}C10.12 = 2
d(11, 12) = C11.12C_{\mathsf{11.12}}C11.12 = 5V3到V5
d(6, 12) = min{C69C_{\mathsf{69}}C69+d(9, 12)，C6.10C_{\mathsf{6.10}}C6.10+d(10, 12)} = {6+4，5+2} = 7
d(7, 12) = min{C79C_{\mathsf{79}}C79+d(9, 12)，C7.10C_{\mathsf{7.10}}C7.10+d(10, 12)} = {4+4，3+2} = 5
d(8, 12) = min{C8.10C_{\mathsf{8.10}}C8.10+d(10, 12)，C8.11C_{\mathsf{8.11}}C8.11+d(11, 12)} = {5+2，6+5} = 7V2到V5
d(2, 12) = min{C26C_{\mathsf{26}}C26+d(6, 12)，C27C_{\mathsf{27}}C27+d(7, 12)，C28C_{\mathsf{28}}C28+d(8, 12)} = {4+7，2+5，1+7} = 7
d(3, 12) = min{C36C_{\mathsf{36}}C36+d(6, 12)，C37C_{\mathsf{37}}C37+d(7, 12)} = {2+7，7+5} = 9
d(4, 12) = min{C48C_{\mathsf{48}}C48+d(8, 12)} = {11+7} = 18
d(5, 12) = min{C57C_{\mathsf{57}}C57+d(7, 12)，C58C_{\mathsf{58}}C58+d(8, 12)} = {11+5，8+7} = 15V1到V5
d(1, 12) = min{C12C_{\mathsf{12}}C12+d(2, 12)，C13C_{\mathsf{13}}C13+d(3, 12)，C14C_{\mathsf{14}}C14+d(4, 12)，C15C_{\mathsf{15}}C15+d(5, 12)}
= {9+7，7+9，3+18，2+15} = 16
回溯可知最优路径是1-2-7-10-12 和1-3-6-10-12（逆序找每次计算得到最小值的路径）
已知一组数在满足，且被搜索对象的概率分布是：
a0 = 0.1 a1 = 0.01 a2 = 0.02 a3 = 0.04 a4 = 0.03 a5 = 0.2
b1 = 0.15 b2 = 0.05 b3 = 0.075 b4 = 0.25 b5 = 0.075 证明二叉搜索满足最优子结构最优值的递推公式
基础知识：
二叉搜索树利用二叉树的内节点存储元素，叶子节点表示查找失败，树内元素大于左子树的任一个元素，小于右子树的任一个元素。其形式化定义如下：给定一个n个不同关键字已排序的序列K=<k1,k2,…,kn>(因此k1<k2<…<kn)，我们希望用这些关键字构造一棵二叉搜索树。对每个关键字ki，都有一个概率pi表示其搜索频率。有些要搜索的值可能不在K中，因此我们还与n+1个“伪关键字”d0,d1,d2…dn表示不在K中的值（对于二叉树，叶子节点 = 内部节点 + 1，自己画个二叉树图看看）。d0表示所有小于k1的值，dn表示所有大于kn的值，对i=1,2,…,n-1，伪关键字di表示所有在ki和ki+1之间的值。对每个伪关键字di，也都有一个概率pi表示对应的搜索频率。
下图显示了对一个n=5个关键字的集合构造的两颗二叉搜索树。每个关键字ki是一个内部结点，而每个伪关键字di是一个叶结点。每次搜索要么成功(找到某个关键字ki)要么失败(找到某个伪关键字di)
如果一棵最优二叉搜索树T有一棵包含关键字k(i),…,k(j)的子树T’，那么T’必然是包含关键字k(i),…,k(j)和伪关键字d(i-1),…,d(j)的子问题的最优解。使用剪贴法证明，如果存在子树T’‘，其期望搜索代价比T’低，那么我们将T’从T中删除，将T’'粘贴到相应的位置，从而得到一颗期望搜索代价低于T的二叉搜索树N，N与T为最优的假设矛盾。没时间啦，自己研究一下吧。/c18219227162/article/details/50429597?spm=1001.2101.3001.6650.2&utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7Edefault-2.fixedcolumn&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7Edefault-2.fixedcolumn
分治法
试用归并排序算法对下列实例排序，写出算法执行过程。A= {48，12，61，3，5，19，32，7}快速排序基础思想：
将待排序数组A[n]，划分成两部分 [0 : n/2] , [n/2+1,n-1]（奇数个的话，前一组多一个）左区间排序，右区间排序最后把左区间和右区间用一次归并操作合并成有序的区间
执行过程
基本步骤：
i指向基准数据（通常为第一个），基准数据用temp变量存储j指针 从后向前找比基准数小的，交换i指针 从前向后找比基准数大的，交换如果两个指针相等，则该位置就是基准数位置（这里的指针实质是数组下标）由基准数据分成的两部分再重复以上4步
NPC问题
NP 完全问题的证明步骤用SAT模型去证明分团问题（Clique）是NPC基础定义：
P类问题:(polynominal) 存在多项式时间算法的问题，即在多项式时间内可解的问题；
例如：冒泡排序、快速排序等问题；
NP类问题:(Nondeterministic polynominal) 能在多项式时间内验证出一个正确解的问题，也就是说这个问题不一定在多项式时间内可解，但可以在多项式时间内验证；
例如：大数分解问题，比如180576这个数让你拆成两个数相乘，必须是三位乘以三位的，可能很久都解不出来（如果是一个很大很大的数的话），但是我告诉你这是352*513得到的，那么很简单就能在多项式时间内验证是否正确，这就是NP问题；
NPC类问题（Nondeterminism Polynomial complete）：存在这样一个NP问题，所有的NP问题都可以约化成它。
NP-Hard类问题（Nondeterminism Polynomial hard）：所有的NP问题都可以约化成它。
NPC问题一定是NP-hard问题，NP-hard问题不一定是NP问题
参考博客：/a12638915/article/details/105180347?spm=1001.2101.3001.6650.3&utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7Edefault-3.no_search_link&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7Edefault-3.no_search_link
原理：若存在一个问题L 为NPC，如果L能够规约到一个NP问题K，则问题K可证明为NPC问题
+++
证明新问题L是NPC（必考）
证明L ∈\in∈ NP（该问题的答案可以在多项式时间内验证是否符合条件，即可证明问题为NP问题）选取一个已知的NPC问题K两种证明方法 规约法：L可以规约到K 构造一个从已知NPC问题K到该问题L的变换 f\mathcal{f}f（可满足性：L有解⇔\Leftrightarrow⇔K有解）证明该变换 f\mathcal{f}f 是一个多项式变换（证明构造的等价NPC模型可以在多项式时间内求解） 限制法：证明L的一个特例是K，K是NPC，所以L也是NPC规约的理解
变换就是寻找已知的NPC问题满足要证明的NPC问题的约束关系的特例（通俗的认为，即要证明的问题比已知的NPC问题还难，则要证明的问题至少是NPC问题）特例 = 对象+规则 = 已知的NPC问题 +要证明的NPC问题的约束关系（将对象用这个规则进行表示）背诵理解基本的用数学语言表示的NPC问题，理解用数学语言表示的要证明的问题，进行等价的多项式变换
+++
常见问题的规约方向，上面的NPC可规约到下面来证明下面问题是NPC
布尔可满足性问题（SAT）
划分问题
01背包问题 整数规划问题
分团问题（Clique）
最小顶点覆盖集问题独立集问题 集合覆盖问题
3SAT问题
图着色问题分团覆盖问题
参加博客
/p/ddae993cc065
/golden1314521/article/details/51470999?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522163931149916780271925644%2522%252C%2522scm%2522%253A%25220713.130102334.pc%255Fall.%2522%257D&request_id=163931149916780271925644&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2allfirst_rank_ecpm_v1~rank_v31_ecpm-3-51470999.pc_search_result_cache&utm_term=%E8%AF%B4%E6%98%8E%E4%B8%80%E4%B8%AANPC%E9%97%AE%E9%A2%98%E6%98%AFNP%E9%9A%BE%E9%97%AE%E9%A2%98&spm=1018.2226.3001.4187
判定形式的整数规划问题的描述如下： 给定一个m * n的矩阵A和一个m元向量b，是否存在一个n元整数向量x，使得Ax <= b 证明判定形式的整数规划问题是NP完全的（不能使用01整数规划问题做规约）（9分）优化形式的整数规划问题除了以上定义外，还有一个n元向量c，优化目标为maximize cTx，说明优化形式的整数规划问题为何是NP难的（2分）求优化形式的整数规划问题的绝对近似解也是NP难问题吗？说明理由。（3分）分团问题是找出一个大小为k的clique，其中clique是一个两两相连的一个点集
任意挑出k个点，我们可以在多项式时间内判断出这k个点是不是clique(两两相连)，所以这个问题属于NP
选取已知的NPC问题SAT问题进行规约
现证明SAT问题可以规约到分团问题
现在将图进行任意布尔值的编码，但是相邻节点必须可以同时为真
编完码后，将其写成SAT的合取范式模型，这里因为k=3，所以合取范式里的析取范式个数为3，搭配是任意的：(x1∨x2)∧x1ˉ∧(x2ˉ∨x3)({x_1}\vee{x_2})\land\bar{x_1}\land(\bar{x_2}\vee{x_3})(x1∨x2)∧x1ˉ∧(x2ˉ∨x3)，构造合取范式为真到k=3的clique有解的映射 若x1ˉ\bar{x_1}x1ˉ是单独的必须为真，则x1{x_1}x1为假，则x2{x_2}x2为真，则x3{x_3}x3为真，即在多项式时间内可证明NPC的SAT问题构造的映射为真，所以分团问题为NPC问题
假定已知“无向图的Hamilton回路”问题是NPC问题，证明“旅行商判定问题”也是NPC问题证明
证明该问题是NP问题：给定x带入后易判断Ax是否小于b，即在多项式时间内可以验证选定一个已知的NPC问题——0/1 背包判定问题进行规约先证明0/1 背包判定问题可以归约到整数规划问题 将矩阵A和b的各行取相同值a11，a12，… a1n和b1，则问题变为：判定是否存在X，a11x1+a12x2+…a1nxn ≤ b1，判定 cTx问题 这就是 0/1 背包判定问题。0/1背包判定问题是NPC，所以这个特殊整数规划问题也是NPC问题，从而整数规划问题是NPC 问题。
如果一个问题是NPC问题，则其最优化一般是NP-Hard问题
证明相遇集问题是 NP 完全问题 。（提示用顶点覆盖问题规约或 3sat）（ 15 分）无向图的Hamilton回路问题：从起点开始一次性经过所有节点所形成的回路
旅行商问题（Traveling Salesman Problem, TSP）有两个版本：
求最优解的对称旅行商问题：在一个图里，除了起始点以外不重复地遍历所有节点构成一条闭合回路，问该回路的最短路径是多少？
对称旅行商问题：需要与所有环游比较才能得到最短路径，是指数级的，即无法在多项式时间内验证答案的，所以问题不是NP问题，因此也不是NPC问题，而是NP-Hard问题判定性的旅行商判定问题：在一个图里，除了起始点以外不重复地遍历所有节点构成一条闭合回路，问路径长度小于等于某个值的这样的回路是否存在？（这个是判定性问题，称为旅行商判定问题）
旅行商判定问题：可以确定型图灵机在多项式时间内验证答案，所以问题2是NP问题，同时这个问题可以从哈密顿问题归约而来，而哈密顿问题是NPC问题，所以它是NPC问题。
对称旅行商问题证明:
对称旅行商问题不是NP问题，因为对其解的任一猜想，要检查它是否是最优的，需要同其他所有环游进行比较，这样的环游有指数个，因而无法在多项式时间内完成
使用已知的NPC问题，图的Hamilton回路问题进行规约
已知无向图G = （V，E），|V| = n，构造其对应的旅行商问题。
$\begin{equation}
d_{ij}=
\begin{cases}
1& \text{ $ if(vi,vj)\in E $ } \
2& \text{ $ otherwise $ }
\end{cases}
\end{equation}$
显然这一变换可以在多项式时间内完成，即对称旅行商问题是NP-Hard问题
旅行商判定问题证明:
给定一个旅行商的路径，可以在多项式时间内判断出该路径长度是否符合要求，即该问题属于NP问题
将NPC的无向图的 Hamilton 问题规约到旅行商的判定问题
已知无向图 G=(V,E)，|V|=n，构造对应的旅行商问题如下：
$\begin{equation}
d_{ij}=
\begin{cases}
1& \text{ $ if(vi,vj)\in E $ } \
2& \text{ $ otherwise $ }
\end{cases}
\end{equation}$
显然，这一变换可以在多项式时间内完成，而且，图G有Hamilton回路的充分必要条件是上述构建的旅行商问题有解，且对应的路程长度为n。因为，若G不含Hamilton回路，则这时的旅行商问题的解对应的路程长度至少为n+1（n-1+2）。因为已知图的Hamilton回路问题是NPC的，且上述问题为多项式变换，所以旅行商问题是NPC的。
基础知识：
顶点覆盖问题
给定一个图G( V, E )和一个正整数K≤∣V∣K \le |V|K≤∣V∣，是否存在一个顶点子集$V^{\prime} \subseteq V ，，， |V^{\prime}| \le K，使得对于每一条边，使得对于每一条边，使得对于每一条边(v1,v2)中的至少有一个顶点在中的至少有一个顶点在中的至少有一个顶点在V^{\prime}$中，即图的子顶点集关联的边可以覆盖整个图的边
相遇集问题
给定集合S的一个子集族C和一个正整数K，S是否包含子集S′S^{\prime}S′，∣S′∣≤K|S^{\prime}| \le K∣S′∣≤K，使得S′S^{\prime}S′与C中任何一个子集交均非空。（|S|表示S集合中顶点的个数）
证明：
证明相遇集问题是NP的。给定C,S′⊆SC,S^{\prime} \subseteq SC,S′⊆S，验证∣S′∣≤K|S^{\prime}| \le K∣S′∣≤K，$C \cap S^{\prime} $非空，可在多项式时间内验证将已知的NPC顶点覆盖问题规约到 ∣C∣=2|C| = 2∣C∣=2 的相遇集问题上任给图G(V,E)，设E={(x1,y1),(x2,y2)…,(xm,ym)}E=\{(x_1,y_1),(x_2,y_2)…,(x_m,y_m)\}E={(x1,y1),(x2,y2)…,(xm,ym)} ,令S=VS=VS=V，C={(x1,y1),(x2,y2)…,(xm,ym)}C=\{(x_1,y_1),(x_2,y_2)…,(x_m,y_m)\}C={(x1,y1),(x2,y2)…,(xm,ym)}，那么，若G存在顶点覆盖V′V^{\prime}V′，|V′V^{\prime}V′|≤K，则V′V^{\prime}V′覆盖E的每条边的至少一个顶点，使得对于每一条边(v1,v2)(v1,v2)(v1,v2)中的至少有一个顶点在V′V^{\prime}V′中。取S′S^{\prime}S′=V′V^{\prime}V′，显然，S′S^{\prime}S′与C中任意子集(v1,v2)(v1,v2)(v1,v2)交集不空。反之，若存在相遇集S′S^{\prime}S′，则令S′S^{\prime}S′=V′V^{\prime}V′，由于S′S^{\prime}S′与C中子集交不空，则S′S^{\prime}S′必含有(v1,v2)(v1,v2)(v1,v2)之一，说明它是G的顶点覆盖。所以|c|=2的相遇集问题是NP难的，从而相遇集问题也是NP难的。相遇集问题∈NP，所以是NP完全问题。
证明0/1背包判定问题是NPC问题
独立集问题：对于给定的无向图G = （V，E）和正整数k（k >= |V|）,是否存在一个顶点集V的子集V ‘ ，|V ‘| = k,使得V ‘中的任何两个顶点在G中都不相邻。
最大独立集问题：再无向图G = （V，E）中寻找独立集V ‘ ，使得V ‘ 的顶点个数最多，即对G任何一个独立集V’‘ ，都有|V‘ | >= |V’‘ |
tips：V表示顶点，E表示边，|V|表示顶点集V中顶点的数量
请回答以下问题：
用3SAT做规约，证明独立集问题是NPC的（12分）最大独立集问题是NP难问题吗？说明理由（3分）
NP难问题的证明基础知识：
3SAT问题：给定一个有穷的布尔变量集合X = {x1，x2，···，xn}，其中布尔变量xi取值为0或1，另有一组子句C = {c1，c2，···，cm}，其中每个子句均为3个文字的析取范式，即ci = (xi∨xj∨xk)({x_i}\vee{x_j}\vee{x_k})(xi∨xj∨xk)，子句之间是合取范式，即C = (xi∧xj∧xk)({x_i}\land{x_j}\land{x_k})(xi∧xj∧xk)。求是否存在一组取值使得C为真，即任意ci 均为真
依靠下面两个原则进行文字值的推导
对于一个子句只要有一个文字为真，则该子句的值为真，即ci = (xi∨xj∨xk)({x_i}\vee{x_j}\vee{x_k})(xi∨xj∨xk)有一个x为真ci为真对于子句集，只要有一个子句为假，则整个子句集假，即C = (ci∧cj∧ck)({c_i}\land{c_j}\land{c_k})(ci∧cj∧ck)中x必须全为真，C才为真
理解角度：
举个例子：小红，小王，小江等n人想找个地方去做运动，他们觉得这个地方可能会有m种情况。为了尽量满足所有人的癖好，每个人都根据可能出现的情况提了一个包含3个需求的列表：小红想找个“有窗户”或者“有厕所”或者“没臭味”的地方，小王想找个“没窗户”或“有臭味”或“没厕所”的地方，小江想找个“有厕所”或“没臭味”或“没窗户”的地方。。。问，是否存在一个地方可以满足所有人的（至少一个）要求？
其中，每个人提的需求列表就是一个“子句”，比如小红提的 " ‘有窗户’或’有大床’或’没臭味’ " 就是一个“子句”。
需求列表中的每一项具体的需求都是一个“文字”，比如“有窗户”就是一个文字，“没臭味”也是一个文字。
需求的选项(可能出现的情况)就是“变量”，比如“窗户”就是一个变量，“厕所”是一个变量，“臭味”也是一个变量。
如果最后找到了一个“有窗户，没厕所，没臭味”的地方，那么“有窗户，没厕所，没臭味”就是变量的真值赋值。
所有人需求就是合取范式，如果“每个人的需求都有3项且至少要满足1项”就是“3合取范式”。
3SAT问题就是问 "是否存在"一个满足所有人需求的地方。
那么如何归约呢? 一个常用的方法就是构造，构造一个满足将要规约到的问题约束条件的3SAT实例，且该构造是多项式时间内可完成的
+++
（1）证明：
参考：/shulianghan/article/details/111244644
证明独立集是NP问题
设独立集的一个解的顶点集合为S，可以在多项式时间内验证该集合的顶点间是否有边相连，所以独立集问题是NP问题
选择已知的NPC问题——3SAT问题进行规约
现证明3SAT问题可以规约到独立集问题
对3SAT问题到独立集问题进行如下变换（两种变换，3SAT要求子句中的文字必须是三个）
布尔逻辑公式 是可满足的 , 当且仅当 , 无向图中有一个 k 独立集该变换加了3m个点，3m+k条边，所以是多项式时间内完成的
额外解释，非证明：
假设有一个3SAT的赋值，则对于每个Ci如果是zj使得Ci=1,则将z j加入顶点集合S,我们能够说S一定是个独立集，因为在每个点集Vi中只取了一个点，且冲突边的两个顶点中至多只有一个顶点被选到，所以是独立集。
假设再G中有一个大小为m的独立集，则一定是再每个三角形顶点中取一个，不然在一个三角形中取两个点则不是独立集。因此存在一个真值赋值。对于每个Vi，如果选择了zi，则zi = 1
3SAT的考察实例 C = (x1∨x2ˉ∨x3ˉ)∧(x1ˉ∨x2∨x3)∧(x1∨x2∨x3)({x_1}\vee\bar{x_2}\vee\bar{x_3})\land(\bar{x_1}\vee{x_2}\vee{x_3})\land({x_1}\vee{x_2}\vee{x_3})(x1∨x2ˉ∨x3ˉ)∧(x1ˉ∨x2∨x3)∧(x1∨x2∨x3) ，如何画图？
（2）证明
在同一个图中，最大团的补图就是最大独立集，寻找图的最大团是 NP 困难的，从而寻找图的最大独立集也是 NP 困难的
原理：若存在一个NPC问题可以在多项式时间内归约到问题L，则称问题L为NP-hard问题
取一个独立集的顶点数最多的实例，该实例可以在多项式时间内规约到最大独立集问题，所以最大独立集问题是NP-hard问题
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-1r1KyMsx-1641871571547)(/water_stop/blog-image/raw/master/img/IMG_4257(1219-120814)].JPG)
独立集证明。（10 分）
已知图 𝐺 = (𝑉,𝐸,𝐼) ，S⊆G，且 S 中不含图 G 的圈，则 S 是独立边集。 证明以下问题：
独立集的子集也是独立集。A, B 是独立集，已知 |A| < |B|，𝑒 ∈ B\A，证明 𝐴∪{𝑒}是独立集。
近似算法
绝对近似和相对近似绝对近似算法:对于问题的任何实例，均有∣F∗(I)−F(I)∣≤k|F^*(I) - F(I)| \le k∣F∗(I)−F(I)∣≤k，其中k为常数，F∗(I)F^*(I)F∗(I)为近似值，F(I)F(I)F(I)为最优值相对近似算法
对于问题的任何实例，均有∣(F∗(I)−F(I))/F∗(I)∣≤ε(n)|(F^*(I) - F(I))/F^*(I)| \le \varepsilon(n)∣(F∗(I)−F(I))/F∗(I)∣≤ε(n)，其中ε(n)\varepsilon(n)ε(n)是I规模n的函数（常为多项式）
CSP约束传播
AC-3求解5 皇后的弧一致性。（15 分）N皇后问题是指在一个N x N的棋盘上放置N个皇后，使得每一行、每一列以及每一斜线上不能有两个以上的皇后。令xi(1≤i≤N)表示第i列的皇后放的行号，则Di={1 … N}，约束条件在下面题目中。
第 i 列的皇后放置在第 𝑥𝑗行，写出 𝑥𝑗,𝑥k(𝑗≠𝑘)的约束条件。（ 3 分）
说明 5皇后的弧一致性的消减传播过程 ，给出 𝑥2,𝑥3,𝑥4,𝑥5的值域。
约束条件：
皇后不能在同一行 𝑥i ≠ 𝑥𝑗 皇后不能在同一列且约束范围 (0<i<j≤n)皇后不能在同一斜线上 | 𝑥i- 𝑥𝑗| ≠ |i-j|
解题基础
Di表示xi的值域，即第i列符合约束条件可以放置皇后的行
Q表示所有需要检查弧一致性的弧的集合（可放列的笛卡尔点对）顺序检查队列Q中点对的弧一致性：对弧（xi , xj ）检查xi顺序取其值域Di中的值时，遍历 xj 在其值域Dj 中是否有值满足约束条件，当Dj没有可以满足弧约束的时候，则将xi 值域中不满足的值删去，然后将与xi相关的弧加入到队列中（对Di所有值都要遍历做如上处理）求得Q中所有弧一致时的值域，要遍历该列的所有值域
证明
由题知
D2 = {4，5}，D3 = {1，3，5}，D4 = {1，3，4}，D5 = {1，3，4，5}
Q = { (x2 , x3)，(x3 , x2)，(x2 , x4)，(x4 , x2)，(x2 , x5)，(x5 , x2)，(x3 , x4)，(x4 , x3)，(x3 , x5)，
(x5 , x3)，(x4 , x5)，(x5 , x4) }依次检查Q可知，(x2 , x3)是弧一致的检查(x3 , x2)，不符合弧一致性，D3 = {1，3}，将(x2 , x3)加入Q检查{ (x2 , x4)，(x4 , x2)，(x2 , x5)，(x5 , x2)，(x3 , x4)，(x4 , x3)，(x3 , x5) }均符合弧一致性，此时，
Q = { (x5 , x3)，(x4 , x5)，(x5 , x4) ，(x2 , x3)}检查 (x5 , x3)，不符合弧一致性，D5 = {4，5}，将(x2 , x5)，(x3 , x5)加入Q检查 (x4 , x5)，不符合弧一致性，D4 = {1，3}，将(x2 , x4)，(x3 , x4)加入Q检查{ (x5 , x4) ，(x2 , x3) }均符合弧一致性，此时，Q = { (x2 , x5)，(x3 , x5)，(x2 , x4)，(x3 , x4) }检查 { (x2 , x5)，(x3 , x5)，(x2 , x4)，(x3 , x4) }均符合弧一致性最后值域为D2 = {4，5}，D3 = {1，3}，D4 = {1，3}，D5 = {4，5}
类似例题，如图所示。写出AC-3维护弧一致性的过程
重写证明：
写出值域D以及待检查队列Q，
D3 = {1，6}，D4 = {1，3}，D5 = {1，3，5}，D6 = {1，3，5，6}
Q = { (x3 , x4)，(x4 , x3)，(x3 , x5)，(x5 , x3)，(x3 , x6)，(x6 , x3)，(x4 , x5)，(x5 , x4)，(x4 , x6)，(x6 , x4)，
(x5 , x6)，(x6 , x5) }检查Q = { (x3 , x4)，(x4 , x3)，(x3 , x5)，(x5 , x3)，(x3 , x6)，(x6 , x3)，(x4 , x5)，(x5 , x4)，(x4 , x6)}均符合弧一致性，此时Q ={ (x6 , x4)，(x5 , x6)，(x6 , x5) }检查(x6 , x4)可知，D6 = {5，6}，将(x3 , x6)，(x4 , x6)添加到Q中（x6在后面的且不在Q的所有点对）检查(x5 , x6)可知，D5= {3}，将(x3 , x5)，(x4 , x5)添加到Q中检查(x6 , x5)，(x3 , x6)，(x4 , x6)可知，符合弧一致性检查(x3 , x5)可知，D3= {6}，将(x4 , x3)，(x5 , x3)，(x6 , x3)添加到Q中，
此时，Q = {(x4 , x5)，(x4 , x3)，(x5 , x3)，(x6 , x3)}检查(x4 , x5)可知，D4= {1}，将(x3 , x4)，(x5 , x43)，(x6 , x4)检查(x4 , x3)，(x5 , x3)可知，符合弧一致性检查(x6 , x3)可知，D6= {5}，将(x3 , x6)，(x4 , x6)，(x5 , x6)加入Q中检查(x3 , x4)，(x5 , x4)，(x6 , x4)，(x3 , x6)，(x4 , x6)，(x5 , x6)Q中剩下的弧均一致，所以值域为D3={6}，D4={1}，D5={3}，D6={5}
Crossword Puzzle是西方人所喜爱的一种填字游戏，方式是将表格的每个空白处填上一个字母，使得每一行，每一列的连续字母构成一个单词，Crossword Puzzle可建模为约束满足问题，现有如下图所示的一个Crossword Puzzle，令变量X1，X2，X3，X4，X5，分别代表第一行、第三列、第五列、第三行、第四行的单词（在图中标记在对应单词的第一个空格处），其中X1，X2，X3，X4，X5的值域分别为：
D1 = {hoses，laser，sheet，snail，steer}
D2 = D4 = {hike，aron，keet，earn，same}
D3 = {run，sun，let，yes，eat，len}
D5 = {no，be，us，it}
请写出约束传播对变量X1，X2，X3，X4，X5的值域的消减过程，以及满足弧一致性时，每个变量的值域（15分）
规则，将变量对应行列填入其值域内的单词，使得所有X均存在单词可以对表格进行完整填充证明 由题知，D已知用AC-4算法计算如下条件的问题Q = { (X1 , X2)，(X2 , X1)，(X1 , X3)，(X3 , X1)，(X1 , X4)，(X4 , X1)，(X1 , X5)，(X5 , X1)，(X2 , X3) (X3 , X2)，(X2 , X4)，(X4 , X2)，(X2 , X5)，(X5 , X2)，(X3 , X4)，(X4 , X3)，(X3 , X5) ，(X5 , X3)，
(X4 , X5)，(X5 , X4)}依次检查Q可知，(X1 , X2)是弧一致的（D1中的第三个字母，均有D2中的第一个字母可以令其成立）检查(X2 , X1)，不符合弧一致性，D2 = {aron，earn，same}，将(X1 , X2)加入Q检查(X1 , X3)，不符合弧一致性，D1 = {hoses，laser，snail，steer}，将(X2 , X1)加入Q检查(X3 , X1)，不符合弧一致性，D3 = {run，sun，let，len}，将(X1 , X3)加入Q检查{ (X1 , X4)，(X4 , X1)，(X1 , X5)，(X5 , X1)，(X2 , X3) (X3 , X2) }均满足弧一致性检查(X2 , X4)，不符合弧一致性，D2 = {earn}，将{(X3 , X2) 加入Q检查(X4 , X2)，不符合弧一致性，D4 = {aron}，将 (X1 , X4)，(X2 , X4) 入Q检查(X2 , X5)，符合弧一致性检查(X5 , X2)，不符合弧一致性，D5 = {no}，将{ (X1 , X5)，(X2 , X5) }加入Q检查(X3 , X4)，不符合弧一致性，D3 = {run，sun，len}，将{ (X2 , X3) }加入Q检查{(X4 , X3)，(X3 , X5) ，(X5 , X3)，(X4 , X5)，(X5 , X4)}，均符合弧一致性Q={(X1 , X2)，(X2 , X1)，(X1 , X3)， (X3 , X2)，(X1 , X4)，(X2 , X4)， (X1 , X5)，(X2 , X5)，(X2 , X3)}检查(X1 , X2)，不符合弧一致性，D1 = {steer}，将{ (X2 , X1)，(X3 , X1)， (X4 , X1)，(X5 , X1) }加入Q检查(X2 , X1)，符合弧一致性检查(X3 , X1)，不符合弧一致性，D3 = {run}，将{ (X4 , X3) ，(X5 , X3)}加入Q检查Q均符合最后值域为
D1 = {steer}
D2 = {earn}
D3 = {run}
D4 = {aron}
D5 = {no}
Z（2，5），X（2，5），Y（2，4），约束关系是: Z可整除X, Z可整除Y（整除：后面除以前面余数为0）
AC-4求解6皇后问题初始化sport数组存放支持变量（x，value）即x取值k的键值对队列
初始化counter数组（x，value）存放其在对应属性的支持键值对个数
将不符合约束条件的count数组放入待检查队列中，并删除z = 5的值并更新sport和counter数组
Q = { (z,5) }检查Q中键值对在sport中相关的键值对并将其加入Q，知s(z,5) 为<x,5>
Q = { (x,5) }检查s(x,5)，得到(z,5) 已删去，所以Q为空，算法完成
由题知 D3 = {1，6}，D4 = {1，3}，D5 = {1，3，5}，D6 = {1，3，5，6}初始化sport数组为初始化counter数组为检查counter中(X6，1) (X6，3)含0（不符合约束的值），则D6 = {5，6}，并将(X6，1) (X6，3)加入Q将(X6，1) 删除，则sport数组中 (X6，1)支持的 <x3,6>,<x5,3>,<x5,5> 对应在counter数组的X6列-1将(X6，3) 删除，则sport数组中 (X6，3)支持的 <x3,1>,<x5,5> 对应在counter数组的X6列-1(X5，5)在counter中含0，则D5 = {1，3}，并将(X5，5)加入Q将(X5，5) 删除，则sport数组中(X5，5)支持的 <x3,1>,<x3,6>,<x4,1>,<x4,3>,<x6,1>,<x6,3> 对应在counter数组的X6列-1，其中<x6,1>,<x6,3> 在counter数组中已经删除，所以不用管了。。。。。。真题，X Y Z T 四个变量的值域都是 {1 2 3}，且满足 X< Y, Y=Z, T<Z, T<X，运用AC-4求解下列问题 通过弧一致性找出约束求解后的值域
初始化sport数组为初始化counter数组为（相互间没有约束关系的，均为*）
S(X,3) | <T,1><T,2> |
| S(Y,1) | <Z,1> |
| S(Y,2) | <X,1><Z,2> |
| S(Y,3) | <X,1><X,2><Z,3> |
| S(Z,1) | <Y,1> |
| S(Z,2) | <Y,2><T,1> |
| S(Z,3) | <Y,3><T,1><T,2> |
| S(T,1) | <Z,2><Z,3><X,2><X,3> |
| S(T,2) | <Z,3><X,3> |
| S(T,3) | |
初始化counter数组为（相互间没有约束关系的，均为*）
