博文
数字追凶(2007-08-09 00:07:00)
摘要：英文名叫《numb3rs》，老实说，情节不怎么吸引人，比较吸引人的是那个主角太有才了，真是无所不知，而且都对破案很有帮助。
原来数学可以这么用，太牛了，真是偶像级mather。
图书馆借的一本书，叫《数学的源与流》，感觉也很不错哦。......
直方图均衡化的理解(2007-07-26 17:44:00)
摘要：其实数字图像处理的本质还是数字信号处理，但是还有一些广泛的知识可以利用，比如物理上成色的原理，人眼感知色彩的原理，形态学等，把这些原理的东西拿开就剩下数学了。
我看了半天书上表述的直方图均衡化，就是没弄明白，后来看了代码才恍然大悟，其实很简单。
定理：一维随机变量a~F(x)，则F(a)~U[0,1]，a从负无穷到正无穷，U[0,1]是标准均匀分布。
证明：（相反的思路）设b~U[0,1]，由定义，
0 x<0
P{b<x}={ x 0<=x<=1
1 x>1
设某值域为[0,1]的单调增函数F(x)的反函数是F-1(x)，则
考察F-1(b)的分布情况，由定义
P{F-1(b)<x}=P{b<F(x)}=F(x)
即F-1(b)~F(x)
令a=F-1(b)，则b=F(a)
有a~F(x)，且F(a)~U[0,1] |
这个定理说明了均匀分布的随机变量的地位，对于任意分布的随机变量，只要给出分布函数的反函数，就可能直接构造出来（不过大部分是很难有简单形式的）。
一张图片，可以看成是对现实景物的一次抽样，就是一个样本，样本有二重性，可以看成是随机变量，就某个特征，比如灰度，它有一定的分布，而直方图就是它的密度函数，均衡化就是先求出F(x)，把密度函数逐段求和就行了，再用F(x)作用每一个像素，将原图像的a，变换成F(a)，使直方图变得相对均衡。
实际实验效果比较恐怖，效果比较吓人，一个美女变成xxx，呵~另外由于是离散的变换，所以结果不会绝对均衡，有时甚至会严重失真。......
用代码新建空白文档（MDI）(2007-07-23 02:50:00)
摘要：查了半天MSDN才找到，比较巧。
有几个类要搞清楚，CDocument,CDocTemplate,CDocManager（这个在MSDN里查不到~我的版本太老了？），他们的关系要看MFC源码，也不是很难弄清楚，比如从OnFileNew这个东西开始找，可以在CWinApp里找到，还有CDocManager，在后者里，最后一句是：
pTemplate->OpenDocumentFile(NULL);
于是找一下CDocTemplate的这个函数说明，找源码也行，里面也有注释，他有两个参数，如果第一个为NULL，则会新建一个空的文档，并返回它的指针，CDocument*，就是我要的功能，关键是这个pTemplate怎么得到，看前面代码，它是用：
CDocTemplate* pTemplate = (CDocTemplate*)m_templateList.GetHead();
而这个CDocManager的实例可以在theApp里找到，这个是唯一的一个全局变量，加上一句声明：extern CMyApp theApp;就可以用了，进m_pDocManager没问题，可是再访问m_templateList就出了问题，是protected权限，没办法了，我都想直接修改MFC源码了~~（怕改乱了）
其实有更直接的方法，CDocument有一个成员函数直接得到：
CDocument::GetDocTemplate()
OK，这样就可以在文档类里实现用代码新建另外一个文档，完了可以设置标题等等。
另外一个同窗在做代码的时候，把菜单的响应事件不小心放到了文档类里，我建议他放在视类，因为视类优先响应消息，文档专门管理文档，他不听，他说书上写在文档类里的，晕~~（破书扔了）后来在文档类里响应了之后要马上更新一下视类，不然会让人觉得没有反应，刚打开的文件显示都没变，不是觉得很奇怪吗？很自然的想到Invalidate()，但是这是在文档类怎么办？
找到两个成员函数：
GetFirstPosition()
GetNextView()
怎么做到看帮助。于是我想到，原来文档和视类是这么层关系，一个文档可以有多个视类，而一个视类只有一个文档。
同样的CDocTemplate和CDocument也是类似一个树状关系，如下图所示：
......
我写的简单矩阵类库 mat库(2007-07-14 02:50:00)
摘要：记得第一个跟我讲MATLAB的老师是数字信息处理的老师，他大概的意思是说MATLAB如何好，举个例子在MATLAB里做个转置就只要a'就行了，说用C语言还要循环套循环，麻烦~我当时就想，MATLAB好用还不是底层把事情都做好了，你只调用当然方便啦，我还是觉得C/C++才是最好的语言。
我想模仿MATLAB做事，有了我写的库，很多事会变得同样简单。
主要功能，用C++模板将已知类型数据组织成矩阵的形式，并提供基本的矩阵运算。
1，矩阵定义：
matrix<类型名> <变量名>;
比如定义一个double双精度的矩阵：
matrix<double> a;
2，矩阵的初始化：
从数组初始化：
double a[]={1,2,3,4,5,6};
matrix<double> ma(a,2,3);
构造出一个2 x 3的矩阵ma，其元素依次是：
1 2 3
4 5 6
从单个元素初始化：
matrix<double> a=0.0;
构造出一个1 x 1的矩阵，其元素是0
用size(h,w)成员函数指定存储大小：
matrix<double> a;
a.size(2,3);
构造出一个2 x 3的矩阵，元素值未知。可以接着用a=0.0;将所有元素赋成0或者其它值
用提供函数identify(T(),h,w)构造单位矩阵：
matrix<double> a=identify(double(),2,3);
第一个参数随便指定一个相同类型的值就行了，结果构造一个2 x 3的单位矩阵：
1 0 0
0 1 0
（和MATLAB里的eye相同）
3，矩阵的基本运算
由于这里的矩阵元素类型不一定为double型，所以不一定是用来做数值运算的，或者你也可以用其它你定义的类型，但有时是需要有+,-,*运算定义以及整数0，1的构造函数构造出0元和单位元的构造函数。有时你也可以把它想成一种容器（它现在的底层实现还不是很好），一种矩阵的容器。
3.1 选择运算
选择运算是最重要的，拿到一个矩阵要很容易选定它的元素或部分。
a,operator[] 选行（列）运算<......
[转]模拟退火算法求解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) ;
目标函......
本站内容链接(2007-07-06 02:43:00)
摘要：您现在访问的是
算法驿站 powered by 编程爱好者网站
这个小站是我修读《信息与计算科学》本科时就自己所学到的所感受的东西留于笔下，开始不叫这名字，后来才慢慢感觉到‘算法’的威力，而‘驿站’是指作者我也是在学习，大家一起学习的这个过程。
有这样一种说法，先不说它的正确与准确性，至少还是有些道理的，就是，程序=数据结构+算法，程序就是一段指令，看看现在的计算机技术，从硬件的描述语言，汇编，高级语言，脚本，其实可以都认为是‘程序’，及程序就是计算机的全部，就算你是做硬件的人，你用CAD吧，你会从逻辑门开始设计吗？可编程逻辑器件，什么Intel8253之类，你做单片机，你会从汇编开始吧，或者是C语言，你不会去做那个片（我国国内好像还不能做'片'），拿到一堆APIs就开始干活，无非是2个8位拼成16位，还不就是做程序，好，你做程序员，就算你做系统程序员，你写个OS之类的，下面也是用别人做好的指令，你不会去设计微指令吧，流水线也不用管，cache也透明，剩下的东西，还不就是编程，做应用程序员，站在XP上干活，站在linux上干活，到你去做的事情，还是编程。我想说的是，‘程序’可以代替一个词‘逻辑’，而逻辑就是计算机的全部，至少当前的冯计算机，不同的只是大家所处的层次不同（越低级的人越少，但是我不同意越赚钱）。
而程序是=数据结构+算法，数据结构是精心地准备好数据，将那些信息以一定的形式一定的逻辑组织在一起，以使算法的效用达到最大，算法是所有程序的核心，可以看成程序本身，也可以这样比，算法是无形的，而程序是有形的，不管你如何实现，算法是发挥最大作用的东西，而程序是算法的某个实例。
做IT这行，只要是做技术的，只要把算法学好，动手能力强，不管做哪一行（计算机行也分很多）都会很吃香，剩下的只是工具的问题，实现的具体环境，熟能生巧嘛，越是高级的工具其实越容易上手，少数可能门槛比较高，但也都没有算法本身重要。
好了不多说了，本文是想把小站的内容做个链接，做个目录，以下是目录。
目录
1 基础算法
排序由浅入深（一）::选择排序
排序由浅入深（二）::交换排序
排序是算法的切入点，这两篇可能也没什么深度，现在看，那些个经典的排序算法，要时刻牢记于心，那会是一种算法设计泛型，比如快排，归并，基数排序，桶排等。
穷举搜索::回溯与深搜
分......
[笔记]MATLAB画图(2007-06-29 20:33:00)
摘要：一点感想，MATLAB用起来方便，关键还是要理解它的实质。
从图形学的角度，计算机画图，无非是画点，画线和画面，OpenGL就是基于点的图形库，它没有提供体的图元，构成体的实际上是体上的各个面，而面是由一些点和一种片型表达的，比如三角形片。
在MATLAB里，也可以这样类比，而且还要简化一些。只有两种，一是画线，一是画网格，也就是四边形片，即使这样表达一些复杂的几何形体也是很强大的。
1，画线
看成是画一维的形体。一维是指表现能力，比如画三维的线，同样还是画线。
比如我要画n维的线，就给出n个向量：
v1,v2,...vn
for i=1:m
{v1(i),v2(i),...vn(i)}就是这个线上一个离散化的点，前后用直线连起来就行了
在MATLAB里有plot和plot3，是同样的方法。
2，画网格
从直观上理解，一个面当然应该是3D的，它用一个离散的网格表示，网格里相邻的四个点构成一个四边形片，整个铺开就是曲面。
这时要给出3个矩阵：
xx,yy,zz
xx(i),yy(i),zz(i)就是网格上一个点的三维表示。
这里常用一个函数，meshgrid，就是生成两个网格的标准xx和yy分量。
比如：
>> x=[1 2 3 4]
x =
1 2 3 4
>> y=[1 2]
y =
1 2
>> [xx,yy]=meshgrid(x,y)
xx =
1 2 3 4
1 2 3 4
yy =
&......
[笔记]循环语句(2007-06-29 19:23:00)
摘要：for 变量=矩阵
变量每次取矩阵的一列，并执行循环体
end
>> for i=[1 2 3;2 3 4];
disp(i);
end
1
2
2
3
3
4
常见的写法是：
for i=1:100
实质上1:100就是一个一行100列的矩阵，每次取一列，即一个数的列向量。
这样规定循环是有好处的，有些矩阵变换就很好写了。......
[转]线性空间的一些直观感悟（2）(2007-06-13 14:06:00)
摘要：转自：http://qiuwei1985.spaces.live.com/
今天先谈谈对线形空间和矩阵的几个核心概念的理解。这些东西大部分是凭着自己的理解写出来的，基本上不抄书，可能有错误的地方，希望能够被指出。但我希望做到直觉，也就是说能把数学背后说的实质问题说出来。
首先说说空间(space)，这个概念是现代数学的命根子之一，从拓扑空间开始，一步步往上加定义，可以形成很多空间。线形空间其实还是比较初级的，如果在里面定义了范数，就成了赋范线性空间。赋范线性空间满足完备性，就成了巴那赫空间；赋范线性空间中定义角度，就有了内积空间，内积空间再满足完备性，就得到希尔伯特空间。
总之，空间有很多种。你要是去看某种空间的数学定义，大致都是“存在一个集合，在这个集合上定义某某概念，然后满足某些性质”，就可以被称为空间。这未免有点奇怪，为什么要用“空间”来称呼一些这样的集合呢？大家将会看到，其实这是很有道理的。
我们一般人最熟悉的空间，毫无疑问就是我们生活在其中的（按照牛顿的绝对时空观）的三维空间，从数学上说，这是一个三维的欧几里德空间，我们先不管那么多，先看看我们熟悉的这样一个空间有些什么最基本的特点。仔细想想我们就会知道，这个三维的空间：1. 由很多（实际上是无穷多个）位置点组成；2. 这些点之间存在相对的关系；3. 可以在空间中定义长度、角度；4. 这个空间可以容纳运动，这里我们所说的运动是从一个点到另一个点的移动（变换），而不是微积分意义上的“连续”性的运动，
上面的这些性质中，最最关键的是第4条。第1、2条只能说是空间的基础，不算是空间特有的性质，凡是讨论数学问题，都得有一个集合，大多数还得在这个集合上定义一些结构（关系），并不是说有了这些就算是空间。而第3条太特殊，其他的空间不需要具备，更不是关键的性质。只有第4条是空间的本质，也就是说，容纳运动是空间的本质特征。
认识到了这些，我们就可以把我们关于三维空间的认识扩展到其他的空间。事实上，不管是什么空间，都必须容纳和支持在其中发生的符合规则的运动（变换）。你会发现，在某种空间中往往会存在一种相对应的变换，比如拓扑空间中有拓扑变换，线性空间中有线性变换，仿射空间中有仿射变换，其实这些变换都只不过是对应空间中允许的运动形式而已。
因此只要知道，“空间”是容纳运动的一个对象集合，而变换则规定了对应......
[转]线性空间的一些直观感悟（1）(2007-06-13 13:49:00)
摘要：转自：http://qiuwei1985.spaces.live.com/
前不久chensh出于不可告人的目的，要充当老师，教别人线性代数。于是我被揪住就线性代数中一些务虚性的问题与他讨论了几次。很明显，chensh觉得，要让自己在讲线性代数的时候不被那位强势的学生认为是神经病，还是比较难的事情。
可怜的chensh，谁让你趟这个地雷阵？！色令智昏啊！
线性代数课程，无论你从行列式入手还是直接从矩阵入手，从一开始就充斥着莫名其妙。比如说，在全国一般工科院系教学中应用最广泛的同济线性代数教材（现在到了第四版），一上来就介绍逆序数这个“前无古人，后无来者”的古怪概念，然后用逆序数给出行列式的一个极不直观的定义，接着是一些简直犯傻的行列式性质和习题——把这行乘一个系数加到另一行上，再把那一列减过来，折腾得那叫一个热闹，可就是压根看不出这个东西有嘛用。大多数像我一样资质平庸的学生到这里就有点犯晕：连这是个什么东西都模模糊糊的，就开始钻火圈表演了，这未免太“无厘头”了吧！于是开始有人逃课，更多的人开始抄作业。这下就中招了，因为其后的发展可以用一句峰回路转来形容，紧跟着这个无厘头的行列式的，是一个同样无厘头但是伟大的无以复加的家伙的出场——矩阵来了！多年之后，我才明白，当老师犯傻似地用中括号把一堆傻了吧叽的数括起来，并且不紧不慢地说：“这个东西叫做矩阵”的时候，我的数学生涯掀开了何等悲壮辛酸、惨绝人寰的一幕！自那以后，在几乎所有跟“学问”二字稍微沾点边的东西里，矩阵这个家伙从不缺席。对于我这个没能一次搞定线性代数的笨蛋来说，矩阵老大的不请自来每每搞得我灰头土脸，头破血流。长期以来，我在阅读中一见矩阵，就如同阿Q见到了假洋鬼子，揉揉额角就绕道走。
事实上，我并不是特例。一般工科学生初学线性代数，通常都会感到困难。这种情形在国内外皆然。瑞典数学家Lars Garding在其名著Encounter with Mathematics中说：“如果不熟悉线性代数的概念，要去学习自然科学，现在看来就和文盲差不多。”，然而“按照现行的国际标准，线性代数是通过公理化来表述的，它是第二代数学模型，...，这就带来了教学上的困难。”事实上，当我们开始学习线性代数的时候，不知不觉就进入了“第二代数学模型”的范畴当中，这意味着数学的表述方式和抽象性有了一次全面的进化，对于从小一直在“第一......