什么是算法(Algorithm)?算法的性质是什么?算法与程序的区别?

1 什么是算法? 算法是指解决问题的一种方法或一个过程。 2 算法的性质 算法是若干指令的有穷序列,满足性质: (1)输入:有外部提供的量作为算法的输入。 (2)输出:算法产生至少一个量作为输出。 (3)确定性:组成算法的每条指令是清晰,无歧义的。 (4)有限性:算法中每条指令的执行次数是有限的,执行每条指令的时间也是有限的。 3 什么是程序? 程序是算法用某种程序设计语言的具体实现。 4 程序与算法的区别 程序可以不满足算法的性质(4)。 例如操作系统,是一个在无限循环中执行的程序,因而不是一个算法。 操作系统的各种任务可看成是单独的问题,每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止 0

Read More

电路可满足性问题

【电路可满足性问题】 电路可满足性问题(Circuit satisfiability problem)描述为:给定一个电路,需要确定是否存在对输入的赋值使得输出值为1。如果存在这样的赋值,则称这个电路是可满足的。这个赋值也被称为一个满足的赋值。如图5为电路可满足性问题的一个实例。 图5 电路可满足性问题 图中的左边,从上到下依次是或门、非门。图中的右边是与门。当1和2输入都为1,3输入为0的时候,输出为1。即这个电路是满足的。 0

Read More

难问题的部分分类

难问题的部分分类 1 包装问题 包装问题主要有独立集问题和集合包装问题。 (1)独立集问题:给定图G和数k,问G包含大小至少为k的独立集吗? (2)集合包装问题:给定 n 个元素的集合 U , U 的子集 S_1,S_2,…,S_m 以及数 k , 问在这些子集中至少含有 k 个集合两两不相交? 2

Read More

三维匹配问题是NP完全的

【三维匹配问题】 给定三个不相交的集合X、Y、Z,三个集合的大小都为n。给定一个三元组集合T \subseteq X \times Y \times Z,集合T的大小为m。 问:T中是否存在一个大小为n的子集T’,这个子集恰好包含X,Y,Z每个元素一次。 三维匹配问题其实是集合覆盖和集合包装问题的特例。 三维匹配问题是NP完全的 首先,很容易证明三维匹配问题是NP问题。只需要判断集合T’的大小是否为n,且包含X,Y,Z中每个元素一次。证明三维匹配问题是NPC的,可以通过3-SAT\leq_p三维匹配证明。 【3-SAT\leq_p三维匹配证明】 考虑任意的一个3-SAT实例,有n个变量x_1,x_2,…,x_n和k个子句C_1,C_2,…,C_n。构造3DM实例X,Y,Z,T。 对于每一个变量,都有一个零件相对应。如图9所示。每个零件有Core(核心)元素、Tip(边梢)元素、Triple元组。每一个零件大大小为2k。k为子句的大小。\ 则,对于每一个变量x_i,建立: A_i={a_{i,1},a_{i,2},…,a_{i,2k}}。 B_i={b_{i,1},b_{i,2},…,b_{i,2k}}。 t_{i,j}={(a_{i,j},a_{i,j+1},b_{i,j}}。 构造的零件如图9所示。

Read More

独立集和顶点覆盖之间的归约

独立集与顶点覆盖之间的归约 【独立集问题(Independent set)】 一个独立集(也称为稳定集)是一个图中一些两两不相邻的顶点所形成的集合。即顶点集合的任意两个点之间没有边。如图1,红色的点集合都是独立集,任意两个红色的顶点没有边。 图1 独立集(红色) 【顶点覆盖问题】 图的顶点覆盖也是一个点的集合。图中每一条边都至少有一个顶点在点集合中。如图2,黑色的点集合都是顶点覆盖集合,图的每一条边都至少有一个顶点在点集合中。 图2 顶点覆盖集(黑色) 【独立集与顶点覆盖之间的归约】 独立集问题:给定图G和数k,问G包含大小至少为k的独立集吗? 顶点覆盖问题:给定图G和数k,G是否包含大小为k的顶点覆盖? 证明两个问题的难度是等价的。 定理3:设G=(V,E)是一个图,S\subseteq V,则S是一个独立集当且仅当它的补图V-S是一个顶点覆盖。 证明: 设S是一个独立集,考虑任意的一条边,因为S是独立集,则u和v不可能都在S中,因此u和v必有一个在V-S中。则每一条至少有一个端点在V-S中,即V-S是一个点覆盖集合。 反过来,假设V-S是一个顶点覆盖。考虑S中的任意两个顶点u和v,如果它们之间有一条边e,则e的两个端点都不在V-S中,则与假设V-S是一个顶点覆盖矛盾。因此,S中的任何两个顶点之间都没有边,则S是一个独立集。 【独立集\leq_p顶点覆盖问题】

Read More

巡回售货员问题是NP完全的

巡回售货员问题 【巡回售货员问题】 有一位巡回售货员,他必须访问n个城市,分别记作v_1,v_2,v_3,…,v_n,售货员从他所居住的城市v_1出发,想找一条旅行路径,访问所有的其他城市最后回到家的顺序。目标是整个旅行路径的距离尽可能的小。 对于每一对城市(v_i,v_j),城市的距离为d(v_i,v_j)。并且,距离不是对称的,即d(v_i,v_j) \neq d(v_j,v_i)。也不要求距离之间满足三角不等式。因此巡回售货员问题的目标是使得总距离\sum_{j=1}^{n-1}d(v_{i_j},v_{i_{j+1}})+d(v_{i_n},v_{i_1})最小。 巡回售货员问题的判定形式为:给定n个城市之间的距离的集合以及界限D,问有长度不超过D的路线吗? 巡回售货员问题是NP完全的 首先,很容易证明巡回售货员问题是一个NP问题,其验证程序可以多项式时间内验证对应的路线的长度是否超过了给定的界限。 可以通过证明哈密顿圈\leq_p巡回售货员,证明巡回售货员问题是NP完全的。 【哈密顿圈\leq_p巡回售货员】 对于一个有向图G=(V,E),规定下述巡回售货员问题实例:对于图中的每一个点v_i,有一个城市v_{i}’。如果在G中有边,则d(v_i’,v_j’)=1,否则d(v_i’,v_j’)=2。 则,G中有哈密顿圈当且仅当这个巡回售货员问题中有长度不超过n的巡回路线。 因此,哈密顿圈\leq_p巡回售货员,巡回售货员问题是NPC的。 ———————————————————————————— 证明哈密顿圈问题是NPC的: 证明哈密顿圈问题是NPC的,可以通过证明3-SAT\leq_p哈密顿圈来得到。 【3-SAT\leq_p哈密顿圈】 构造方法如下: (1)对于每一个变量x_i,创建3m+3个顶点。命名为v_{i,1},…,v_{i,3m+3},并且对相邻的顶点,添加边(v_{i,j},v_{i,j+1})和(v_{i,j+1},v_{i,j})。如图中7中红色的点和绿色的边。如果x_i为1,则路径P_i从左到右。反之,如果x_i为0,则路径P_i从右到左。

Read More