目录1.一个棋类游戏可以定义为一个判定问题知道棋子的一个合法布局以及下一步是哪一方走的信息确定这一方是否会赢。这个判定问题是可判定的吗?2.一个特定的问题可以用一个运行时间为O(nlog₂ⁿ)的算法求解。下面哪个断言是正确的?3.对下面的图举一个例子或者说明为什么不存在这样的例子。a.存在哈密顿回路但不存在欧拉回路的图。b.存在欧拉回路但不存在哈密顿回路的图。c.既存在哈密顿回路又存在欧拉回路的图。d.图中存在一个包含所有顶点的回路但既没有哈密顿回路又没有欧拉回路。4.对于下面的每一个图求出它的颜色数量。5.为图的二色问题设计一个多项式时间的算法确定一个给定图的顶点是否可以用不超过两种颜色染色使得任何两个邻接的顶点都不同色。6.考虑下面这个解合数问题的蛮力算法把从 2 到[n/2]的连续整数作为n的可能除数进行检查。如果其中一个可以整除n就返回“是”(也就是说这个数字是合数)。如果没有一个数能够整除n则返回“否”。这个算法为什么不能使该问题归入P类?7.定义下面每个问题的判定版本并且简要描述问题的一个多项式时间的算法它能够检验某个待定解是不是问题的一个解。(我们可以假设一个待定解代表了检验算法的一个合法输入。)a.背包问题b.装箱问题8.证明划分问题能够在多项式时间内化简为背包问题的判定版本。9.证明下面三个问题能够在多项式的时间内相互转化。10.判断下面的问题是不是 NP 完全问题。给定几个由大小写字母构成的序列问是否可能从每个序列中选出一个字母使得同一个字母的大小写版本不会被同时选中。例如序列是 AbcBCaB 和 ac可以从第一个序列中选 A从第二和第三个序列中选B从第四个序列中选c。另外一个四个序列的例子是AB AbaB和 ab这个例子不存在选择方案能够满足问题要求。([Kar86])11.下面哪些示意图和我们当前对于复杂度类型 PNPNPC(NP 完全问题)的知识没有矛盾?12.亚瑟王打算请150名骑士参加宫中一年一度的宴会。遗憾的是有些骑士相互之间会有口角而亚瑟王知道谁和谁不和。亚瑟王希望能让他的客人围着一张圆桌坐下而所有不和的骑士相互之间都不会挨着坐。a.哪一个标准问题能够作为亚瑟王问题的模型?b.作为一个研究作业请证明如果和每个骑士不和的人数不超过75那么该问题是有解的。1.一个棋类游戏可以定义为一个判定问题知道棋子的一个合法布局以及下一步是哪一方走的信息确定这一方是否会赢。这个判定问题是可判定的吗?棋类游戏的合法布局数目有限每一步的走法数目也有限游戏必然在有限步内终止。因此可以通过穷举所有可能走法搜索整个游戏树来判断当前玩家是否有必胜策略。该问题是可判定的。2.一个特定的问题可以用一个运行时间为O(nlog₂ⁿ)的算法求解。下面哪个断言是正确的?a.该问题是易解的。b.该问题是难解的。c.以上两种说法都不对。先要知道易解问题 (tractable)存在多项式时间算法的问题即 O (n^k)k 是常数。难解问题 (intractable)不存在多项式时间算法比如指数级 O (2ⁿ)。而nlog₂ⁿ是小于n^2的所以选a3.对下面的图举一个例子或者说明为什么不存在这样的例子。a.存在哈密顿回路但不存在欧拉回路的图。b.存在欧拉回路但不存在哈密顿回路的图。c.既存在哈密顿回路又存在欧拉回路的图。d.图中存在一个包含所有顶点的回路但既没有哈密顿回路又没有欧拉回路。4.对于下面的每一个图求出它的颜色数量。a2b3c45.为图的二色问题设计一个多项式时间的算法确定一个给定图的顶点是否可以用不超过两种颜色染色使得任何两个邻接的顶点都不同色。二色问题等价于判断图是否为二分图用两种颜色给顶点着色相邻顶点颜色不同图中不含奇数长度环使用BFS / DFS遍历逐层染色即可给每个顶点标记颜色0未着色1颜色 12颜色 2从任意未着色顶点开始染成颜色 1。使用 BFS 或 DFS 遍历对当前顶点的每个邻居若未着色染成与当前顶点相反的颜色若已着色且与当前顶点同色则不是二色图返回false若整个图遍历完都没冲突返回true。时间O (V E)6.考虑下面这个解合数问题的蛮力算法把从 2 到[n/2]的连续整数作为n的可能除数进行检查。如果其中一个可以整除n就返回“是”(也就是说这个数字是合数)。如果没有一个数能够整除n则返回“否”。这个算法为什么不能使该问题归入P类?该蛮力算法的时间复杂度为O(n)相对于输入数值 n 是多项式时间7.定义下面每个问题的判定版本并且简要描述问题的一个多项式时间的算法它能够检验某个待定解是不是问题的一个解。(我们可以假设一个待定解代表了检验算法的一个合法输入。)a.背包问题① 判定版本给定 n 个物品每个物品有重量 wᵢ、价值 vᵢ背包容量 C以及一个目标值 K。判定是否存在一个子集使得总重量 ≤ C且总价值 ≥ K② 多项式时间验证算法给定一个候选解一个子集比如用 0/1 串表示计算子集的总重量计算子集的总价值检查总重量 ≤ C总价值 ≥ K满足则输出是否则否时间O(n)是多项式时间。b.装箱问题① 判定版本给定 n 个物品大小 sᵢ箱子容量 C以及箱子数量 K。判定是否可以用最多 K 个箱子装下所有物品② 多项式时间验证算法给定一个候选解每个物品被分配到哪个箱子对每个箱子计算箱内物品总大小检查每个箱子总大小 ≤ C使用的箱子数 ≤ K所有物品都被装了满足则输出是否则否时间O(n)是多项式时间。8.证明划分问题能够在多项式时间内化简为背包问题的判定版本。任给一个划分问题实例计算总和Sa1a2⋯an若 S 是奇数直接输出 “无解”。若 S 是偶数构造背包实例重量 wiai价值 viai容量 CS/2目标价值 KS/2这一步显然可以在多项式时间 O(n)内完成。若划分问题有解存在子集和为 S/2该子集满足因此背包判定为 yes。此时子集满足即该子集是划分问题的解划分问题为 yes。9.证明下面三个问题能够在多项式的时间内相互转化。a.对于一个给定的图GVE和一个正整数m≤|V|确定G是不是包含一个规模大于等于m的团(clique)。(图中一个规模为k的团是图的一个包含k个顶点的完全子图。)b.对于一个给定的图GVE和一个正整数m≤|V|确定是不是存在G的一个规模小于等于m的顶点覆盖(vertex cover)。(图GV,E的一个规模为k的顶点覆盖是一个满足|F|k的子集V⊆V并且对于每一条边(uv)∈Eu和v中至少有一个属于V。)c.对于一个给定的图GVE和一个正整数m≤|V|确定G是不是包含一个规模大于等于m的独立集(independent set)。(图GV,E的一个规模为k 的独立集是一个满足的子集V⊆V,并且对于所有的u, v∈V,顶点u和v在G中不邻接。)S 是 G 的团 ⇔ S 是补图 G 的独立集S 是 G 的独立集 ⇔ V\S 是 G 的顶点覆盖由此可得三个问题两两互相多项式归约顶点覆盖就是选一些顶点让图里的每一条边至少有一个端点被选中。独立集就是 “互相之间都不认识、没有边相连” 的一群点。对于团和独立集既然存在G(V,E)不妨设G_补(V,E_补)是G的补集那么对于(v,u)∈E就有v,u∈E_补若 S 是 G 中规模 ≥m 的团则任意两点相邻 ⇒ 在补图中任意两点不相邻 ⇒ S 是 G_补 的独立集。反之若 S 是 G_补 的独立集则 S 是 G 的团。构造补图只需 O(∣V∣^2)是多项式时间。对于顶点覆盖和独立集同样有假设S是G的独立集V∖S(V中除了S的部分)是G的顶点覆盖S 独立集 ⇔ 每条边至少有一个端点不在 S⇔ 每条边至少有一个端点在 V∖S⇔ V∖S 是顶点覆盖。大小关系为转换效率为O(1),因此由传递性团与顶点覆盖也能转换10.判断下面的问题是不是 NP 完全问题。给定几个由大小写字母构成的序列问是否可能从每个序列中选出一个字母使得同一个字母的大小写版本不会被同时选中。例如序列是 AbcBCaB 和 ac可以从第一个序列中选 A从第二和第三个序列中选B从第四个序列中选c。另外一个四个序列的例子是AB AbaB和 ab这个例子不存在选择方案能够满足问题要求。([Kar86])1. 它属于 NP给定一个 “从每个串里各选一个字母” 的候选解我们可以在多项式时间内检查是不是每个串恰好选了一个字母有没有任意一个字母大写和小写同时被选中验证是多项式的 ⇒ 问题在NP中。2. 可以从3-SAT多项式归约过来思路把每个序列看作一个子句每个字母的大写 / 小写看作一个布尔变量及其否定要求 “不能同时选同一个字母的大小写”⇔ 不能同时选一个变量和它的否定⇔ 对应逻辑公式的可满足性已知SAT / 3-SAT 是 NP 完全且归约可以在多项式时间完成因此该问题是 NP 完全问题。11.下面哪些示意图和我们当前对于复杂度类型 PNPNPC(NP 完全问题)的知识没有矛盾?┌───────────────────────────── NP ─────────────────────────────┐ │ │ │ ┌──────────┐ ┌────────────────────┐ │ │ │ P │ │ NP-完全(NPC) │ │ │ └──────────┘ └────────────────────┘ │ │ │ └──────────────────────────────────────────────────────────────┘P ⊆ NPNPC ⊆ NP如果P≠NP则P 和 NPC 不相交NP 里还有既不是 P 也不是 NPC 的问题NP-intermediate(a) 不可能因为对于所有输入都返回“是”的平凡判定问题显然不是 NP 完全的。(b) 可能描述了 P NP 的情况(c) 不可能因为若 P ≠ NP则必须存在既不在 P 也不是 NP 完全的问题。(d) 不可能因为这意味着存在一个 NP 完全问题属于 P这要求 P NP。(e) 可能描述了 P ≠ NP 的情况12.亚瑟王打算请150名骑士参加宫中一年一度的宴会。遗憾的是有些骑士相互之间会有口角而亚瑟王知道谁和谁不和。亚瑟王希望能让他的客人围着一张圆桌坐下而所有不和的骑士相互之间都不会挨着坐。a.哪一个标准问题能够作为亚瑟王问题的模型?把每个骑士看作一个顶点。如果两个骑士关系和睦可以相邻坐就在两点之间连一条边。亚瑟王的要求找一条经过所有顶点的简单回路让相邻骑士都和睦。这正是无向图的哈密顿回路问题。b.作为一个研究作业请证明如果和每个骑士不和的人数不超过75那么该问题是有解的。也就是说每个骑士朋友 ≥ 150 − 1 − 75 74而由狄拉克定理可知一个n ≥ 3个顶点的简单无向图如果每个顶点的度数 ≥ n/2那么这个图一定存在哈密顿回路。
算法设计与分析-习题11.3
发布时间：2026/5/26 6:15:02
目录1.一个棋类游戏可以定义为一个判定问题知道棋子的一个合法布局以及下一步是哪一方走的信息确定这一方是否会赢。这个判定问题是可判定的吗?2.一个特定的问题可以用一个运行时间为O(nlog₂ⁿ)的算法求解。下面哪个断言是正确的?3.对下面的图举一个例子或者说明为什么不存在这样的例子。a.存在哈密顿回路但不存在欧拉回路的图。b.存在欧拉回路但不存在哈密顿回路的图。c.既存在哈密顿回路又存在欧拉回路的图。d.图中存在一个包含所有顶点的回路但既没有哈密顿回路又没有欧拉回路。4.对于下面的每一个图求出它的颜色数量。5.为图的二色问题设计一个多项式时间的算法确定一个给定图的顶点是否可以用不超过两种颜色染色使得任何两个邻接的顶点都不同色。6.考虑下面这个解合数问题的蛮力算法把从 2 到[n/2]的连续整数作为n的可能除数进行检查。如果其中一个可以整除n就返回“是”(也就是说这个数字是合数)。如果没有一个数能够整除n则返回“否”。这个算法为什么不能使该问题归入P类?7.定义下面每个问题的判定版本并且简要描述问题的一个多项式时间的算法它能够检验某个待定解是不是问题的一个解。(我们可以假设一个待定解代表了检验算法的一个合法输入。)a.背包问题b.装箱问题8.证明划分问题能够在多项式时间内化简为背包问题的判定版本。9.证明下面三个问题能够在多项式的时间内相互转化。10.判断下面的问题是不是 NP 完全问题。给定几个由大小写字母构成的序列问是否可能从每个序列中选出一个字母使得同一个字母的大小写版本不会被同时选中。例如序列是 AbcBCaB 和 ac可以从第一个序列中选 A从第二和第三个序列中选B从第四个序列中选c。另外一个四个序列的例子是AB AbaB和 ab这个例子不存在选择方案能够满足问题要求。([Kar86])11.下面哪些示意图和我们当前对于复杂度类型 PNPNPC(NP 完全问题)的知识没有矛盾?12.亚瑟王打算请150名骑士参加宫中一年一度的宴会。遗憾的是有些骑士相互之间会有口角而亚瑟王知道谁和谁不和。亚瑟王希望能让他的客人围着一张圆桌坐下而所有不和的骑士相互之间都不会挨着坐。a.哪一个标准问题能够作为亚瑟王问题的模型?b.作为一个研究作业请证明如果和每个骑士不和的人数不超过75那么该问题是有解的。1.一个棋类游戏可以定义为一个判定问题知道棋子的一个合法布局以及下一步是哪一方走的信息确定这一方是否会赢。这个判定问题是可判定的吗?棋类游戏的合法布局数目有限每一步的走法数目也有限游戏必然在有限步内终止。因此可以通过穷举所有可能走法搜索整个游戏树来判断当前玩家是否有必胜策略。该问题是可判定的。2.一个特定的问题可以用一个运行时间为O(nlog₂ⁿ)的算法求解。下面哪个断言是正确的?a.该问题是易解的。b.该问题是难解的。c.以上两种说法都不对。先要知道易解问题 (tractable)存在多项式时间算法的问题即 O (n^k)k 是常数。难解问题 (intractable)不存在多项式时间算法比如指数级 O (2ⁿ)。而nlog₂ⁿ是小于n^2的所以选a3.对下面的图举一个例子或者说明为什么不存在这样的例子。a.存在哈密顿回路但不存在欧拉回路的图。b.存在欧拉回路但不存在哈密顿回路的图。c.既存在哈密顿回路又存在欧拉回路的图。d.图中存在一个包含所有顶点的回路但既没有哈密顿回路又没有欧拉回路。4.对于下面的每一个图求出它的颜色数量。a2b3c45.为图的二色问题设计一个多项式时间的算法确定一个给定图的顶点是否可以用不超过两种颜色染色使得任何两个邻接的顶点都不同色。二色问题等价于判断图是否为二分图用两种颜色给顶点着色相邻顶点颜色不同图中不含奇数长度环使用BFS / DFS遍历逐层染色即可给每个顶点标记颜色0未着色1颜色 12颜色 2从任意未着色顶点开始染成颜色 1。使用 BFS 或 DFS 遍历对当前顶点的每个邻居若未着色染成与当前顶点相反的颜色若已着色且与当前顶点同色则不是二色图返回false若整个图遍历完都没冲突返回true。时间O (V E)6.考虑下面这个解合数问题的蛮力算法把从 2 到[n/2]的连续整数作为n的可能除数进行检查。如果其中一个可以整除n就返回“是”(也就是说这个数字是合数)。如果没有一个数能够整除n则返回“否”。这个算法为什么不能使该问题归入P类?该蛮力算法的时间复杂度为O(n)相对于输入数值 n 是多项式时间7.定义下面每个问题的判定版本并且简要描述问题的一个多项式时间的算法它能够检验某个待定解是不是问题的一个解。(我们可以假设一个待定解代表了检验算法的一个合法输入。)a.背包问题① 判定版本给定 n 个物品每个物品有重量 wᵢ、价值 vᵢ背包容量 C以及一个目标值 K。判定是否存在一个子集使得总重量 ≤ C且总价值 ≥ K② 多项式时间验证算法给定一个候选解一个子集比如用 0/1 串表示计算子集的总重量计算子集的总价值检查总重量 ≤ C总价值 ≥ K满足则输出是否则否时间O(n)是多项式时间。b.装箱问题① 判定版本给定 n 个物品大小 sᵢ箱子容量 C以及箱子数量 K。判定是否可以用最多 K 个箱子装下所有物品② 多项式时间验证算法给定一个候选解每个物品被分配到哪个箱子对每个箱子计算箱内物品总大小检查每个箱子总大小 ≤ C使用的箱子数 ≤ K所有物品都被装了满足则输出是否则否时间O(n)是多项式时间。8.证明划分问题能够在多项式时间内化简为背包问题的判定版本。任给一个划分问题实例计算总和Sa1a2⋯an若 S 是奇数直接输出 “无解”。若 S 是偶数构造背包实例重量 wiai价值 viai容量 CS/2目标价值 KS/2这一步显然可以在多项式时间 O(n)内完成。若划分问题有解存在子集和为 S/2该子集满足因此背包判定为 yes。此时子集满足即该子集是划分问题的解划分问题为 yes。9.证明下面三个问题能够在多项式的时间内相互转化。a.对于一个给定的图GVE和一个正整数m≤|V|确定G是不是包含一个规模大于等于m的团(clique)。(图中一个规模为k的团是图的一个包含k个顶点的完全子图。)b.对于一个给定的图GVE和一个正整数m≤|V|确定是不是存在G的一个规模小于等于m的顶点覆盖(vertex cover)。(图GV,E的一个规模为k的顶点覆盖是一个满足|F|k的子集V⊆V并且对于每一条边(uv)∈Eu和v中至少有一个属于V。)c.对于一个给定的图GVE和一个正整数m≤|V|确定G是不是包含一个规模大于等于m的独立集(independent set)。(图GV,E的一个规模为k 的独立集是一个满足的子集V⊆V,并且对于所有的u, v∈V,顶点u和v在G中不邻接。)S 是 G 的团 ⇔ S 是补图 G 的独立集S 是 G 的独立集 ⇔ V\S 是 G 的顶点覆盖由此可得三个问题两两互相多项式归约顶点覆盖就是选一些顶点让图里的每一条边至少有一个端点被选中。独立集就是 “互相之间都不认识、没有边相连” 的一群点。对于团和独立集既然存在G(V,E)不妨设G_补(V,E_补)是G的补集那么对于(v,u)∈E就有v,u∈E_补若 S 是 G 中规模 ≥m 的团则任意两点相邻 ⇒ 在补图中任意两点不相邻 ⇒ S 是 G_补 的独立集。反之若 S 是 G_补 的独立集则 S 是 G 的团。构造补图只需 O(∣V∣^2)是多项式时间。对于顶点覆盖和独立集同样有假设S是G的独立集V∖S(V中除了S的部分)是G的顶点覆盖S 独立集 ⇔ 每条边至少有一个端点不在 S⇔ 每条边至少有一个端点在 V∖S⇔ V∖S 是顶点覆盖。大小关系为转换效率为O(1),因此由传递性团与顶点覆盖也能转换10.判断下面的问题是不是 NP 完全问题。给定几个由大小写字母构成的序列问是否可能从每个序列中选出一个字母使得同一个字母的大小写版本不会被同时选中。例如序列是 AbcBCaB 和 ac可以从第一个序列中选 A从第二和第三个序列中选B从第四个序列中选c。另外一个四个序列的例子是AB AbaB和 ab这个例子不存在选择方案能够满足问题要求。([Kar86])1. 它属于 NP给定一个 “从每个串里各选一个字母” 的候选解我们可以在多项式时间内检查是不是每个串恰好选了一个字母有没有任意一个字母大写和小写同时被选中验证是多项式的 ⇒ 问题在NP中。2. 可以从3-SAT多项式归约过来思路把每个序列看作一个子句每个字母的大写 / 小写看作一个布尔变量及其否定要求 “不能同时选同一个字母的大小写”⇔ 不能同时选一个变量和它的否定⇔ 对应逻辑公式的可满足性已知SAT / 3-SAT 是 NP 完全且归约可以在多项式时间完成因此该问题是 NP 完全问题。11.下面哪些示意图和我们当前对于复杂度类型 PNPNPC(NP 完全问题)的知识没有矛盾?┌───────────────────────────── NP ─────────────────────────────┐ │ │ │ ┌──────────┐ ┌────────────────────┐ │ │ │ P │ │ NP-完全(NPC) │ │ │ └──────────┘ └────────────────────┘ │ │ │ └──────────────────────────────────────────────────────────────┘P ⊆ NPNPC ⊆ NP如果P≠NP则P 和 NPC 不相交NP 里还有既不是 P 也不是 NPC 的问题NP-intermediate(a) 不可能因为对于所有输入都返回“是”的平凡判定问题显然不是 NP 完全的。(b) 可能描述了 P NP 的情况(c) 不可能因为若 P ≠ NP则必须存在既不在 P 也不是 NP 完全的问题。(d) 不可能因为这意味着存在一个 NP 完全问题属于 P这要求 P NP。(e) 可能描述了 P ≠ NP 的情况12.亚瑟王打算请150名骑士参加宫中一年一度的宴会。遗憾的是有些骑士相互之间会有口角而亚瑟王知道谁和谁不和。亚瑟王希望能让他的客人围着一张圆桌坐下而所有不和的骑士相互之间都不会挨着坐。a.哪一个标准问题能够作为亚瑟王问题的模型?把每个骑士看作一个顶点。如果两个骑士关系和睦可以相邻坐就在两点之间连一条边。亚瑟王的要求找一条经过所有顶点的简单回路让相邻骑士都和睦。这正是无向图的哈密顿回路问题。b.作为一个研究作业请证明如果和每个骑士不和的人数不超过75那么该问题是有解的。也就是说每个骑士朋友 ≥ 150 − 1 − 75 74而由狄拉克定理可知一个n ≥ 3个顶点的简单无向图如果每个顶点的度数 ≥ n/2那么这个图一定存在哈密顿回路。
![别再乱装 Skill 了！这 4 组神级 Skill 让你的 Claude Code 直接封神[特殊字符]【2026 最新实测】](http://pic.xiahunao.cn/yaotu/别再乱装 Skill 了！这 4 组神级 Skill 让你的 Claude Code 直接封神[特殊字符]【2026 最新实测】)
