1 Webb.S 一、（搜索）双向广度搜索
广度搜索虽然可以得到最优解，但是其空间消耗增长太快。但如果从正反两个方向进行广度搜索，理想情况下可以减少二分之一的搜索量，从而提高搜索速度。
范例：有N个黑白棋子排成一派，中间任意两个位置有两个连续的空格。每次空格可以与序列中的某两个棋子交换位置，且两子的次序不变。要求出入长度为length的一个初始状态和一个目标状态，求出最少的转化步数。 问题分析：该题要求求出最少的转化步数，但如果直接使用广度搜索，很容易产生数据溢出。但如果从初始状态和目标状态两个方向同时进行扩展，如果两棵解答树在某个节点第一次发生重合，则该节点所连接的两条路径所拼成的路径就是最优解。 对广度搜索算法的改进：
１。添加一张节点表，作为反向扩展表。
２。在while循环体中在正向扩展代码后加入反向扩展代码，其扩展过程不能与正向过程共享一个for循环。
３。在正向扩展出一个节点后，需在反向表中查找是否有重合节点。反向扩展时 与之相同。
对双向广度搜索算法的改进：
略微修改一下控制结构，每次while循环时只扩展正反两个方向中节点数目较少的一个，可以使两边的发展速度保持一定的平衡，从而减少总扩展节点的个数，加快搜索速度。
二、（搜索）分支定界
分支定界实际上是A*算法的一种雏形，其对于每个扩展出来的节点给出一个预期值，如果这个预期值不如当前已经搜索出来的结果好的话，则将这个节点(包括其子节点)从解答树中删去，从而达到加快搜索速度的目的。
范例：在一个商店中购物，设第I种商品的价格为Ci。但商店提供一种折扣，即给出一组商品的组合，如果一次性购买了这一组商品，则可以享受较优惠的价格。现在给出一张购买清单和商店所提供的折扣清单，要求利用这些折扣，使所付款最少。
问题分析：显然，折扣使用的顺序与最终结果无关，所以可以先将所有的折扣按折扣率从大到小排序，然后采用回溯法的控制结构，对每个折扣从其最大可能使用次数向零递减搜索，设A为以打完折扣后优惠的价格，C为当前未打折扣的商品零售价之和，则其预期值为A+a*C，其中a为下一个折扣的折扣率。如当前已是最后一个折扣，则a=1。 对回溯算法的改进：
１。添加一个全局变量BestAnswer，记录当前最优解。
２。在每次生成一个节点时，计算其预期值，并与BestAnswer比较。如果不好，则调用回溯过程。
三、（hash）KR算法——字符串匹配
KR算法对模式串和循环中每一次要匹配的子串按一定的hash函数求值，如果hash值相同，才进一步比较这两个串是否真正相等。
举例说一下KR算法吧：在我写的这个总结中，各个算法使用的例子都一样，随便找的； 模式串 pattern=\ 文本串 text=\pattern 长度记 pattern_len
1
2 Webb.S
预备阶段就是计算pattern的hash，长度为6，那么hash_pattern='p'*2^5+'a'*2^4+'p'*2^3+'p'*2^2+'a'*2^1+'r'*2^0
当然，这里使用的是字符的ascii值
也计算text前六个字符的hash，我们记第一个为hash_text[0]
然后就开始向前移动了，在移动时，要重新计算当前与模式串对应的串的hash值，这个工作叫rehash
初始化 i=0
如果 hash_pattern与hash_text[i]相等，返回 i
如果不等 计算新的hash值，就是text[i..i+patten_len]的hash， 当然这里不会像第一次那样全部计算，方法是
上一次计算的值减去上一次匹配时串的第一个字符乘以 2^pattern_len ,然后乘以2，再加上新加入比较的字符值
根据公式可以很清晰看出来。
就是减去计算中的第一项，把剩下的乘以2，然后在末尾加入新增的字符值
四、（图论）Floyd求最小环
floyd求最小环是一种相对效率较高的算法。它的改进算法就是在外层循环n次，每一次都用k作中转点求出一个最短路，为下一次求最小环做好了准备。核心代码如下： min:=1 shl 30;
for k:=1 to n do begin for i:=1 to k-1 do for j:=1 to k-1 do
if (i<>j)and(f[i,j]+map[k,i]+map[j,k] if (i<>j)and(i<>k)and(k<>j) and(f[i,k]+f[k,j] 对于求最小环部分，可以这样来理解，当前的f[i,j]是用1...k-1作中转点求出来的，那么必然最短路不包含k点，现在如果i,j到k有边，且构成的环更优，那么更新min。还有点需要注意就是方向性，因为在有向图中边是单向的，所以需要最小环的构成情况： min=f[i,j]+map[j,k]+map[k,i] 首先f[i,j]是i到j的最短路，然后j到k有边，k到i有边，构成环。 对于floyd求最短路部分，当前已经用k作中转点求出了最小环，那么现在的k已经失去了作中转点的作用，于是可以构成最短路的一部分，为下一次用k+1作中转点求出最短路。 这两个部分就是floyd求最小环的精华所在，每次的floyd都为下次求min做好了铺垫，不多不少，没有冗余，很完美的算法。 五、（优化）位运算 === 1. and运算 === and运算通常用于二进制取位操作，例如一个数 and 1的结果就是取二进制的最末位。这可以用来判断一个整数的奇偶，二进制的最末位为0表示该数为偶数，最末位为1表示该 2 3 Webb.S 数为奇数. === 2. or运算 === or运算通常用于二进制特定位上的无条件赋值，例如一个数or 1的结果就是把二进制最末位强行变成1。如果需要把二进制最末位变成0，对这个数or 1之后再减一就可以了，其实际意义就是把这个数强行变成最接近的偶数。 === 3. xor运算 === xor运算通常用于对二进制的特定一位进行取反操作，因为异或可以这样定义：0和1异或0都不变，异或1则取反。 xor 运算的逆运算是它本身，也就是说两次异或同一个数最后结果不变，即(a xor b) xor b = a。xor运算可以用于简单的加密，比如我想对我MM说1314520，但怕别人知道，于是双方约定拿我的生日19880516作为密钥。1314520 xor 19880516 = 20665500，我就把20665500告诉MM。MM再次计算20665500 xor 19880516的值，得到1314520，于是她就明白了我的企图。 === 4. shl运算 === a shl b就表示把a转为二进制后左移b位（在后面添b个0）。例如100的二进制为1100100，而110010000转成十进制是400，那么100 shl 2 = 400。可以看出，a shl b的值实际上就是a乘以2的b次方，因为在二进制数后添一个0就相当于该数乘以2。 通常认为a shl 1比a * 2更快，因为前者是更底层一些的操作。因此程序中乘以2的操作请尽量用左移一位来代替。 定义一些常量可能会用到shl运算。你可以方便地用1 shl 16 - 1来表示65535。很多算法和数据结构要求数据规模必须是2的幂，此时可以用shl来定义Max_N等常量。 === 5. shr运算 === 和 shl相似，a shr b表示二进制右移b位（去掉末b位），相当于a除以2的b次方（取整）。我们也经常用shr 1来代替div 2，比如二分查找、堆的插入操作等等。想办法用shr代替除法运算可以使程序效率大大提高。最大公约数的二进制算法用除以2操作来代替慢得出奇的mod运 算，效率可以提高60%。 功能 | 示例 | 位运算 --------------------------------+---------------------------------------+-------------------- 去掉最后一位 | (101101->10110) | x shr 1 在最后加一个0 | (101101->1011010) | x shl 1 在最后加一个1 | (101101->1011011) | x shl 1+1 把最后一位变成1 | (101100->101101) | x or 1 把最后一位变成0 | (101101->101100) | x or 1-1 最后一位取反 | (101101->101100) | x xor 1 把右数第k位变成1 | (101001->101101,k=3) | x or (1 shl (k-1)) 把右数第k位变成0 | (101101->101001,k=3) | x and not (1 shl (k-1)) 右数第k位取反 | (101001->101101,k=3) | x xor (1 shl (k-1)) 取末三位 | (1101101->101) | x and 7 取末k位 | (1101101->1101,k=5) | x and (1 shl k-1) 取右数第k位 | (1101101->1,k=4) | x shr (k-1) and 1 把末k位变成1 | (101001->101111,k=4) | x or (1 shl k-1) 末k位取反 | (101001->100110,k=4) | x xor (1 shl k-1) 把右边连续的1变成0 | (100101111->100100000) | x and (x+1) 把右起第一个0变成1 | (100101111->100111111) | x or (x+1) 3 4 Webb.S 把右边连续的0变成1 | (11011000->11011111) | x or (x-1) 取右边连续的1 | (100101111->1111) | (x xor (x+1)) shr 1 去掉右起第一个1的左边 | (100101000->1000) | x and (x xor (x-1)) 最后这一个在树状数组中会用到。 和 普通算法一样，这是一个递归过程，程序一行一行地寻找可以放皇后的地方。过程带三个参数，row、ld和rd，分别表示在纵列和两个对角线方向的限制条件 下这一行的哪些地方不能放。我们以6x6的棋盘为例，看看程序是怎么工作的。假设现在已经递归到第四层，前三层放的子已经标在左图上了。红色、蓝色和绿色 的线分别表示三个方向上有冲突的位置，位于该行上的冲突位置就用row、ld和rd中的1来表示。把它们三个并起来，得到该行所有的禁位，取反后就得到所 有可以放的位置（用pos来表示）。前面说过-a相当于not a + 1，这里的代码第6行就相当于pos and (not pos + 1)，其结果是取出最右边的那个1。这样，p就表示该行的某个可以放子的位置，把它从pos中移除并递归调用test过程。注意递归调用时三个参数的变 化，每个参数都加上了一个禁位，但两个对角线方向的禁位对下一行的影响需要平移一位。最后，如果递归到某个时候发现row=111111了，说明六个皇后 全放进去了，此时程序从第1行跳到第11行，找到的解的个数加一。 六、（数据结构）树状数组 用lowbit函数维护了一个树的结构 那么查询a[1]+...+a[n]的时间是log级别的，而且是一个在线的数据结构， 支持随时修改某个元素的值，复杂度也为log级别。 来观察这个图： 令这棵树的结点编号为C1，C2...Cn。令每个结点的值为这棵树的值的总和，那么容易发现： 4 5 Webb.S C1 = A1 C2 = A1 + A2 C3 = A3 C4 = A1 + A2 + A3 + A4 C5 = A5 C6 = A5 + A6 C7 = A7 C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 ... C16 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 + A9 + A10 + A11 + A12 + A13 + A14 + A15 + A16 这里有一个有趣的性质： 设节点编号为x，那么这个节点管辖的区间为2^k（其中k为x二进制末尾0的个数）个元素。因为这个区间最后一个元素必然为Ax， 所以很明显：Cn = A(n – 2^k + 1) + ... + An 算这个2^k有一个快捷的办法，定义一个函数如下即可： int lowbit(int x){ return x&(x^(x–1)); } 当想要查询一个SUM(n)(求a[n]的和），可以依据如下算法即可： step1: 令sum = 0，转第二步； step2: 假如n <= 0，算法结束，返回sum值，否则sum = sum + Cn，转第三步； step3: 令n = n – lowbit(n)，转第二步。 可以看出，这个算法就是将这一个个区间的和全部加起来，为什么是效率是log(n)的呢？以下给出证明： n = n – lowbit(n)这一步实际上等价于将n的二进制的最后一个1减去。而n的二进制里最多有log(n)个1，所以查询效率是log(n)的。 那么修改呢，修改一个节点，必须修改其所有祖先，最坏情况下为修改第一个元素，最多有log(n)的祖先。 所以修改算法如下（给某个结点i加上x）： step1: 当i > n时，算法结束，否则转第二步； step2: Ci = Ci + x， i = i + lowbit(i)转第一步。 i = i +lowbit(i)这个过程实际上也只是一个把末尾1补为0的过程。 对于数组求和来说树状数组简直太快了! 七、（数论）快速幂 把b转换成2进制数 该2进制数第i位的权为a^（2^(i-1)） 例如 a^11=a^(2^0+2^1+2^3) 11的二进制是1 0 1 1 11 = 2^3*1 + 2^2*0 + 2^1*1 + 2^0*1 so:我们将a^11转化为算a^(2^0)*a^(2^1)*a^(2^3) 5