博文
遗传算法小记(2008-04-19 15:54:00)
摘要：我的毕设是做TSP问题，给定一个图，n个顶点，求一个哈密顿圈（不连通认为以无穷大权连通），使总的权合最小，即最小哈密顿圈。它的通俗描述是，一个旅行商(traveling salesman)从一个城市出发，经过其它城市一次且仅一次，最后回到出发城市，求一个路径，使总的行程最短。
下面这个是用GA做的，城市数n=50，种群大小gn=100，交叉概率pc=0.98，变异概率pv=0.01，结束迭代的条件是，连续10个种群的平均评价值没有增长，图中值是种群平均评价值的倒数，也就是哈密顿圈总权和。从图中看出，它很好的收敛到某个较低值。但是最优个体并不一定出现在最后的种群，为什么？这很容易理解，算法是用种群为单位计算的，但我要的结果却是一个个体，以种群为单位是为了很好的避开局部最优，但是全局最优可能会存在于较后期的某个种群，而不一定是最后一个种群，以人类的历史为比喻，最聪明的人一定是今天地球上的某个人吗？人类历史也可能停止不前，只能说总体水平在优化，但我个人认为比爱因斯坦聪明的人还没有过，但它却不在最后一个种群当中。
GA收敛得很好，但是比较慢，它竟然进化了1千多代！相比SAA对一个相同数据的计算结果图如下：
它没有优化到前者那个水平，最后只能划一条直线的原因是温度已经降得过低了，已经没有可能再优化了。它的起伏比较大，但是它的优点是收敛快，它从17000左右优化到7000左右，只迭代了100次不到，而且它只迭代一个个体，相比之下GA优化到那个水平却进化了500代左右。SAA还有改进的空间，比如温度的控制，迭代次数和温度的关系，等。而GA就要从交叉的方法等改进。......
[转]模拟退火算法求解TSP问题(2007-07-07 21:51:00)
摘要：模拟退火算法求解TSP问题
作者：ymhui
下载源代码
一、问题描述
旅行商问题，即TSP问题（Travelling Salesman Problem）是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路经的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。
图1 TSP问题的示意图
二、遍历算法
一个最容易想到的方法是利用排列组合的方法把所有的路径都计算出来，并逐一比较，选出最小的路径。虽然该方法在理论上是可行的，但路径的个数与城市的个数成指数增长，当城市个数较大时，该方法的求解时间是难以忍受的，甚至是不可能完成的。以每秒1亿次的计算速度来估算，如果TSP问题包含20个城市时，求解时间长达350年；如果要处理30个城市，则求解时间更长达1+10e16年。如此长的时间，在实际中完成是难以想象的。
三、模拟退火算法
模拟退火算法是解决TSP问题的有效方法之一，其最初的思想由Metropolis在1953年提出，Kirkpatrick在1983年成功地将其应用在组合最优化问题中。
模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。
求解TSP的模拟退火算法模型可描述如下:
解空间：解空间S是遍访每个城市恰好一次的所有路经，解可以表示为{w1,w2 ,……, wn}，w1, ……, wn是1,2,……,n的一个排列，表明w1城市出发，依次经过w2, ……, wn城市，再返回w1城市。初始解可选为(1,……, n) ;
目标函......
FFT乘法和高精运算库(1)(2007-04-11 20:28:00)
摘要：不准备多写，这些东西网上可以搜出一箩筐来。
高精运算库的构想，是可以快速的应付巨数的运算，包括加，减，乘，除等。比如现在的int是16字节，long32字节，LONGLONG64字节，再大一些就要扩字了，于是就不能用原来汇编给我们用的指令了，需要重新定义运算。
加减很容易，小学加减法，跟手工算一样的，复杂度是O(n)，n表示数据的长度。
乘法如果直接像手工算一样做，复杂度是O(n*n)的，FFT乘法是将数看成多项式：
P1(x)=a0+a1x+a2x^2+...+anx^n，如果取ak在0到9之间，且x取10，那它就表示一个十进制数，如果再用另外一个多项式P2(x)与它相乘，那结果和它所表示的数相乘是一样的数值。
多项式乘法其实质是做两个系数序列的卷积，而FFT正是对这样的卷积做从时域到频域的变化，FFT的本质也是DFT，离散富里叶变换，因为有卷积定理：
如果h(t)=x(t)*(y(t)，且H(s)=DFT[h(t)]，X(s)=DFT[x(t)]，Y(s)=DFT[y(t)]，那么有，H(s)=X(s)Y(s)
在频域的序列只需要做乘积，就是对应项乘对应项，是O(n)复杂度，因为FFT是一个DFT的快速算法，复杂度在O(nlogn)，所以可以得到同样复杂度的FFT乘法，形式表示成：
h(t)=IFFT[ FFT[x(t)]FFT[y(t)] ]
IFFT是快速富里叶反变换，可以转换成FFT，所以一个乘法的时间是3个FFT加一个线性乘积运算，因此也是O(nlogn)。
开始动手做FFT乘法程序之前，先实现一个FFT算法模块，然后要考虑的事有：1，复数如何表示？用float还是double型存实型数？2，进行运算的时候选多大的基？
因为DFT的运算关系到复数，复数好办，用两个实数表示就行了，实数的选取，精度够不够，如何表示精度，误差怎样控制？
如果基是B，参与运算的数最长有N，则一种最极端的情况是，全部取到B-1（测试的时候如果基10，就全9，基100就全99进行测试），做线性卷积回来最大的可能结果是N(B-1)^2，这里要考虑浮点数的精度和需要达到的巨数的长度，很矛盾的选择，一方面想基越大越好，这样大数存起来比较节省，但是基一选大了，精度就会下降，可以实验一下。我实验的结果是float型绝对不够，可能算不是很大的数都错几位，double可以......
数独(sudoku)的生成与破解(2007-01-25 21:06:00)
摘要：数独(sudoku)的生成与破解
最近在网上比较流行的智力游戏。笔者本人也玩过，可以下个模拟游戏试试，简单的还可以，太难就无从下手了。虽然偶脑子不好使，但偶是计算机科班出身，怕你不成，老规矩，编程破解。
首先，偶是第一次做数独的程序，可能程序不强，以后有时间再改进改进。望高手评析。
还是把数独游戏的规则说一说吧，或许你是刚刚听说这个名字的朋友。数独(sudoku)，起源于瑞士，于1970 年代由美国的一家数学逻辑游戏杂志首先发表，当时名为Number Place。及后在日本大力推广下得以发扬光大，于1984 年取名“数独”，即“独立的数字”的省略，在一个9x9的方格中，有81个小方格组成，然后又分9个大块，每块由3x3的方格组成，就是中国的九宫图，大九宫里面再套9个小九宫，共九九八十一个小格子，游戏开始前会有一些格子上写好了数，你需要在剩下的格子里填数，真到把所有格子填满，并且要求，任何一行或一列或者一个小九宫中没有相同的数字，当然你只能用1-9之间的9个数字。如下图就是一个数独。希望我解释清楚了，如果你还不清楚，用google搜索一下相关资料，点这里http://www.google.com/search?q=sudoku%20%E6%95%B0%E7%8B%AC&hl=zh-CN&lr=&nxpt=10.1471893728569764719035
好啦，言归正传。简单来说，我的破解法非常简单，就是超级无敌强硬大搜索，呵呵，别拿你想数独的那套来让计算机想，它比你可笨得多了，它只会照程序做事，做得快而已，快就是它的本事，其它的一概不会。
核心算法：深度优先搜索（其它形式的搜索也可以）
数据结构：如果用递归的形式写深搜，定义在函数dfs里的所有变量都可以看成是这里的数据结构，因为它们自动地被系统压入栈内，所以，省了，你唯一要做的就是一个二维数组，存放当前数独的状态。
当然有了这些，偶还不敢动手做，如果你做过马遍历的程序，大概会有点怕，那才8x8，这里是9x9，不来点‘启发式’谁敢动手写程序，有可能一个数独来几千几万个解，一个解要搜80层上下（估计），懂得树这个数据结构的人就会明白，80层是什么概念，1-9有9个数字，就是9叉树，至少是9^80量级的代价，什么？计算机反正算得快？也不行，再快的计算机遇到指数复杂度的程序......
算法设计小结(2006-12-02 13:38:00)
摘要：前段时间借了本《算法设计》大致看完了，作个小结。
大的方向：分治与递归
发现这个是经典啊，递归是分治思想的实现方法。递归有两个方面，一个是递归方程，是设计分治问题的数学工具，于是就有主方法，主定理，这一块比较容易用来考试，像考研啊可能会比较喜欢这块内容，还有一个就是程序中的递归，这个需要技巧，先别乱用。
分治这条线下来，看最优问题中的两个常见范型，DP和贪心，她们的共同点是有最优子结构，怎么刻划最优子结构？就是递归方程，写成方程是最终目的，一开始可以简单表示，然后考虑需要考虑的量，然后转化成方程，有了递归方程再做程序，程序中不要用递归，而是打表，做备忘录或者直接递推，最后再由结果构造最优解，这样DP算法设计完毕。贪心的数学工具是拟阵，它是非空的，可遗传的，可独立扩充的一个二元集合，对拟阵有Greedy算法，这是有证明的算法，于是在贪心算法的具体问题上如果发现它满足拟阵的定义就可以直接运用贪心算法。贪心和DP的区别在于，贪心是从当前状态简单的做出最优判断，做状态转移，也可以看成是先排序（或大致有序）再一一进行选择，然后最优解就可以简单地构造出来，而DP是对当前状态进行一个计算，然后再构造最优集。贪心算法从理论上虽然不完美，但实际中有很重要的作用，像Dijkstra单源点最短路径算法，Prim算法等都是贪心。顺便提一下优先队列，这个数据结构可以用于最优问题中的选择算法，它可以动态的维护一个堆，而不是作相对费时的排序操作，而使算法性能提高很多。这一块分出来，叫面向数据结构的算法设计。此外，最优化问题远不仅如此，像LP等，那都是工科数学做的，应用方面多在工程上。
分治DP这一块有很多很多经典问题，有些问题本身都可以看成是算法设计范型，应用相当广泛，像LCS，归并，快排等。
递归这条线下来，看回溯法。回溯是王道啊。这里要了解解集和解集树的概念，在不是最优问题时或者没有最优子结构的最优问题里，就需要先构造解集树。这里和图论中的DFS有一些联系，实际上对图的一次DFS就是对它的某个生成树的遍历，其实质上也就是回溯。回溯就是先构造解的一部分，再决定是继续构造解还是退回，也就是回溯一词的本意。更广泛的来讲，回溯不仅限于DFS，DFS只是延深度方向延拓结点构造解，而回溯也可以延广度方向，或者是其它形式。理解了DFS，相当于理解了回溯的一大半，于是你就可以轻松的设计全排列、8皇......
FibonacciHeap的C++模板实现(2006-11-23 17:01:00)
摘要：FibonacciHeap是一种优先队列，它的性能如下图所示。
就平均而言有很好的性能，所以在一些图论算法中可以用来作改进算法的数据结构，尤其是那些稀疏图，总之是很好的工具。下面以设计者的角度简单描述我设计它的过程和思路。
1、组织方法
采用C++提供的模板支持设计这个模板类，以达到很高的适应性。参数列表中只有一个类class T，它表示这个容器的元素类型，然后需要对它进行小的封装，封装的结果是得到一个内部小数据结构fibnode，如上图所示。
fibnode是组织FibonacciTree的结点结构，它包括了全部的指针和标记，整个FibonacciHeap就由它组成的，这个FibonacciTree在外部看来，只有一个min指针，指向它的根一层结点。
由于这样的组织形式，所以在析构的时候需要以递归的方式进行，递归的调用release()完成内存单元的回收。
这样的组织元素会遇到一个外部的问题，那就是内外数据的映射，由于元素是采用COPY的方式放入容器的，所以在内部是不知道哪个元素被封在哪个fibnode里，在内部确定一个元素的唯一方法就是找到它的fibnode指针，而为此如果做查找运算的话那它的优势将无法发挥出来。这个问题我没有在内部给出解决方法，原因是为了高适应性，因为这个T是未知的，所以我没办法给个O(1)的映射算法，如果用红黑树做Map，那会有O(lbn)的时间开销，那将使Decrease_Key()等调用的性能下降，唯一更好的办法是采用Hash表，而如果确定Hash函数又是和T有关的事情，所以这些事留给使用着在外部解决，根据具体的数据内容选择好的Hash函数，做外部的从T到const fibnode*的映射。值得说明的是，任何的fibnode指针都会在insert()过程的返回值中得到，如列程序所示：
Heap::FibonacciHeap<int> h;
const Heap::FibonacciHeap<int>::fibnode *x;
x=h.insert(100);
x将得到元素100的内部指针。于是可以将x作为Decrease_Key()的参数进行操作。
2、几个实现中的问题
从FibonacciHeap的算法描述到实现其实不是太难，很多操作都轻而易举的事，我额外定义的......
Priority Queue - Binary Heap(2006-11-14 17:14:00)
摘要：没什么好写的，都在《Introduction to Algorithms》里面，老外的教材就是厉害，不像我们国内，计算机类书籍不少，优点是：一、贵，二、内容不全，有时候要学个什么东西查一本书还不行，唉，写书都是为了赚钱，哪有什么好书。
前些天我借了本《算法设计与分析》的书，读着读着发觉怎么好像读过，一想，哦，是这本书里看过，那时候觉得看英文累，印象深刻，原来写中文书还有这么一招，直接翻译来就OK。老外不喜欢东搞西搞，一本书，比砖头还厚，把想说的全说完，全部搞定，简单，容易查阅，买一本一辈子带身边。哈哈，我刚好有一本，影印版的。
这个Priority Queue原来学《数据结构》的时候老师没讲，自己也没重视，现在翻出来学，发现很有用的。
一般的queue都是FIFO，元素间的前后关系完全取决于入队的时间，而不是某种数学上的偏序关系。而现实中的队列却是有优先级的，按优先级排个序，最先出来的应该是优先级最高的，这个时候的queue有个新名字，heap。
按我自己的理解，一个heap就是一个具有某种偏序关系的有序集合，它是一种半‘排序’化状态，我们感兴趣的就是第一个从heap里出来的元素，这时它是最小的，但是你要一次让第k小的出来，做不到，因为它内部组织数据的时候没有完全有序，并不是那么简单的。为什么只需要知道最小元素呢，因为它是一个Priority Queue。
像消息队列就应该是一个Priority Queue，有系统消息，各种用户级别的消息等。
另外像有的时候在需要动态维持一个有序集，同时又需要求最小元素时，很适合使用。像Dijkstra单源点最短路径算法中就可以用Priority Queue优化算法，还有最小生成树算法等。
Priority Queue有很多种，最简单的二叉堆，还有Binomial Heap,Fibonacci Heap等。它们的效率各不相同，优点各异，二叉堆在实现上比较简单，而且重要的操作，像Extract_Min()（取最小元素并移出队列）,Insert()等，都有较好的时间复杂度，但是缺点是Union()操作太废时，这本书上说是O(n)的，而且就给了一句话：By concatenating the two arrays that hold the binary heaps to be merged and then running......
Fibonacci数列的计算(2006-11-06 17:43:00)
摘要：Fibonacci数列F(n)递归地定义为：
1 n<=2
F(n)={
F(n-1)+F(n-2) n>2
列出前几项：1，1，2，3，5，8，13，21，34。。。
注意到这些数字没有，很多都是在大自然中出现的，我知道的少，不过你可以在互联网上搜一下，关键词：黄金分割。
没错，这个数列中体现了黄金分割，用数学方法很容易证明。首先它是发散的，但是不妨假设F(n+1)/F(n)是可以收敛的，设e=limF(n+1)/F(n)，由递推方程：F(n)=F(n-1)+F(n-2)，两边同除F(n-1)得（在极限情况下）：e=1+1/e，解出来就得e=1.618...，同时也得知它近似地相当于指数数列1.618^n，至少会以这样的增涨率增涨。
以下总结一下Fibonacci数列的计算方法。
1，直接递归计算。
int fibonacci(int n)
{
if(n<=2)
return 1;
return fibonacci(n-1)+fibonacci(n-2);
}
它的计算效率同它的数值增涨效率一样是指数型的（O(1.618^n)），因为它会在递......
Euclid算法与RSA(2006-10-11 09:48:00)
摘要：历史上第一个称得上算法的好像就是这个欧几里得算法，其实就是地球人都知道的辗转相除，不要小看她，她是很美的。
简单的描述就是，记gcd(a,b)表示非负整数a,b的最大公因数，那么：gcd(a,b)=gcd(b,a%b)或者gcd(a,0)=gcd(0,a)=a。
写成程序很简单，不管是用递归还是循环：
int gcd(int a,int b)
{
if(a==0)
return b;
if(b==0)
return a;
return gcd(b,a%b);
}
不仅算法形式简单，而且效率很高，我不知道具体是多少复杂度的，我只知道效率很高；）
前天看ＲＳＡ算法，是非对称加密的标准算法，其实算法很简单：
找到两个素数p,q，再找一个数r，使gcd(r,(p-1)(q-1))=1，也就是说互素，然后再找一个数m，使rm=1(mod (p-1)(q-1))，然后再作乘法n=pq，然后把pq丢掉，最好是让任何人都不知道，包括自己（免得说梦话的时候被人听到），然后手里拿到r,m,n，r就是Private Key，只有你知道，而m,n就是Public Key。设信息为a,加密过程：a^r=b (mod n)，b就是密文，解密过程：b^m=a(mod n)，反过来用m加密，用r解密是一样的。
书上说由gcd(r,(p-1)(q-1))=1到求m，使rm=1(mod (p-1)(q-1))是很容易的，就用辗转相除，我想了好久才想到一个方法。
问题：如果gcd(a,b)=1，求x，使ax=1(mod b)
......
香农编码(2006-09-20 20:52:00)
摘要：今天的作业，想到可以直接由浮点数格式中取出尾数得到ShannanCode，麻烦点的地方是需要重新对阶，因为在尾数规格化省掉了一位，最终效率比较高。
#ifndef SHANNAN_CODE_DEF_200609
#define SHANNAN_CODE_DEF_200609
typedef unsigned long U32;
typedef signed char S8;
class CShannan
{
float *m_p;//消息概率
float *m_sp;//累计概率P
float *m_i;//信息量
int *m_length;//码长
U32 *m_code;
int m_n;
public:
static int cpux86();
public:
CShannan(int n);
~CShannan();
void InputPro();
void OutputCode();
};
#endif
#include "stdio.h"
#include "assert.h"
#include "math.h"
#include "shannan.h"
#ifndef NULL
#define NULL 0
#endif
CShannan::CShannan(int n)
{
assert(n>0);
m_n=n;
m_p=new float[n];
m_sp=new float[n];
m_i=new float[n];
m_length=new int[n];
m_code =new U32[n];
assert(m_p!=NULL);
assert(m_sp!=NULL);
assert(m_i!=NULL);
assert(m......