蚁群优化算法讲稿.ppt

数学系凌军第Ⅰ篇组合优化问题与元启发式算法
第Ⅱ篇ACO原理及其实现

第Ⅲ篇ACO理论及应用第Ⅰ篇组合优化问题与元启发式算法第Ⅰ篇组合优化问题与元启发式算法1.2计算的复杂度
通常，对算法效率在理论上的探讨又称为算法的事前估计，可分为算法的时间复杂度分析和空间复杂度分析。

定义1.1算法空间复杂度是指算法执行时间内所占用的存储单元的大小。

定义1.2算法的时间复杂度是指算法执行基本操作的次数。这里我们将求解该问题的所有关键操作（如加、减、乘、除、比较等运算）指定为基本操作。
定义1.3最差时间复杂度指的是对于每个可能的输入规模为的问题算法求解该问题时找到一个解所需的最长时间。
一个算法的最差时间复杂度常常采用符号来表示。给定两个函数和，若存在两个正常数与，对一切的
时有则称是以为界的，那么函数的最差时间复杂度就为。换句话说，符号给出了算法在最差时间复杂度上的渐进上限值，它表示的是一个数量级的概念。
若一个算法对应的时间复杂度为，而是一个多项式函数，则称该算法为多项式时间算法；若不是多项式则称该算法为指数级时间算法。
P、NP、NP-C、NP-hard问题描述图灵（A.Turing）1912年出生于伦敦。他1936年的论文《论可计算数及其在判定问题中的应用》是阐明现代计算与计算机原理的开山之作。论文围绕着一个基础数学问题：只要有足够的计算时间数学函数是否都能经过有限次机械步骤得出解答？为了弄清楚计算机能够解决哪些问题，他提出了后来被称作“图灵机”的可计算性理论。1937年，他的论文《基于序数的逻辑系统》进一步展开了关于这个问题的逻辑探索。定义1.4图灵机图灵机概念最早由英国数学家Turing提出，其本质是由两部分组成：一部分是一个无限长的磁带，磁带被分割成一个个的小方格，每个小方格装有符号‘0’或‘1’；另一部分是检测头，它能沿着磁带前后移动，一次移动一个小方格，并能读出当前小方格的符号。检测头可以不改变小方格的值，也能将新值写进小方格。在操作的每一步，我们假定检测头处于有限设置中的一个，称其为状态。检测头可能采取的行动：例、用图灵机来计算1加2图灵机是对算法进行分析和研究算法复杂度的
得力工具，可分为确定性单带图灵（deterministic

one-tapeTuringmachine,DTM）和非确定性单带
图灵机（nondeterministiconetapeTuringmaching
NDTM）两大类。
一个DTM程序应包括以下信息：非确定性单带图灵机NDTM完全是一种假象的机
器，通常多用猜想模块来对其进行描述。定义1.5实例实例是问题的特殊表现，是确
定了描述问题特性的所有参数的问题，其中参数
值称为数据，这些数据占用计算机的空间称为数
据实例的输入长度。P类问题的每个实例只有“是”或“否”两种回答，
并称肯定回答为“是”实例；称否定回答为“否”实例。定义1.7NP(non-deterministicpoly-nominal)类问题若存在一个多项式函数和一个验证算法，对一
类判定问题的任何一个“是”回答，满足其输入长度
不超过，其中为的输入长度，且验证
算法中为的“是”回答的计算时间不超过，则
称判定问题为非多项式确定问题，简称NP类问题。
NP类问题是所有可用NDTM在多项式时间内求解的
判定问题的集合。判定问题是否属于NP类问题的关键是对“是”的
判定实例是否存在满足上述条件的一个字符串和
算法，其中字符串在此可理解为问题的一个解，
而定义中没有强调字符串和算法是如何得到的。
能用DTM在多项式时间内解决的P类问题，也一
定能用NDTM在多项式时间内加以解决，这个关
系可表示为。然而，在当前的计算复杂度理论中，尚没有
解决是否兼属P类或NP类的问题，即证明
的难度和证明的难度同样大。定义1.8给定问题和，若存在一个多项式
函数和一个字符串满足：
（1）对于的任何一个实例，在其输入长
度的多项式时间内构造的一个实例，
使其长度不超过;
（2）由此构造使得实例和的解一一对应
且为的“是”回答的充要条件为对应的解是
的一个“是”回答。
则称可以转换为。定义1.9给定判定问题和，若存在多项
式函数和，使得对的任何一个实例
在多项式时间内构造的一个实例，其输入长度
不超过，并对的任何一个算法，都存
在问题的一个算法，使得计算时间满足：

则称可多项式归纳为。由此可见，若问题存在多项式时间算法，
则问题一定存在多项式时间算法。且对的
一个算法，可以按照如下步骤构造的算法：
（1）对问题的任何一个实例，先用多项式
时间构造问题的一个实例；
（2）调用算法求解，此步计算时间为

如此构造的算法对问题的任何一个实例的
计算时间不超过定义1.10NP-C(NP-comlete)类问题它是NP
类问题中最困难的一类问题。所