;第11章难解性问题求解—组合、随机与近似解;怎样研究算法：研究什么算法;社会/自然现象(遗传与进化);社会/自然现象(遗传与进化);社会/自然现象(遗传与进化);现实世界中的问题分类;问题规模n;【P类问题】多项式问题(PolynomialProblem)，即：可以找出一个呈现O(na)复杂性算法求出精确解的问题，其中a为常数。P类问题是指计算机可以在有限时间内求出精确解的问题，
【NP类问题】非确定性多项式问题(Non-deterministicPolynomial)，即：可以找出一个呈现O(na)复杂性算法来验证一个解是否正确的非确定性问题。
有些问题，其答案无法直接计算得到，但可通过间接的猜算/试算来得到，这就是非确定性问题(Non-deterministic)。
虽然在多项式时间内难于求解，但给定一个解却不难在多项式时间内验证其正确性的问题，即是NP类问题。
【NPC类问题】完全非确定性多项式问题(NP-Complete)，即：如果NP问题的所有可能解都可以在多项式时间内进行正确与否的验算，则为NP-Complete问题。
一个NP问题，并非其每个解都可以在多项式时间内验算，即：有些解是可以验算的，而有些解是不能验算的。
如果一个NP问题其需要验算的解空间是用非多项式函数(指数函数或阶乘函数)来表达的，则是NP-Complete问题。
如果一个NP问题经过约简后得到的问题仍旧是NP问题，则是NP-Complete问题;穷举法或称遍历法：对解空间中的每一个可能解进行验证，直到所有的解都被验证是否正确，便能得到精确的结果---精确解;第11章难解性问题求解—组合、随机与近似解;关于生物遗传进化的基本观点
(i)生物的所有遗传信息都包含在其染色体中，染色体决定了生物的性状；
(ii)染色体是由基因及其有规律的排列所构成的，遗传和进化过程发生在染色体上；
(iii)生物的繁殖过程是由其基因的复制过程来完成的；
(iv)通过同源染色体之间的交叉或染色体的变异会产生新的物种，使生物呈现新的性状。
(v)对环境适应性好的基因或染色体经常比适应性差的基因或染色体有更多的机会遗传到下一代。;;种群(Population)vs.个体(Individual)vs.染色体(chromosome)
染色体(chromosome)vs.基因(gene)
基因型(Genotype)vs.表现型(Phenotype)
个体的适应度(Fitness)
选择(Selection)
复制((Reproduction)
交配/杂交(Crossover)
突变(Mutation);;第11章难解性问题求解—组合、随机与近似解;【示例】;生物学中的概念;求X,满足MinF(X)=X2-19X+20
forX=1,…,64之间的整数；;;例如：将X的染色体转为其个体表现形式，取个体的适应度函数为F(X)，即计算F(X);繁衍种群(候选解集)的适应性评价;选择:选优汰劣;仿生物学过程进行问题求解（一张图显示）;表达成算法;第11章难解性问题求解—组合、随机与近似解;四、探讨算法的本质--遗传算法为什么可以求解NP问题？;;;;;对于NPC问题，当没有其他更好的算法可以使用时，可以考虑选择遗传算法。
遗传算法的适用条件：
(1)已知【解空间】。即:【可能解】能够被表达、被枚举
(2)已知关于可能解的【适应度】的计算方法。即：能够判断一个可能解是接近精确解还是偏离精确解。适应度用于判断一个可能解接近精确解的程度或方向。;第11章难解性问题求解—组合、随机与近似解;【示例1】“会议室”租用问题;【示例2】“航班机组成员”选择问题;【示例3】“软件测试用例”选择问题;;用遗传算法求解一维解覆盖问题;【示例】“课程表”优化问题
8门课程需安排教室，记为Li，i=1,…,8；
6个教室可被使用，记为Rj，j=1,…,6；
要求每门课只能安排在一个教室，而每个教室最多只能安排两门课。
教室与课程班之间的约束矩阵A如下表给出，其中aij=1表示该课程班可以安排在该教室，aij=0则不可安排。
费用为教室容纳人数/课程班人数，即Cij=Kj/Li。;可能解是二维矩阵;;NPC求解:
产生一个或一批可能解
判断可能解是否是问题的解;实际问题分析:解的形式,解的约束,解空间;x11x12…x1n
x21x22…x2n
………
xm1xm2…xmn;行优先编码:课程分段编码,一门课程相关的划为一段，有多少课程就有多少段;NPC求解:
产生一个或一批可能解
判断可能解是否是问题的解;0;0;0;行交叉是指对两个染色体同位置的两个课程段