模拟退火

Share

模拟退火是一种通用概率算法，用来在固定时间内寻求一个大的寻找空间内找到的最优解。

简介

模拟退火来自冶金学的专有名词退火。退火是将材料加热后再经特定速率冷却，目的是增大晶粒体积，并且减少晶格中的缺陷。材料中的原子原来会停留在使内能有局部最小值的位置，而随机在其他位置中移动。退火冷却时速度较慢，使得原子有较多可能可以找到内能比原来更低的位置。

模拟退火的原理也和金属退火的原理近似：我们将热力学的理论套用到统计学上，将搜寻空间内每一点想像成空气内的分子；分子的能量，就是它本身的动能；而搜寻空间内的每一点，也像空气分子一样带有“能量”，以表示该点对命题的合适程度。算法先以搜寻空间内一个任意点作起始：每一步先选择一个“邻居”，然后再计算从现有位置到达“邻居”的概率。

More →

红黑树C实现

Share 
红黑树是一门玄学，想活着就千万不要想我一样去碰他（吐出一口老血）

这个轮子是我到目前写的最复杂的一个数据结构的轮子，没有之一。

具体关于红黑树的文章我会在过几天整理出来。

先看代码吧，里面有注释。

More →

二叉查找树

Share

查找树(search tree)是一种数据结构，它支持多种动态集合操作，包括 SEARCH , MINIMUN , MAXIMUN , PREDECESSOR , SUCCESSOR , INSERT 以及 DELETE。它既可以用作字典，也可以用作优先队列。

在二叉查找树(binary search tree)上执行的基本操作的时间与树的高度成正比。对于一颗含有n个结点的完全二叉树，这些操作的最坏运行时间为O(lgn)。但是，如果树是含有n个结点的线性链，则这些操作的最坏情况为O(n)。在下文可以看到，一颗随机构造的二叉查找树的期望高度为O(lgn)，从而这种树上基本动态集合的平均操作时间为O(lgn)

More →

详探贪心算法

Share

贪心算法的基本内容

贪心算法是通过做一系列的选择来给出某一问题的最优解。对算法中的每一个决策点，做一个当时看起来是最佳的选择。这种启发式策略并不是总能产生最优解，但正如我们在哈夫曼问题中看到的那样，它常常能给出最优解。此篇文章我们来讨论讨论贪心算法的某些一般性质。

More →

Huffman树以及Huffman编码

Share

Huffman树是一种存储结构，由于国内有的资料翻译为哈夫曼或者是霍夫曼，这里为了简单（当然不是懒了）就是用英语Huffman代替。

解决Huffman树问题是典型的贪心算法问题。

贪心算法

贪心算法又叫贪婪算法，是指在对问题求解释，总是做出当前看来是最好的选择。

当一个问题具有以下性质时可以用贪心算法求解：每一步的局部最优解，同时也是整个问题的最优解。

More →