第
17卷第4期 2018年 4月
Journal of Educational Technology
软件导刊•教育技术
Vol.l7No.4Apr. 2018
NP难解问题的教学方法探讨
张
辉，王裕明，姚兴华，孔丽红
(上海工程技术大学电子电气工程学院，上海201620)
摘要
：N
P难解问题，由于其理解起来的难度，加之目前本科生中普遍存在的学习和思想误区，实际
教学难以取得理想的效果。有鉴于此，讨论了两种教学方法，旨在使难于理解的抽象问题转换为具体的 有趣问题，降低初学者理解NP难解问题的难度，唤起学生的学习热情，提升教学效果。
关键词：理论计算机科学；NP难解问题；多项式时间归约；整数规划问题；可满足性问题 中图分类号：（434
文献标识码：A
文章编号！672-7800(2018)04-0082-02
1现状分析
NP难解问题是
一
本操作。继续考虑乘法，类似的，两个一位数相乘需要背一 次乘法口诀，两个w位数相乘，需要乘数的每一位去乘被乘
类理论上可解，但为了获取其解需要
数的每一位，因此，需要背w2次乘法口诀，之后还要把得到
耗费大量的时间和空间的计算问题。该章节的教学是离散
数学中最难的部分，在当前教学中存在急功近利、代码为王、 数据为王、程序不思其解只要运行结果的思想，学生对理论 的学习缺乏学习积极性，望而生畏。要想改变这一部分教学 内容的教学现状、提升教学效果，需要从以下几方面改进。
w行数加起来，这又起码是w—1次w位的一位数加法，因
此，不难理解两个w位数相乘的算法复杂度为0(w2 \"即，乘
法比加法更复杂。
进一步，可以让学生思考乘法的反方向问题，分解因 子。对于很小的合数，我们利用较小的素数因子2、3、5等 去除它可以很快的进行分解。但是对于较大的数，比如，这 个 129 位的整数，1143816257578888676692357799761) 6612010218296721242362562561842935706935245733783 059712356395870505075147599290026879543541，人类 无法完成分解。事实上，这个大数也正是1977年RSA加密 算法的创始人向全世界提出的挑战，当时估计四万兆年后 人类才能完成它的分解。当然，借助于计算机的帮助，17年 后的1994年，研究人员总共动用1 600部电脑花了 8个月 的时间得到了分解的结果。通过这一组简单易懂的实例的 讲解，学生可以很好的体会高复杂度的计算对计算机而言 也是难解的。在此基础上，再给学生引入多项式时间复杂 度和指数时间复杂度的分类，学生也就更易理解。
更进一步，虽然对129位整数进行因子分解是一个很 难的问题，但如果让它除以34905295108476509491478 4961990381334177638493387843990820577 这个 位 整数，虽然除起来也很花时间，但只要有足够的耐心和细
\"
2.1
教学方法探讨
利用启发式教学引导学生体会难解问题的“难”之所在难解问题的传统教学模式是，首先介绍图灵机数学概
念，尤其是确定性图灵机和非确定性图灵机的概念，然后介 绍P类问题和NP类问题，并通过引入归约的概念，证明在
NP类问题中存在一个子类，所有的NP类问题都可以在多
项式时间内转化为此类问题，即，NP完全问题。这些知识
点，充斥着大量的概念和严格符号化的证明，要想获得良好 的教学效果，必须转换教学理念，使抽象的理论具体化，让 学生通过实例去理解和体会为什么有些问题比另一些问题 “难”，而有些问题甚至对计算机都是“难解”的。
比如，四则运算中加法更简单，因为两个一位数相加， 至多是两位数，两个〃位数相加，至多是〃十1位数，两个w 位数相加的算法复杂度为〇(w)，这里以一位数的加法为基
收稿日期：2017-11-07基金项目：上海市重点课程建设项目（201502001);上海工程技术大学教育科学研究项目（y201602001);上海工程技术大学《数据库原理》
课程建设项目（201702003)
k
作者简介：张辉（1975-)，男，硕士，上海工程技术大学电子电气工程学院讲师，研究方向为理论计算机科学；王裕明（1961-)，男，硕士，上海
工程技术大学电子电气工程学院教授、硕士生导师，研究方向为信息管理和计算机应用；姚兴华（1982-)，男，博士，上海工程技 术大学电子电气工程学院讲师，研究方向为形式化方法；孔丽红（1975-)，女，硕士，上海工程技术大学电子电气工程学院讲师， 研究方向为数据库理论和地理信息系统。
第）期
张辉，王裕明，姚兴华，等：
NP难解问题的教学方法探讨
的整数规划问题。
又如，SAT问题的优化版本—
• 83 •
心，哪怕是小学生也能算出来结果，因为除法是一个多项式
时间复杂度的算法。事实上，它的确是那个129位数的一 个因子。那么，如果某人灵机一动，猜到了这个数，只需除 一下检验猜测的是否正确即可。到这里，学生就可以体会 出，有那么一类问题，虽然直接求结果，哪怕对计算机而言 也是很难的，但是，如果可以猜测结果的话，则可以在多项 式时间内验证猜测。这里就引人了 NP类问题，即，先猜测 一个结果，再利用多项式时间复杂度的算法进行检验。2.2灵活运用实例降低难解证明的理解难度
最大可满足性问题。
假设命题逻辑合取范式公式F=F1 * F\" *…* Fm，其中F, 为命题变元集合X= {\"；!，\"2，…，\"m}上的析取项，最大可满 足性问题是指F中最多有多少个析取项是可满足的？如果 变元\"9真值为真当且仅当\"9 = 1，引人m维列向量2T =
U1，…，z„)，z, = 1当且仅当析取项F,可满足，并定义^ +
(F,)为F,中以正文字\"，形式出现变元的下标集- (F,) 为F,中以负文字？\"，形式出现变元的下标集，则最大可满
虽然有很多问题可能都是NP类问题，也都很难，但怎 么衡量它们之间的难易程度，这就需要引人多项式时间归 约和NP完全性的概念。
传统的NP完全性归约的证明讲解，首先是介绍Cook 定理证明合取范式的可满足性问题SAT的完全性，然后引 人一些经典的问题，设计一个由SAT传递归约的路线，同 时总结证明NP完全性的一些技巧。比如，在Garey W
Johnson的经典名著《计算机与难解性》一书中，作者先给出 了 SAT问题的特例3SAT、“三维匹配问题”（3DM)、“顶点覆 盖问题”(VC)等6个问题，然后通过将SAT归约为3SAT、将 3SAT分别归约为3DM和VC等证明它们的NP完全性，并
总结了、局部代换和组件设计等证明技巧。这些证明中 的某些技巧，从SAT到3SAT相对比较容易理解，但多数证 明中用到的技巧，只能让初学NP完全性证明的人叹为观止 但敬而远之。其它书籍中用到的证明思路，也大体类似，所 不同的就是选择的典型问题或者是归约证明的路线。
事实上，相对容易理解且更能吸引学生兴趣的是一类 特殊的优化问题——
线性规划，尤其是整数线性规划问题。
一般地，线性规划问题，是对形如以下形式的问题
目标函数* (CT • X
约束条件:
寻找满足约束条件的目标函数的最优值，可以是最大 值或最小值，其中C、X均为《维列向量，A为矩阵，
B为m维列向量。而整数线性规划，不仅需要约束条件矩 阵A、向量B和C中各值为整数外，还进一步要求X中的值
也得为整数。正是这个为整数的要求，使得整数线性规划 问题成为一个经典的NP难解问题。为此，在课堂教学中， 可以将某些经典NP难解问题作为教学案例，通过将它们归 约为整数规划问题，从而说明这些难解问题并不比整数规 划更难，也可以大大降低学生理解的难度。
比如，0 — 1背包问题。它是将重量分别为，…，•〇>„， 价值分别为„的物品放人一个最多可载重6的背包 中，以期望背包中放人物品的价值最大。显然，如果引人》 维列向量灰了=(叫，5，叫）和CT=(Cl，…，c„)以及引人取 值为{0，
1}的《维列向量X，_r, = 1当且仅当重为％的物品
放人背包，则0 — 1背包问题可以表示为
目标函数：max CT • X : max( ct •
9
-1
约束条件：WT • X = (59
• \"9 ) b
9
-1
足性
以
为
目标函数：max(z,
9-1
约束条件：29— ( \"< — ( (1 — \"<) ) 0,其中 9—
< + .+ (f9)
< + . (f9)
1，…
的整数规划问题。其中，约束条件保证了 Y = 1当且仅当析 取项巧可满足。由于SAT问题是由Cook证明了的第一个
NP %它的优 大 满足性 为
数规划问题，所以，SAT问题不比整数规划更难，利用将其 他难解问题归约为整数规划问题，就可以证明更多的NP完
。
3结语
可以看出，通过启发学生思考问题的难解程度以及基
于整数线性规划讨论难解问题归约的教学策略，相比着传 统的讲解，其理解的难度大大降低，有助于学生理解难解问 题。尤其是在学生解决实际算法问题时，当设计求解某些 问题的高效算法而百思不得其解时，可能就需要换种思路， 证明这个问题是NP难解的，进而说明这类问题不大可能存 在高效的算法。而对于一个NP难解问题，就可以引导学生 通过考虑特殊情形、概率分析、近似算法或启发式算法等策 略求解。当然，这些教学策略的不足是减少了学生欣赏原 始证明中的那些奇妙构造的机会。可在学生理解NP完全 问题及其归约的基础上，介绍更多的例子加以补充，以达到 既降低了理解难度，又开阔学生视野的效果。参考文献：
[1]
GAREY M, JOHNSON D. Computer and Intractability[M],
New York： W. H. Freeman andCompany, 1979 ：46-74.
[2]
JURAJ H. Algorithmics for hard problems [M]. Springer,
2002:211-218.
[]
SANJOY D, CHRISTOS P, UMESH V.算法概论[M].北
京：机械工业出版社，2009:247-263.
[4] 姚雪梅编译原理”课程的教学探索
[J].重庆交通学院学报：
社科版，2003(6) :85-86.
[] 谭永基.离散型数学模型问题的计算复杂性简介
[J].数学的
实践与认识数学的实践与认识，1997(2) : 141-147.
(编辑：叶露）
