通常以第 c 层意义的正确性作为衡 量一个算法是否合格的标准。
2. 可读性
算法另一方面，晦涩难读的程序 易于隐藏较多错误而难以调试；
3．健壮性
当输入的数据非法时，算法应当恰当 地作出反映或进行相应处理，而不是产 生莫名奇妙的输出结果。并且，处理出 错的方法不应是中断程序的执行，而应 是返回一个表示错误或错误性质的值， 以便在更高的抽象层次上进行处理。
4．有输入 作为算法加工对象的量值， 通常体现为算法中的一组变量。有些输入 量需要在算法执行过程中输入，而有的算 法表面上可以没有输入，实际上已被嵌入 算法之中；
5．有输出 它是一组与“输入”与 确 定关系的量值，是算法进行信息加 工后得到的结果，这种确定关系即 为算法的功能。
二、算法设计的原则 设计算法时，通常应考虑达到以下目标：
1.3 计算复杂性的概念
算法计算量的度量之例——TSP枚举法
计算量的统计： 城市数n 第一城市为始终点，计算一条路径（1,i2, ,in,1）长度的基本运算 为两两城市间距离的n个数求和,共有(n 1)!条路径,
求和运算次数为：(n 1)!n n!;
枚举所有路径进行(n 1)!次比较可得最优路径,基本计算总次数为
计算 1 24 10 4.3 4.9 时间 sec sec min hour day
29 30 31
136.5 10.8 325 day year year
随城市增多，计算时间增加很快。 到31个城市时，要计算325年。
35
1.3 计算复杂性的概念
描述算法的好坏——计算复杂性—— 讨论计算时间与问题规模之间的关系
最优化理论与方法
（现代优化计算方法）
1
内容
概论 递归、分治、贪心、回溯 禁忌搜索、爬山算法 模拟退火、蚁群算法 遗传算法 神经网络 元胞自动机 随机算法
2
背景
传统实际问题的特点 连续性问题——主要以微积分为基础，且问题规模较小
传统的优化方法 追求准确——精确解 理论的完美——结果漂亮 主要方法：线性与非线性规划、动态规划、多目标规划、整 数规划等；排队论、库存论、对策论、决策论等。
数学模型：
min f (x) s.t.g(x) 0,
x D.
目标函数 约束函数 有限点集, 决策变量
7
1.1 组合优化问题
组合优化问题的三参数表示：
(D, F, f ) D :决策变量定义域
F x | x D, g(x) 0,可行域,有限点集
f :目标函数 x F :可行解（点）
s.t. xij 1.i 1, 2, , n, j 1
n
xij 1. j 1, 2, , n,
i 1
xij s 1, 2 s n 1, s 1, 2,
i, js
xij 0,1, i, j 1, 2, , n, i j.
其中
(1.4) 总路长 (1.5) 只从城市i出来一次 (1.6) 只走入城市j一次
现代优化方法 追求满意——近似解 实用性强——解决实际问题
现代优化算法的评价方法 算法复杂性
4
现代优化(启发式)方法种类
禁忌搜索（tabu search） 模拟退火（simulated annealing） 遗传算法（genetic algorithms） 神经网络（neural networks） 蚁群算法（群体（群集）智能，Swarm
其中 B : 装下全部物品需要的箱子， 1, 第i物品装在第b个箱子，
xib 0，第i物品不装在第b个箱子.
14
1.1 组合优化问题
例4 约束机器排序问题（bin packing） n 个加工量为{di|i = 1, 2, ⋯, n} 的产品在
一台机器上加工,机器在第t个时段的工作 能力为ct , 求完成所有产品加工的最少时 段数。
Intelligence） 拉格朗日松弛算法（lagrangean relaxation）
5
1 现代优化计算方法概述
1.1 组合优化问题 1.2 算法 1.3 计算复杂性的概念 1.4 启发式算法
6
1.1 组合优化问题
组合优化（combinatorial optimization）:解决离散问 题的优化问题——运筹学分支。通过数学方法的研究 去寻找离散事件的最优编排、分组、次序或筛选等。
4．高效率与低存储量需求
通常，效率指的是算法执行 时间；存储量指的是算法执行过程 中所需的最大存储空间。两者都与 问题的规模有关。
算法的描述方法.
（1）自然语言 （2）流程图 （3）程序设计语言
例. 求正整数m、n的最大公因数。 解一.
（1）求余数：用m除以n，得余数r(0≤r﹤n)。
（2） 判断余数：若余数r=0，输出n，结束。 否则，转（3）。
9
1.1 组合优化问题
数学模型：
n
max ci xi i 1
(1.1)总价值
n
s.t. ai xi b, i 1
xi 0,1, i 1,, n.
(1.2)包容量限制 (1.3)决策变量
其中xi

1，装第i物品 0，不装第i物品
D 0,1n.
10
1.1 组合优化问题
1．有穷性 对于任意一组合法输入值， 在执行有穷步骤之后一定能结束，即： 算法中的每个步骤都能在有限时间内完成；
2．确定性 对于每种情况下所应执行的 操作，在算法中都有确切的规定，使算法 的执行者或阅读者都能明确其含义及如何 执行。并且在任何条件下，算法都只有一 条执行路径；
3．可行性 算法中的所有操作都必须足 够基本，都可以通过已经实现的基本操作 运算有限次实现之；
总计算量:n! (n 1)!
43
1.3 计算复杂性的概念
实例的输入长度：
设对i, j有dij K , 则 L n(n 1)(log（ 2 K 1） 2) log（ 2 n 1） 2
实例的输入长度是n的多项式函数 枚举法的基本计算量是n的阶乘函数，
随n的增加，比指数函数增加得还快.
44
1.3 计算复杂性的概念
实例I , 实例规模：l(I )，算法A 基本计算总次数：CA (I)
存在函数g ( x)和一个常数，使得对于该问题的任意实例Ｉ 都满足 CA(I) g(l(I )) （ＸＸ）
则二者关系表示为：CA (I ) O(g(l(I ))) g ( x)的性质决定了算法的性能。
以目前二进制计算机中的存储和计算为基础，以 理论的形式系统描述，是评估算法性能的基础。
36
1.3 计算复杂性的概念
问题（problem）：要回答的一般性提问，通常含有若 干个满足一定条件的参数（或自由变量）。可以从两 方面描述： （1）对所有参数的一般性描述； （2）答案（或解）必须满足的性质。
45
1.3 计算复杂性的概念
定义 多项式算法 给定问题P，算法A，对一个实例I，存在多项式 函数g(x)，使（XX ）成立，称算法A对实例I是 多项式算法； 若存在多项式函数g(x)，使（XX ）对问题P的任 意实例I都成立，称算法A为解决该问题P的多项 式算法. 当g(x)为指数函数时，称A为P的指数时间算法。
实例（instance）:给问题的所有参数指定具体值，得 到问题的一个实例。这些具体值称为数据；这些数据 输入计算机所占的空间称为实例的长度（size）.
37
1.3 计算复杂性的概念
一类最优化问题是由一些类似的具体问题（实例） 组成的，每一个具体问题可表达成二元组 （F,C）.
F为可行解集合;C是费用函数，是由F到R（实数集） 的映像。
1．正确性 2. 可读性 3．健壮性 4．高效率与低存储量需求
1．正确性
首先，算法应当满足以特定的“规格说明”方 式给出的需求。
其次，对算法是否“正确”的理解有四个层 次： a．程序中不含语法错误；
b．程序对于几组输入数据能够得出满足要求 的结果；
c．程序对于精心选择的、典型、苛刻且 带有刁难性的几组输入数据能够得出满足 要求的结果； d．程序对于一切合法的输入数据都能得 出满足要求的结果；
, n, (1.7) 在任意城市子集中不形成回路
(1.8) 决策变量
dij:城市i与城市j之间的距离 , s :集合s中元素的个数，
1, 走城市i和城市j之间的路径，
xij


0，不走城市i和城市j之间的路径.
对称距离TSP : dij d ji , i, j
非对称距离TSP : dij d ji , i, j
（3）更新被除数和除数：m←n，n←r，转(1)。
解二.
开始
输入m、n
r=m%n
是 r=0?
否 m←n，n←r
输出n
解三.
Euclid(int m, int n) { int r; while(n!=0)
{ r=m%n; m=n; n=r; }
printf(“%d”, m) }
1.3 计算复杂性的概念
记x的输入规模（编码长度）为l(x)，则 l(x) log2 (| x | 1) 2 其中2是考虑了1个符号位和1个数据分隔位。
39
如何估算 算法的时间复杂度？
算法 = 控制结构 + 原操作
算法的执行时间 =
∑元操作(i)的执行次数×元操作(i)的执行时间
从算法中选取一种对于所研究的 问题来说是 基本操作 的原操作，以 该基本操作 在算法中重复执行的次 数 作为算法运行时间的衡量准则。
问题是在F中找到一个点f*，使对F中任意的f，有 C(f*) C(f),称f*为这一具体问题的最优解（或
全局最优解 ）.
38
1.3 计算复杂性的概念