A* Algorithm
该算法是一个求最短路径的算法，同Dijkstra算法类似，起始点到终点的距离f(M) = g(M) + h(M)，g(M)表示从起始点S走到M点的距离，h(M)表示从M点到终点的估计距离。算法的关键在h的估计上，可以采用欧氏距离、曼哈顿距离等距离度量方式。在采用特定的距离度量方式估计h(M)的值后，计算f(M)的值，并对f(M)的值进行排序，找到最小的f(M)对应的那个节点作为下一个节点。
与Dijkstra算法不同的是，Dijkstra算法是从未走过的节点中找到一个距离已走过的节点最近的节点作为下一个节点，如果A*算法不对f(M)进行排序，则跟Dijkstra算法类似，只是比Dijkstra多计算一个估计值。如果h=0，则A*算法类似于BFS算法，即不考虑终点，只考虑起始点，但可以保证给出最优解；如果g=0，s则A*算法类似于DFS，即不考虑起始点，一根筋的找离终点最近的下一个节点走，这样可能不会给出最优解。
Fibonacci堆
- Fibonacci堆采用双向循环链表；
- 去除最小节点后，将该节点的所有子节点都串联到根表中，然后将根表中度数相同的子树合并，直至没有度数相同的子树。
- 在合并根表中相同度数的子树时，注意孩子节点的值要比父节点的值要小，这样才能保证Fibonacci堆中的最小值始终在根节点上。
- 节点值减小：如果破坏了最小堆性质，则需要重新维护最小堆。首先将值减小的节点及其子树从堆中拿出来，然后将其并到根链表中；然后再从”被切节点的父节点”到所在树根节点递归执行级联剪枝。
- 节点值增大：将值增大的节点的孩子添加到根链表中，如果值增大的节点不在根链表中，则将其也加入根链表中。然后对其父节点进行级联剪切；如果没有父节点，则判断是否需要更新堆得最小值。
- 级联剪切的真正目的是为了防止”最小堆”由二叉树演化成链表。
装箱问题
tabu 搜索，模拟退火，领域搜索，GRASP算法
基本知识
一般50,000,000次循环用时在0.5s左右
STL
二分搜索
- lower_bound(
*begin, *end, key)：返回第一个不小于key的元素在数组中的位置 - binary_search
- upper_bound
排序
- algotithm包里面sort(v.begin(), v.end())采用快排，快排不稳定；stable_sort采用归并排序，是稳定的，不过归并排序会产生额外的内存开销，时间复杂度虽然也是O(nlogn)，但会比快排稍慢。
set
set里元素不重复，由二叉搜索树实现，并且对树进行了平衡处理，使得元素在树中分布较为均匀，可以保证搜索、插入和删除的复杂度在O(logn)。
贪心
采用贪心法，一般分为若干步，每一步选择都以代价最小或者收益最大为判断标准，可行解即满足问题约束条件的解
NP问题
当我们讨论一个算法的时间复杂度时，是在说算法运行时间与其输入规模的关系。一个问题实例的规模就是指它被编码到图灵机的输入带上的长度。可以证明的是，用任何有限的字符集来编码，图灵机完成计算所用的时间T本质上都不会变，只是会乘上某个常数因子。所以通常我们用输入的二进制编码长度来表示输入规模。对于背包问题，其时间复杂度是O(nW)，n为物品个数，W为背包最大容量；复杂度转化为二进制表示为$O(n*2^{log^W})$，设m=$log^W$，则W随m是呈指数变化的