Algorithm

退火算法

模拟退火算法描述：

若J( Y(i+1) )>= J( Y(i) ) (即移动后得到更优解)，则总是接受该移动

若J( Y(i+1) )< J( Y(i) ) (即移动后的解比当前解要差)，则以一定的概率接受移动，而且这个概率随着时间推移逐渐降低（逐渐降低才能趋向稳定）

爬山算法：兔子朝着比现在高的地方跳去。它找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是爬山算法，它不能保证局部最优值就是全局最优值。

模拟退火：兔子喝醉了。它随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，它渐渐清醒了并朝最高方向跳去。这就是模拟退火。

Rabin-karp string searching

$$ f(x) = m_0x^{n-1} + m_1x^{n-2} + \cdots + m_{n-1} $$

如要在一个字符串中查找cdef, 则n=4, x=128

下图中假定被查找的字符串只出现10个字母，或者另加一个参数mod=10

$$ (A * B) mod C = ((A mod C) * (B mod C)) mod C $$

Murmurhash3

MurmurHash是一种经过广泛测试且速度很快的非加密哈希函数。名字来自两个基本运算，即multiply和rotate（尽管该算法实际上使用shift和xor而不是rotate）。

加密哈希函数旨在保证安全性，很难找到碰撞。非加密哈希函数只是试图避免非恶意输入的冲突。作为较弱担保的交换，它们通常更快。

Jaccard distance

$$ JDist(X, Y) = 1 - JSim(X, Y) $$

---