一. 爬山算法 ( Hill Climbing )
介绍模拟退火前，先介绍爬山算法。爬山算法是一种简单的贪心搜索算法，该算法每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解。
爬山算法实现很简单，其主要缺点是会陷入局部最优解，而不一定能搜索到全局最优解。如图1所示：假设C 点为当前解，爬山算法搜索到A 点这个局部最优解就会停止搜索，因为在A 点无论向那个方向小幅度移动都不能得到更优的解。
图1
二. 模拟退火(SA,Simulated Annealing)思想
爬山法是完完全全的贪心法，每次都鼠目寸光的选择一个当前最优解，因此只能搜索到局部的最优值。模拟退火其实也是一种贪心算法，但是它的搜索过程引入了随机因素。模拟退火算法以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。以图1为例，模拟退火算法在搜索到局部最优解A 后，会以一定的概率接受到E 的移动。也许经过几次这样的不是局部最优的移动后会到达D 点，于是就跳出了局部最大值A 。
模拟退火算法描述：
若J( Y(i+1) )>= J( Y(i) ) (即移动后得到更优解) ，则总是接受该移动
若J( Y(i+1) )
根据热力学的原理，在温度为T 时，出现能量差为dE 的降温的概率为P(dE)，表示为：
P(dE) = exp( dE/(kT) )
其中k 是一个常数，exp 表示自然指数，且dE
随着温度T 的降低，P(dE)会逐渐降低。
我们将一次向较差解的移动看做一次温度跳变过程，我们以概率P(dE)来接受这样的移动。
关于爬山算法与模拟退火，有一个有趣的比喻：
爬山算法：兔子朝着比现在高的地方跳去。它找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是爬山算法，它不能保证局部最优值就是全局最优值。
模拟退火：兔子喝醉了。它随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，它渐渐清醒了并朝最高方向跳去。这就是模拟退火。
下面给出模拟退火的伪代码表示。
三. 模拟退火算法伪代码
代码
/*
* J(y)：在状态y 时的评价函数值
* Y(i)：表示当前状态
* Y(i+1)：表示新的状态
* r： 用于控制降温的快慢
* T： 系统的温度，系统初始应该要处于一个高温的状态
* T_min ：温度的下限，若温度T 达到T_min，则停止搜索
*/
while ( T >
T_min )
{
dE = J( Y(i+1) ) - J( Y(i) ) ;
if ( dE >=0 ) //表达移动后得到更优解，则总是接受移动 Y(i+1) = Y(i) ; //接受从Y(i)到Y(i+1)的移动
else
{
// 函数exp( dE/T )的取值范围是(0,1) ，dE/T越大，则exp( dE/T )也 if ( exp( dE/T ) > random( 0 , 1 ) )
Y(i+1) = Y(i) ; //接受从Y(i)到Y(i+1)的移动
}
T = r * T ; //降温退火 ，0
/*
* 若r 过大，则搜索到全局最优解的可能会较高，但搜索的过程也就较长。若r 过小，则搜索的过程会很快，但最终可能会达到一个局部最优值 */
i ++ ;
}
四. 使用模拟退火算法解决旅行商问题
旅行商问题 ( TSP , Traveling Salesman Problem ) ：有N 个城市，要求从其中某个问题出发，唯一遍历所有城市，再回到出发的城市，求最短的路线。
旅行商问题属于所谓的NP 完全问题，精确的解决TSP 只能通过穷举所有的路径组合，其时间复杂度是O(N!) 。
使用模拟退火算法可以比较快的求出TSP 的一条近似最优路径。（使用遗传算法也是可以的，我将在下一篇文章中介绍）模拟退火解决TSP 的思路：
1. 产生一条新的遍历路径P(i+1)，计算路径P(i+1)的长度L( P(i+1) )
2. 若L(P(i+1))
3. 重复步骤1，2直到满足退出条件
产生新的遍历路径的方法有很多，下面列举其中3种：
1. 随机选择2个节点，交换路径中的这2个节点的顺序。
2. 随机选择2个节点，将路径中这2个节点间的节点顺序逆转。
3. 随机选择3个节点m ，n ，k ，然后将节点m 与n 间的节点移位到节点k 后面。
五. 算法评价
模拟退火算法是一种随机算法，并不一定能找到全局的最优解，可以比较快的找到问题的近似最优解。 如果参数设置得当，模拟退火算法搜索效率比穷举法要高。
模拟退火算法是用来求解最优化问题的算法。比如著名的TSP 问题，函数最大值最小
值问题等等。接下来将以如下几个方面来详细介绍模拟退火算法。
Contents
1. 模拟退火算法认识
2. 模拟退火算法描述
3. 费马点问题求解
4. 最小包含球问题求解
5. 函数最值问题求解
6. TSP问题求解
1. 模拟退火算法认识
爬山算法也是一个用来求解最优化问题的算法，每次都向着当前上升最快的方向往上爬，但是初始化不同可能
会得到不同的局部最优值，模拟退火算法就可能跳出这种局部最优解的限制。模拟退火算法是模拟热力学系统
中的退火过程。在退火过程中是将目标函数作为能量函数。大致过程如下
初始高温 => 温度缓慢下降=> 终止在低温 （这时能量函数达到最小，目标函数最小）
在热力学中的退火过程大致是变温物体缓慢降温而达到分子之间能量最低的状态。设热力学系统S 中有有限个且
离散的n 个状态，状态
这时处于状态的概率为
的能量为，在温度下，经过一段时间达到热平衡，
模拟退火算法也是贪心算法，但是在其过程中引入了随机因素，以一定的概率接受一个比当前解要差的解，并且 这个概率随着时间的推移而逐渐降低。
2. 模拟退火算法描述
若
若
该移动，并且这个概率随时间推移
逐渐降低。这个概率表示为
，即移动后得到更优的解，那么总是接受改移动。 ，即移动后得到更差的解，则以一定的概率接受
由于是退火过程，所以dE
出现降温的概率就越小，由于dE 总是小于0，所以P(dE)取值在0到1之间。伪码如下
3. 费马点问题求解
题目：http://poj.org/problem?id=2420 题意：给n 个点，找出一个点，使这个点到其他所有点的距离之和最小，也就是求费马点。题目：平面上给定n 条线段，找出一个点，使这个点到这n 条线段的距离和最小。
4. 最小包含球问题求解
题目：http://poj.org/problem?id=2069
题意：给定三维空间的n 点，找出一个半径最小的球把这些点全部包围住。
5. 函数最值问题求解
题目：http://acm.hdu.edu.cn/showproblem.php?pid=2899
题意：给出方程
，输入
，其中，求的最小值。
分析：本题可以用经典的二分法求解，这种方法比较简单，就不说了。主要来说模拟退火做法。
6. TSP问题求解
TSP问题是一个NP 问题，但是可以求近似解，通过模拟退火算法实现，代码如下
BloomFilter ——大规模数据处理利器
Bloom Filter是由Bloom 在1970年提出的一种多哈希函数映射的快速查找算法。通常应用在一些需要快速判断某个元素是否属于集合，但是并不严格要求100%正确的场合。
一. 实例
为了说明Bloom Filter存在的重要意义，举一个实例：
假设要你写一个网络蜘蛛（web crawler）。由于网络间的链接错综复杂，蜘蛛在网络间爬行很可能会形成“环”。为了避免形成“环”，就需要知道蜘蛛已经访问过那些URL 。给一个URL ，怎样知道蜘蛛是否已经访问过呢？稍微想想，就会有如下几种方案：
1. 将访问过的URL 保存到数据库。
2. 用HashSet 将访问过的URL 保存起来。那只需接近O(1)的代价就可以查到一个URL 是否被访问过了。
3. URL经过MD5或SHA-1等单向哈希后再保存到HashSet 或数据库。
4. Bit-Map方法。建立一个BitSet ，将每个URL 经过一个哈希函数映射到某一位。
方法1~3都是将访问过的URL 完整保存，方法4则只标记URL 的一个映射位。
以上方法在数据量较小的情况下都能完美解决问题，但是当数据量变得非常庞大时问题就来了。 方法1的缺点：数据量变得非常庞大后关系型数据库查询的效率会变得很低。而且每来一个URL 就启动一次数据库查询是不是太小题大做了？
方法2的缺点：太消耗内存。随着URL 的增多，占用的内存会越来越多。就算只有1亿个URL ，每个URL 只算50个字符，就需要5GB 内存。
方法3：由于字符串经过MD5处理后的信息摘要长度只有128Bit ，SHA-1处理后也只有160Bit ，因此方法3比方法2节省了好几倍的内存。
方法4消耗内存是相对较少的，但缺点是单一哈希函数发生冲突的概率太高。还记得数据结构课上学过的Hash 表冲突的各种解决方法么？若要降低冲突发生的概率到1%，就要将BitSet 的长度设置为URL 个数的100倍。
实质上上面的算法都忽略了一个重要的隐含条件：允许小概率的出错，不一定要100%准确！也就是说少量url 实际上没有没网络蜘蛛访问，而将它们错判为已访问的代价是很小的——大不了少抓几个网页呗。
二. Bloom Filter的算法
废话说到这里，下面引入本篇的主角——Bloom Filter。其实上面方法4的思想已经很接近Bloom Filter 了。方法四的致命缺点是冲突概率高，为了降低冲突的概念，Bloom Filter使用了多个哈希函数，而不是一个。
Bloom Filter算法如下：
创建一个m 位BitSet ，先将所有位初始化为0，然后选择k 个不同的哈希函数。第i 个哈希函数对字符串str 哈希的结果记为h （i ，str ），且h （i ，str ）的范围是0到m-1 。
(1) 加入字符串过程
下面是每个字符串处理的过程，首先是将字符串str“记录”到BitSet 中的过程：
对于字符串str ，分别计算h （1，str ），h （2，str ）…… h（k ，str ）。然后将BitSet 的第h （1，str ）、h （2，str ）…… h（k ，str ）位设为1。
图1.Bloom Filter加入字符串过程
很简单吧？这样就将字符串str 映射到BitSet 中的k 个二进制位了。
(2) 检查字符串是否存在的过程
下面是检查字符串str 是否被BitSet 记录过的过程：
对于字符串str ，分别计算h （1，str ），h （2，str ）…… h（k ，str ）。然后检查BitSet 的第h （1，str ）、h （2，str ）…… h（k ，str ）位是否为1，若其中任何一位不为1则可以判定str 一定没有被记录过。若全部位都是1，则“认为”字符串str 存在。
若一个字符串对应的Bit 不全为1，则可以肯定该字符串一定没有被Bloom Filter记录过。（这是显然的，因为字符串被记录过，其对应的二进制位肯定全部被设为1了）
但是若一个字符串对应的Bit 全为1，实际上是不能100%的肯定该字符串被Bloom Filter记录过的。（因为有可能该字符串的所有位都刚好是被其他字符串所对应）这种将该字符串划分错的情况，称为false positive 。
(3) 删除字符串过程
字符串加入了就被不能删除了，因为删除会影响到其他字符串。实在需要删除字符串的可以使用
Counting bloomfilter(CBF)，这是一种基本Bloom Filter的变体，CBF 将基本Bloom Filter每一个Bit 改为一个计数器，这样就可以实现删除字符串的功能了。
Bloom Filter跟单哈希函数Bit-Map 不同之处在于：Bloom Filter使用了k 个哈希函数，每个字符串跟k 个bit 对应。从而降低了冲突的概率。
三. Bloom Filter参数选择
(1)哈希函数选择
哈希函数的选择对性能的影响应该是很大的，一个好的哈希函数要能近似等概率的将字符串映射到各个Bit 。选择k 个不同的哈希函数比较麻烦，一种简单的方法是选择一个哈希函数，然后送入k 个不同的参数。
(2)Bit数组大小选择
哈希函数个数k 、位数组大小m 、加入的字符串数量n 的关系可以参考参考文献1。该文献证明了对于给定的m 、n ，当 k = ln(2)* m/n 时出错的概率是最小的。
同时该文献还给出特定的k ，m ，n 的出错概率。例如：根据参考文献1，哈希函数个数k 取10，位数组大小m 设为字符串个数n 的20倍时，false positive发生的概率是0.0000889 ，这个概率基本能满足网络爬虫的需求了。
四. Bloom Filter实现代码
下面给出一个简单的Bloom Filter的Java 实现代码：
import java.util.BitSet;
publicclass BloomFilter
{
/* BitSet 初始分配2^24个bit */
privatestaticfinalint DEFAULT_SIZE =1
/* 不同哈希函数的种子，一般应取质数 */
privatestaticfinalint [] seeds =newint [] { 5, 7, 11, 13, 31, 37, 61 }; private BitSet bits =new BitSet(DEFAULT_SIZE);
/* 哈希函数对象 */
private SimpleHash[] func =new SimpleHash[seeds.length];
public BloomFilter()
{
for (int i =0; i
{
func[i] =new SimpleHash(DEFAULT_SIZE, seeds[i]);
}
}
// 将字符串标记到bits 中
publicvoid add(String value)
{
for (SimpleHash f : func)
{
bits.set(f.hash(value), true );
}
}
//判断字符串是否已经被bits 标记
publicboolean contains(String value)
{
if (value ==null )
{
returnfalse ;
}
boolean ret =true ;
for (SimpleHash f : func)
{
ret = ret && bits.get(f.hash(value));
}
return ret;
}
/* 哈希函数类 */
publicstaticclass SimpleHash
{
privateint cap;
privateint seed;
public SimpleHash(int cap, int seed)
{
this .cap = cap;
this .seed = seed;
}
//hash函数，采用简单的加权和hash
publicint hash(String value)
{
int result =0;
int len = value.length();
for (int i =0; i
{
result = seed * result + value.charAt(i);
}
return (cap -1) & result;
}
}
}
模拟退火算法
模拟退火算法心得
本文属于原创，make by 刘润佳，转载请注明出处。
由于在做一些Sat （可满足性问题）的事情，所以也尝试了多种方法来求解，其中模拟退火算法是一种不完全方法。首先看看模拟退火算法的思想：
一、模拟退火算法的起源
1）它受益于物理退火过程
加温过程
等温过程
冷却（退火）过程
2）等温下热平衡过程可用Monte Carlo方法模拟，计算量大。
3）1953年，Metropolis 提出重要性采样法，即以概率接受新状态，称Metropolis 准则，计算量相对Monte Carlo方法显著减少。
4）1983年，Kirkpatrick 等提出模拟退火算法，并将其应用于组合优化问题的求解。
二、模拟退火的基本思想
它可以分解为解空间、目标函数和初始解三部分。
∙
∙
∙
∙
∙
∙
∙ (1) 初始化：初始温度T(充分大) ，初始解状态S(是算法迭代的起点) ， 每个T 值的迭代次数L (2) 对k=1，……，L 做第(3)至第6步： (3) 产生新解S′ (4) 计算增量Δt′=C(S′)-C(S)，其中C(S)为评价函数 (5) 若Δt′0，然后转第2步。
三、模拟退火算法的流程
四、需注意因素
五、本人的心得
在使用模拟退火算法求解Sat 问题时，遇到了几个问题，觉得有必要提出来探讨一下，这也是模拟退火算法需要注意的地方：
1）温度的设定及其变化函数；
2）在每个温度值下，进行尝试的次数；
3）评估函数选取问题
一. 爬山算法 ( Hill Climbing )
介绍模拟退火前，先介绍爬山算法。爬山算法是一种简单的贪心搜索算法，该算法每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解。
爬山算法实现很简单，其主要缺点是会陷入局部最优解，而不一定能搜索到全局最优解。如图1所示：假设C 点为当前解，爬山算法搜索到A 点这个局部最优解就会停止搜索，因为在A 点无论向那个方向小幅度移动都不能得到更优的解。
图1
二. 模拟退火(SA,Simulated Annealing)思想
爬山法是完完全全的贪心法，每次都鼠目寸光的选择一个当前最优解，因此只能搜索到局部的最优值。模拟退火其实也是一种贪心算法，但是它的搜索过程引入了随机因素。模拟退火算法以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。以图1为例，模拟退火算法在搜索到局部最优解A 后，会以一定的概率接受到E 的移动。也许经过几次这样的不是局部最优的移动后会到达D 点，于是就跳出了局部最大值A 。
模拟退火算法描述：
若J( Y(i+1) )>= J( Y(i) ) (即移动后得到更优解) ，则总是接受该移动
若J( Y(i+1) )
根据热力学的原理，在温度为T 时，出现能量差为dE 的降温的概率为P(dE)，表示为：
P(dE) = exp( dE/(kT) )
其中k 是一个常数，exp 表示自然指数，且dE
随着温度T 的降低，P(dE)会逐渐降低。
我们将一次向较差解的移动看做一次温度跳变过程，我们以概率P(dE)来接受这样的移动。
关于爬山算法与模拟退火，有一个有趣的比喻：
爬山算法：兔子朝着比现在高的地方跳去。它找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是爬山算法，它不能保证局部最优值就是全局最优值。
模拟退火：兔子喝醉了。它随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，它渐渐清醒了并朝最高方向跳去。这就是模拟退火。
下面给出模拟退火的伪代码表示。
三. 模拟退火算法伪代码
代码
/*
* J(y)：在状态y 时的评价函数值
* Y(i)：表示当前状态
* Y(i+1)：表示新的状态
* r： 用于控制降温的快慢
* T： 系统的温度，系统初始应该要处于一个高温的状态
* T_min ：温度的下限，若温度T 达到T_min，则停止搜索
*/
while ( T >
T_min )
{
dE = J( Y(i+1) ) - J( Y(i) ) ;
if ( dE >=0 ) //表达移动后得到更优解，则总是接受移动 Y(i+1) = Y(i) ; //接受从Y(i)到Y(i+1)的移动
else
{
// 函数exp( dE/T )的取值范围是(0,1) ，dE/T越大，则exp( dE/T )也 if ( exp( dE/T ) > random( 0 , 1 ) )
Y(i+1) = Y(i) ; //接受从Y(i)到Y(i+1)的移动
}
T = r * T ; //降温退火 ，0
/*
* 若r 过大，则搜索到全局最优解的可能会较高，但搜索的过程也就较长。若r 过小，则搜索的过程会很快，但最终可能会达到一个局部最优值 */
i ++ ;
}
四. 使用模拟退火算法解决旅行商问题
旅行商问题 ( TSP , Traveling Salesman Problem ) ：有N 个城市，要求从其中某个问题出发，唯一遍历所有城市，再回到出发的城市，求最短的路线。
旅行商问题属于所谓的NP 完全问题，精确的解决TSP 只能通过穷举所有的路径组合，其时间复杂度是O(N!) 。
使用模拟退火算法可以比较快的求出TSP 的一条近似最优路径。（使用遗传算法也是可以的，我将在下一篇文章中介绍）模拟退火解决TSP 的思路：
1. 产生一条新的遍历路径P(i+1)，计算路径P(i+1)的长度L( P(i+1) )
2. 若L(P(i+1))
3. 重复步骤1，2直到满足退出条件
产生新的遍历路径的方法有很多，下面列举其中3种：
1. 随机选择2个节点，交换路径中的这2个节点的顺序。
2. 随机选择2个节点，将路径中这2个节点间的节点顺序逆转。
3. 随机选择3个节点m ，n ，k ，然后将节点m 与n 间的节点移位到节点k 后面。
五. 算法评价
模拟退火算法是一种随机算法，并不一定能找到全局的最优解，可以比较快的找到问题的近似最优解。 如果参数设置得当，模拟退火算法搜索效率比穷举法要高。
模拟退火算法是用来求解最优化问题的算法。比如著名的TSP 问题，函数最大值最小
值问题等等。接下来将以如下几个方面来详细介绍模拟退火算法。
Contents
1. 模拟退火算法认识
2. 模拟退火算法描述
3. 费马点问题求解
4. 最小包含球问题求解
5. 函数最值问题求解
6. TSP问题求解
1. 模拟退火算法认识
爬山算法也是一个用来求解最优化问题的算法，每次都向着当前上升最快的方向往上爬，但是初始化不同可能
会得到不同的局部最优值，模拟退火算法就可能跳出这种局部最优解的限制。模拟退火算法是模拟热力学系统
中的退火过程。在退火过程中是将目标函数作为能量函数。大致过程如下
初始高温 => 温度缓慢下降=> 终止在低温 （这时能量函数达到最小，目标函数最小）
在热力学中的退火过程大致是变温物体缓慢降温而达到分子之间能量最低的状态。设热力学系统S 中有有限个且
离散的n 个状态，状态
这时处于状态的概率为
的能量为，在温度下，经过一段时间达到热平衡，
模拟退火算法也是贪心算法，但是在其过程中引入了随机因素，以一定的概率接受一个比当前解要差的解，并且 这个概率随着时间的推移而逐渐降低。
2. 模拟退火算法描述
若
若
该移动，并且这个概率随时间推移
逐渐降低。这个概率表示为
，即移动后得到更优的解，那么总是接受改移动。 ，即移动后得到更差的解，则以一定的概率接受
由于是退火过程，所以dE
出现降温的概率就越小，由于dE 总是小于0，所以P(dE)取值在0到1之间。伪码如下
3. 费马点问题求解
题目：http://poj.org/problem?id=2420 题意：给n 个点，找出一个点，使这个点到其他所有点的距离之和最小，也就是求费马点。题目：平面上给定n 条线段，找出一个点，使这个点到这n 条线段的距离和最小。
4. 最小包含球问题求解
题目：http://poj.org/problem?id=2069
题意：给定三维空间的n 点，找出一个半径最小的球把这些点全部包围住。
5. 函数最值问题求解
题目：http://acm.hdu.edu.cn/showproblem.php?pid=2899
题意：给出方程
，输入
，其中，求的最小值。
分析：本题可以用经典的二分法求解，这种方法比较简单，就不说了。主要来说模拟退火做法。
6. TSP问题求解
TSP问题是一个NP 问题，但是可以求近似解，通过模拟退火算法实现，代码如下
BloomFilter ——大规模数据处理利器
Bloom Filter是由Bloom 在1970年提出的一种多哈希函数映射的快速查找算法。通常应用在一些需要快速判断某个元素是否属于集合，但是并不严格要求100%正确的场合。
一. 实例
为了说明Bloom Filter存在的重要意义，举一个实例：
假设要你写一个网络蜘蛛（web crawler）。由于网络间的链接错综复杂，蜘蛛在网络间爬行很可能会形成“环”。为了避免形成“环”，就需要知道蜘蛛已经访问过那些URL 。给一个URL ，怎样知道蜘蛛是否已经访问过呢？稍微想想，就会有如下几种方案：
1. 将访问过的URL 保存到数据库。
2. 用HashSet 将访问过的URL 保存起来。那只需接近O(1)的代价就可以查到一个URL 是否被访问过了。
3. URL经过MD5或SHA-1等单向哈希后再保存到HashSet 或数据库。
4. Bit-Map方法。建立一个BitSet ，将每个URL 经过一个哈希函数映射到某一位。
方法1~3都是将访问过的URL 完整保存，方法4则只标记URL 的一个映射位。
以上方法在数据量较小的情况下都能完美解决问题，但是当数据量变得非常庞大时问题就来了。 方法1的缺点：数据量变得非常庞大后关系型数据库查询的效率会变得很低。而且每来一个URL 就启动一次数据库查询是不是太小题大做了？
方法2的缺点：太消耗内存。随着URL 的增多，占用的内存会越来越多。就算只有1亿个URL ，每个URL 只算50个字符，就需要5GB 内存。
方法3：由于字符串经过MD5处理后的信息摘要长度只有128Bit ，SHA-1处理后也只有160Bit ，因此方法3比方法2节省了好几倍的内存。
方法4消耗内存是相对较少的，但缺点是单一哈希函数发生冲突的概率太高。还记得数据结构课上学过的Hash 表冲突的各种解决方法么？若要降低冲突发生的概率到1%，就要将BitSet 的长度设置为URL 个数的100倍。
实质上上面的算法都忽略了一个重要的隐含条件：允许小概率的出错，不一定要100%准确！也就是说少量url 实际上没有没网络蜘蛛访问，而将它们错判为已访问的代价是很小的——大不了少抓几个网页呗。
二. Bloom Filter的算法
废话说到这里，下面引入本篇的主角——Bloom Filter。其实上面方法4的思想已经很接近Bloom Filter 了。方法四的致命缺点是冲突概率高，为了降低冲突的概念，Bloom Filter使用了多个哈希函数，而不是一个。
Bloom Filter算法如下：
创建一个m 位BitSet ，先将所有位初始化为0，然后选择k 个不同的哈希函数。第i 个哈希函数对字符串str 哈希的结果记为h （i ，str ），且h （i ，str ）的范围是0到m-1 。
(1) 加入字符串过程
下面是每个字符串处理的过程，首先是将字符串str“记录”到BitSet 中的过程：
对于字符串str ，分别计算h （1，str ），h （2，str ）…… h（k ，str ）。然后将BitSet 的第h （1，str ）、h （2，str ）…… h（k ，str ）位设为1。
图1.Bloom Filter加入字符串过程
很简单吧？这样就将字符串str 映射到BitSet 中的k 个二进制位了。
(2) 检查字符串是否存在的过程
下面是检查字符串str 是否被BitSet 记录过的过程：
对于字符串str ，分别计算h （1，str ），h （2，str ）…… h（k ，str ）。然后检查BitSet 的第h （1，str ）、h （2，str ）…… h（k ，str ）位是否为1，若其中任何一位不为1则可以判定str 一定没有被记录过。若全部位都是1，则“认为”字符串str 存在。
若一个字符串对应的Bit 不全为1，则可以肯定该字符串一定没有被Bloom Filter记录过。（这是显然的，因为字符串被记录过，其对应的二进制位肯定全部被设为1了）
但是若一个字符串对应的Bit 全为1，实际上是不能100%的肯定该字符串被Bloom Filter记录过的。（因为有可能该字符串的所有位都刚好是被其他字符串所对应）这种将该字符串划分错的情况，称为false positive 。
(3) 删除字符串过程
字符串加入了就被不能删除了，因为删除会影响到其他字符串。实在需要删除字符串的可以使用
Counting bloomfilter(CBF)，这是一种基本Bloom Filter的变体，CBF 将基本Bloom Filter每一个Bit 改为一个计数器，这样就可以实现删除字符串的功能了。
Bloom Filter跟单哈希函数Bit-Map 不同之处在于：Bloom Filter使用了k 个哈希函数，每个字符串跟k 个bit 对应。从而降低了冲突的概率。
三. Bloom Filter参数选择
(1)哈希函数选择
哈希函数的选择对性能的影响应该是很大的，一个好的哈希函数要能近似等概率的将字符串映射到各个Bit 。选择k 个不同的哈希函数比较麻烦，一种简单的方法是选择一个哈希函数，然后送入k 个不同的参数。
(2)Bit数组大小选择
哈希函数个数k 、位数组大小m 、加入的字符串数量n 的关系可以参考参考文献1。该文献证明了对于给定的m 、n ，当 k = ln(2)* m/n 时出错的概率是最小的。
同时该文献还给出特定的k ，m ，n 的出错概率。例如：根据参考文献1，哈希函数个数k 取10，位数组大小m 设为字符串个数n 的20倍时，false positive发生的概率是0.0000889 ，这个概率基本能满足网络爬虫的需求了。
四. Bloom Filter实现代码
下面给出一个简单的Bloom Filter的Java 实现代码：
import java.util.BitSet;
publicclass BloomFilter
{
/* BitSet 初始分配2^24个bit */
privatestaticfinalint DEFAULT_SIZE =1
/* 不同哈希函数的种子，一般应取质数 */
privatestaticfinalint [] seeds =newint [] { 5, 7, 11, 13, 31, 37, 61 }; private BitSet bits =new BitSet(DEFAULT_SIZE);
/* 哈希函数对象 */
private SimpleHash[] func =new SimpleHash[seeds.length];
public BloomFilter()
{
for (int i =0; i
{
func[i] =new SimpleHash(DEFAULT_SIZE, seeds[i]);
}
}
// 将字符串标记到bits 中
publicvoid add(String value)
{
for (SimpleHash f : func)
{
bits.set(f.hash(value), true );
}
}
//判断字符串是否已经被bits 标记
publicboolean contains(String value)
{
if (value ==null )
{
returnfalse ;
}
boolean ret =true ;
for (SimpleHash f : func)
{
ret = ret && bits.get(f.hash(value));
}
return ret;
}
/* 哈希函数类 */
publicstaticclass SimpleHash
{
privateint cap;
privateint seed;
public SimpleHash(int cap, int seed)
{
this .cap = cap;
this .seed = seed;
}
//hash函数，采用简单的加权和hash
publicint hash(String value)
{
int result =0;
int len = value.length();
for (int i =0; i
{
result = seed * result + value.charAt(i);
}
return (cap -1) & result;
}
}
}
模拟退火算法
模拟退火算法心得
本文属于原创，make by 刘润佳，转载请注明出处。
由于在做一些Sat （可满足性问题）的事情，所以也尝试了多种方法来求解，其中模拟退火算法是一种不完全方法。首先看看模拟退火算法的思想：
一、模拟退火算法的起源
1）它受益于物理退火过程
加温过程
等温过程
冷却（退火）过程
2）等温下热平衡过程可用Monte Carlo方法模拟，计算量大。
3）1953年，Metropolis 提出重要性采样法，即以概率接受新状态，称Metropolis 准则，计算量相对Monte Carlo方法显著减少。
4）1983年，Kirkpatrick 等提出模拟退火算法，并将其应用于组合优化问题的求解。
二、模拟退火的基本思想
它可以分解为解空间、目标函数和初始解三部分。
∙
∙
∙
∙
∙
∙
∙ (1) 初始化：初始温度T(充分大) ，初始解状态S(是算法迭代的起点) ， 每个T 值的迭代次数L (2) 对k=1，……，L 做第(3)至第6步： (3) 产生新解S′ (4) 计算增量Δt′=C(S′)-C(S)，其中C(S)为评价函数 (5) 若Δt′0，然后转第2步。
三、模拟退火算法的流程
四、需注意因素
五、本人的心得
在使用模拟退火算法求解Sat 问题时，遇到了几个问题，觉得有必要提出来探讨一下，这也是模拟退火算法需要注意的地方：
1）温度的设定及其变化函数；
2）在每个温度值下，进行尝试的次数；
3）评估函数选取问题