Local Search
常用的local search 算法有 爬山算法, 模拟退火算法, 遗传算法和禁忌查找等, 主要是用来解决一些NP问题。
local seach 是一种meta-heuristic , 就是一种启发示找查。大致思想是:
- 给定一个数量的初始值状态,也就当前状态
- 根据当前状态以一定的规则生成一定数量的相邻状态
- 根据一定规则用相邻状态来代替当前状态 (比如相邻状态值优于当前状态)
- 重复(2),(3)直到找到一个满意的解或者查找时间用完!
对于local search 最重要的就是以下几个方面:
1). 状态的表示, 用什么的结构表示状态, 就在一定程度上决定后面生成相邻状态难易和查找空间大小
2). 相邻状态的生成的方法
3). 参数设置(如找查的初始解,模拟退火的初始温度, 温度的变化率,禁忌表的长度等), 不同问题参数设置可能不一样!
爬山算法
这几个算法中爬山算法计算时间最少,当然它快的是有代价的, 它的原理就是在步骤(3)中,找查当前状态中所有的相邻状态,然后用最好的相邻状态代替当前状态, 它的缺点就是容易出现局部最小解! 但是它仍然在一些实时性要求比较高的问题用的比较多吧!
爬山算法java举例
爬山算法图解
退火算法
与爬山算法相比较,退火算法可以以一定的概率接受一些状态值比当前状态值差的状态, 这个就有可能escape局部最小的状态! 这个概率和当前的"温度"有关,当查找越往后, "温度"就越低, 这样接受比当前状态值差的可能性就越小!
名词解析
在算法中经常碰到P问题、NP问题、NP完全问题和NP难问题，为什么我们要研究这个？因为计算机处理的输入常常不是那么几十个几千个那么一点点，想象一下，当计算机处理的数据达到100万个的时候，时间复杂度为o(n^2) 和o(e^n) 的算法，所需的运行次数简直是天壤之别，o(e^n)指数级的可能运行好几天都没法完成任务，所以我们才要研究一个问题是否存在多项式时间算法。而我们也只在乎一个问题是否存在多项式算法，因为一个时间复杂度比多项式算法还要复杂的算法研究起来是没有任何实际意义的。
以冒泡排序为例，我们知道了，在排序这个大问题里，是可以找到一种时间复杂度为多项式o(n^2)的算法(如冒泡排序法)来求解排序问题的，所以我们说排序问题是一个有多项式时间算法的问题。
排序算法
P类问题
P类问题：存在多项式时间算法的问题 (P：polynominal，多项式)。
NP类问题
NP类问题：能在多项式时间内验证得出一个正确解的问 (NP:Nondeterministic polynominal，非确定性多项式)。
P类问题是NP问题的子集，因为存在多项式时间解法的问题，总能在多项式时间内验证他。
注意定义，这里是验证。NP类问题，我用个人的俗话理解就是，不知道这个问题是不是存在多项式时间内的算法，所以叫non-deterministic非确定性，但是我们可以在多项式时间内验证并得出这个问题的一个正确解。举个例子:
著名的NP类问题：旅行商问题(TSP)。即有一个推销员，要到n个城市推销商品，他要找出一个包含所有n个城市的环路，这个环路路径小于a。我们知道这个问题如果单纯的用枚举法来列举的话会有(n-1)! 种，已经不是多项式时间的算法了，(注：阶乘算法比多项式的复杂)。那怎么办呢？我们可以用猜的，假设我人品好，猜几次就猜中了一条小于长度a的路径，我画画画画，好的，我得到了一条路径小于a的环路，问题解决了，皆大欢喜。可是，我不可能每次都猜的那么准，也许我要猜完所有种呢？所以我们说，这是一个NP类问题。也就是，我们能在多项式的时间内验证并得出问题的正确解，可是我们却不知道该问题是否存在一个多项式时间的算法，每次都能解决他(注意，这里是不知道，不是不存在)。是否所有能在多项式时间内验证得出正确解的问题，都是具有多项式时间算法的问题呢。答案是有的存在有的不存在。
NPC问题
NPC问题:如果所有np问题都能在多项式时间内转化为他，则称该np问题为npc问题(NPC:NP complete又叫NP完全问题)
NPC问题是NP问题的子集。
对于同一类的所有的NP类问题，若他们都可以在多项式时间内约化成最难的一个NP类问题，（我们直观的认为，被约化成的问题应具有比前一个问题更复杂的时间复杂度）当我们针对这个时间复杂度最高的超级NP问题要是能找到他的多项式时间算法的话，那就等于变向的证明了其下的所有问题都是存在多项式算法的，即NP=P！！！！
NPH问题
NPH问题：我们又叫NP难问题，他不是一个NP问题，然后所有的NPC问题都可以在多项式时间内转化为他的话，我们就叫他NPH（hard）问题。
网友评论