科学网—标签

相关帖子	版块	作者	回复/查看	最后发表

hanpu0725 2010-5-25 09:36

K-MEANS算法: 输入：聚类个数 k ，以及包含 n 个数据对象的数据库。输出：满足方差最小标准的k个聚类。处理流程：（1）从 n个数据对象任意选择 k 个对象作为初始聚类中心；（2）循环（3）到（4）直到每个聚类不再发生变化为止（3）根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分；（4）重新计算每个（有变化）聚类的均值（中心对象） k-means 算法接受输入量 k ；然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个中心对象（引力中心）来进行计算的。 k-means 算法的工作过程说明如下：首先从n个数据对象任意选择 k 个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数. k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。

个人分类: 算法基础|87 次阅读|0 个评论

2-SAT问题

热度 1 cpcs 2010-5-17 13:51

初始2-SAT那时还是在研一时上了一门叫做计算复杂性的课，教材是一本英文的书，很难。当时，第一次接触了不可判定的问题，疯狂地看了很多东西。又系统地学习了复杂度类P,NP(C)，受益颇多。3-SAT就是NPC了，而2-SAT确是P的。所谓2-SAT就是2元可满足性问题。首先，作为众所周知的，任何布尔表达式，都可以化为合取范式的形式，即化为： () and () and () ...and () 其中括号里面的是用析取符号or 连接的变量或者变量的非的形式。我们一般称，变量或者变量的非为文字,而括号里的叫做子句。可满足性问题是要给所有的变量一个赋值（真或假）使得表达式值为真。而2元可满足性问题，就是化为合取范式后，每个子句最多有两个文字的可满足性问题。 cook定理已经说明，一般地可满足性问题是NPC的。但是值得注意的是，2-SAT却是P的。简单分析一下2-SAT: 它要求每个子句的值都是真。考虑一个子句，a or b，显然如果a取false，则b一定取true，反之亦然。先给出算法：假设2-SAT问题中有N个变量，则构造一个有向图包含2n个节点。每个节点代表一个变量或者变量的非（即代表一个文字）。对每个子句a or b,在途中加2条有向边 (~a,b)和(~b,a) (其中~表示变量的非)。然后对这个有向图求强连通分量，把每个强连通分量看作一个点（缩点），这样新的有向图是无环的（无环有向图又叫DAG）。如果一个强连通分量里同时包含了同一个变量以及它的非，则原问题是不可满足的。否则，我们可以构造解，对这个DAG可以进行拓扑排序，按照节点的拓扑排序顺序的倒序进行如下操作：找到此顺序中第一个没有标记的节点，把此节点标记成true，并且把和此节点矛盾的节点（一个节点包含了a，另外一个节点包含了~a，则称它们是矛盾的），以及祖先标记成false，直到所有节点都有标记，结束。这些标记也对应着变量的取值。大概不严谨地证明一下，首先同一个强连通分量里的文字是等价的。因为对一个子句a or b，按照一个取假，另外一个一定取真的意思，连的边表示逻辑中的蕴含关系，即有~a-b，~b-a。这样一个强连通分量里的文字互相蕴含，所以是等价的。于是，当存在a-~a-a时，显然原问题不可满足。第二，因为每标记一个true，立刻把与它矛盾的并且反向蕴含的点都设置为false，所以，这样的赋值不会产生矛盾。第三，不会把一个变量和它的非都设置为false。这是因为，考虑设置变量为false时，假设设置a为true，沿着反向蕴含链把x设置为false了，这说明有x-~a,由于对称性，有a-~x （这里的-表示有路相连，并不一定是一条边），按照算法流程必须要先考虑~x （拓扑排序的逆序），可见这时~x应该已经被设置为true了，因为否则的话，如果~x=false，则会沿着反向蕴含链把a也设置为false的，根本不会到考虑a为true的这一步骤了。于是，设置false是安全的。综上所述，该算法可以找到一组2-SAT的可行解，或者判断无解。该算法的复杂度：求强连通分量、拓扑排序、以及遍历图都是O(m)的，其中m是边数。从网上找了段2-SAT的C++类的代码，修改了一下： #include #include #include #include using namespace std; const int N = 5050;//最大人数 const int inf=6000001; class SAT { private: vector g ;//原图边连接情况 int n, M, h , id ;//id , low , cur ; int stack , top, est , etop; vector tree ;//有向无环图的边连接情况(新图) vector contain ;//新图中每个点都包含原图中的哪些点 void dfs(int); void tsDfs(int); void topologicalSort(); void colorDfs(int); void color(); void tagAnswer(); void printAnswer(); void getOneAnswer(); void buildGraph(); public: void scR(); void build(int); bool judge(); bool solve(); void make(int,int); }; /* 函数build是对原图初始化(根据实际输入情况做相应的更改) */ void SAT::make(int x,int y) { // x || y 负数表示非 1=|x| , |y| =M 注意从1开始 int x1,x2,y1,y2; if (x 0) { x1 = x - 1; x2 = x1 + M; } else { x2 = -x - 1; x1 = x2 + M; } if (y 0 ) { y1 = y - 1; y2 = y1 + M; } else { y2 = -y - 1; y1 = y2 + M; } g .push_back(y1); g .push_back(x1); } void SAT::build(int num) //变量个数 { int i; M = num; n = M 1; for (i = 0 ; i n ; ++i) { g .clear(); } } void SAT::dfs(int src) { etop = top = 0; stack = src; while(top != 0) { intc = stack ; if(dfn == -1) { h = dfn = low = cnt++; est = c; } for(; cur = 0; cur --) { int no = g ]; if(dfn == -1) { stack = no; break; } if (h low ) { h = low ; } } if(cur = 0) continue; top--; int k; if(h != low ) { low = h ; continue; } do { k = est ; id = scnt; low = N; } while(k != c); scnt++; } } /* 函数scR和dfs是求原图的强连通分量(代码由wywcgs原创) */ void SAT::scR() { int i; memset(dfn, 0xff, sizeof(dfn)); cnt = scnt = 0; for(i = 0; i n; i++) { cur = g .size()-1; contain .clear(); } for(i = 0; i n; i++) if(dfn == -1) dfs(i); /* 统计每个强连通分量都包含哪些点，为后面求可行方案做准备。如果不求可行解，可注释掉。 */ for ( i=0;i { contain ].push_back(i); } } /* 函数judge判断是否能找出一个可行方案出来 */ bool SAT::judge() { int i; for ( i=0;i if (id ==id ) return false; return true; } /* 函数buildGraph把每个强连通分量作为一个点，重新构图。(缩点，得到的是一个有向无环图) 用的是链接表的形式，可能有很多重边。可以加一些预处理消除重边。 */ void SAT::buildGraph() { int i,j; for (i=0;i tree .clear(); for (i=0;i for (j=0;j { int a=id ; int b=id ]; if (a!=b) { tree .push_back(a); } } } void SAT::tsDfs(int k) { dfn =cnt++; for (int i=0;i { int w=tree ; if (dfn ==-1) { tsDfs(w); } } low =k; } /* 函数topologicalSort和tsDfs是对新图进行拓扑排序，排序后的结果存在low数组中 */ void SAT::topologicalSort() { int i; for ( i=0;iscnt;i++) { dfn =-1; low =-1; } int nn=scnt; cnt=scnt=0; for ( i=0;inn;i++) { if (dfn ==-1) tsDfs(i); } } /* 函数color和colorDfs是对新图进行着色，新图中着色为1的点组成一组可行解 */ void SAT::color() { int i; for ( i=0;i dfn =-1; for ( i=scnt-1;i=0;i--) if (dfn ]==-1) { /* 新图中low 着色为1后，它的矛盾点应标记为2 */ int a=contain ] ;//在原图中找一点属于强连通分量low 的点a，点a所属组的另一点b所属的强连通分量id 一定是low 矛盾点。 int b; if (a = M) b= a - M; else b= a + M; dfn ]=1; if (dfn ==-1) colorDfs(id );//由于依赖关系，有id 能达的点都是low 的矛盾点 } } /* 函数tagAnswer由新图对原图的点进行标记，得到原图的可行解 */ void SAT::tagAnswer() { int i,j; for ( i=0;i low =-1; for (i=0;i if (dfn ==1)//i为新图中可行解包含的点，那么原图中强连通分量属于i的点都是原图中可行解的点 { for ( j=0;j low ]=1; } } /* 函数printAnswer打印原图的可行解 */ void SAT::printAnswer() { } /* 函数getOneAnswer得到原图的一组可行解 */ void SAT::getOneAnswer() { buildGraph(); topologicalSort(); color(); tagAnswer(); } /* 函数solve可根据实际要求，进行更改输出 */ bool SAT::solve() { scR(); if (judge()) { //puts(YES); //getOneAnswer(); //printAnswer(); return true; } else { //puts(NO); return false; } } 用法：先build(n) n是变量的个数，再通过make(i,j) 加入子句 xi or xj (负数表示变量取反 i,j是正整数 ) solve判断有无解，getOneAnswer得到一组赋值，printOneAnswer根据情况输出一组解可优化的地方：可以用set存放临接表，进而去除重边。拓扑排序可以写成非递归的，而不用递归的dfs 小技巧：表示xor 关系的表达如果要表示a xorb = true 即 a b有且仅有一个为true 则可以表达为2个子句： a orb 和 ~a or ~b 表示同或关系即a xorb = false 即a=b 则可表达为两个子句： ~a orb和 a or ~b 表示 a and b = true 即两个都是true 可以表达为2个子句 a or a 和b or b 表示 a and b = false 即至少有一个是false 可以表达为: ～a or ~b 表示 a or b = false 即全是false 可表达为 ~a or ~a和~b or ~b 表示 a为true时 b不能为false 可以表达为 ~a or b 作为acm算法的训练题： http://acm.pku.edu.cn/JudgeOnline/problem?id=2723 http://acm.pku.edu.cn/JudgeOnline/problem?id=2749 http://acm.pku.edu.cn/JudgeOnline/problem?id=3207 http://acm.pku.edu.cn/JudgeOnline/problem?id=3648 http://acm.pku.edu.cn/JudgeOnline/problem?id=3678 http://acm.pku.edu.cn/JudgeOnline/problem?id=3683

个人分类: 技术|15421 次阅读|2 个评论

[转载]【趣闻】Google不让C语言之父提交代码

NatureXin 2010-4-22 10:09

2010-04-22 01:39 | 次阅读 | 【已有 23 条评论】发表评论关键词： Google | 感谢 liujiangCE 的提供 | 收藏这篇资讯哀悼结束，生活还要继续。说段趣闻吧。大家都知道，C语言和Unix的发明者、图灵奖得主、最具传奇性的程序员Ken Thomson加盟Google之后，与一帮高手一起捣鼓出了又一惊天之作：并发时代的系统编程语言Go。Go一经面世就闯入了编程语言排行榜前20，创造了奇迹。可是， Gawker网站今天爆料，他在Google居然没有提交代码的权力！原因呢，只不过是按公司规定，所有程序员必须通过编程语言考试，而他还没有参加过这种考试，至少在《Coders at Works》一书写作前： Peter Seibel: 我知道Google有一个规定，每个新员工都要在接受编程语言测试之后，才允许提交代码。那就是说你也得考（你自己发明的）C罗？ Thompson: 是啊，我还没考呢。 Seibel: 你还没考？难道你还不能提交代码吗？ Thompson: 是啊，我不能提交代码，不行我只是还没有去考试，还没觉得有必要去考。看来Google真是一家唯算法唯规则的公司。三年前，Google曾被曝光用算法和机器人程序来给申请者提交的简历打分。此外还有很多招聘和面试程序中的古怪事情不断见诸报端。无独有偶，昨天成为CSDN头条的文章从盖茨到扎克伯格：极客的力量中，也爆出开发Mac操作系统核心程序员之一Hertzfeld现在在Google也不快乐：使赫兹菲尔德发生变化的不只是时间，还有他的工作环境。谷歌将工程师看作最重要的资产，认为员工必须喜欢自己从事的工作，同时支持开源软件。但赫兹菲尔德承认，谷歌是一家大公司，在产品设计方面有严格的标准和程序，因此减少了他工作中的乐趣。他说：我与工作的关系是艺术家与他的作品的关系，但在谷歌，我无法从自己的工作中获得快乐。尽管个人的控制力降低了，但赫兹菲尔德拥有了产生更大影响的可能性。有时，谷歌的几行代码可能会影响成千上万的人，这为他的工作带来了一种激情。他说：这里的一切都是主流的。谷歌、iPhone，这些比上世纪60年代甲壳虫乐队更能影响文化，它们甚至会影响整个人类。对了，《Coders at Work》一书是对15位顶级程序员（包括图灵奖得主高德纳、Erlang和JavaScript 之父、Norvig、Guy Steele等等大师）的访谈集，在同类书中是最有趣、最有料而且最精彩的一本。中文版还在翻译中，将由人民邮电出版社图灵公司出版。微软研究院的邹欣做了不错的读书笔记1 ， 2 ， 3 ， 4 ，大家可以去先睹为快。搞技术的，了解高手的思想有时候至关重要。

个人分类: 未分类|3239 次阅读|0 个评论

Dantzig–Wolfe分解方法

putin24 2010-4-19 16:59

DantzigWolfe decomposition ， DantzigWolfe 算法解决特殊的线性规划问题，它是 George Dantzig 和 Phil Wolfe 在 1960 年建立起来和并得到发展，依靠 Delayed Column Generation 算法改进为了解决大规模线性规划问题。在重复使用单纯形法 (Simplex Algorithm) 解决大多数的线性规划问题，发现很多的列 ( 变量 ) 是多余的，基于这样的事实，提出主要问题包含最少的活动列 ( 基本矩阵 basis) ，然后使用子问题去生成列 ( 变量 ) 填入基本矩阵来改进目标函数。 1. 需要条件线性规划的约束矩阵必须具有特殊的形式，约束集合必须被定义为 connecting, coupling, complicating 三种约束且约束系数不为零。剩下约束被建立为系数不为零的独立子矩阵，简单的描述： D1 D2 Dn F1 - - - - F2 - - - - Fn - 其中 D 矩阵表示的是耦合约束关系而 F 表示独立的子矩阵。 2. 算法的步骤 1. Starting with a feasible solution to the reduced master program, formulate new objective functions for each subproblem such that the subproblems will offer solutions that improve the current objective of the master program. 1. 建立已简化矩阵的可行解，公式化子问题的目标函数，子问题的解会改善主规划的目标； 2. Subproblems are re-solved given their new objective functions. An optimal value for each subproblem is offered to the master program. 2. 重新计算子问题新的目标函数，每一个子问题的解提供给主规划； 3. The master program incorporates one or all of the new columns generated by the solutions to the subproblems based on those columns' respective ability to improve the original problem's objective. 3. 主规划集成 1 个或者所有新列，这些新列由子问题根据自身优化生成的解，从而来改进初始主规划的目标函数。 4. Master program performs x iterations of the simplex algorithm, where x is the number of columns incorporated. 4. 主规划重复 x 的单纯形法的迭代， x 表示的列已经被集成进去了为止； 5. If objective is improved, goto step 1. Else, continue. 5. 主规划的目标函数被优化，否则继续循环； 6. The master program cannot be further improved by any new columns from the subproblems, thus return. 6. 通过改进各个子问题的目标解，主规划还不能被继续优化，那么返回。 3. 应用 DantzigWolfe decomposition 在数学建模语言 AMPL 、 GAMS 得到过实现，该算法如果子问题目标解完全独立，那么可以对子问题平行同时处理。参考文献： George B. Dantzig and Philip Wolfe. Decomposition Principle for Linear Programs. Operations Research 8 (1960) pp 101111 wiki英文介绍： http://en.wikipedia.org/wiki/Dantzig%E2%80%93Wolfe_decomposition

个人分类: 学术笔记|20075 次阅读|0 个评论

C#实现基于三角网的等值线追踪及填充算法

热度 15 moustudio 2010-3-16 15:15

Captain Dialog 2010-03 1 引言介绍等值线是一种离散数据的图形表示方法，在水利、土木、地质、石油勘探等工程和技术领域内广泛的应用。常规的等值线绘制通常采用网格法，其绘制的步骤一般为：离散数据网格化；等值点的计算；等值线的追踪；光滑和标记等值线等。等值线图的显示方式一般有两种： (1) 等值线显示，即采用线条上加注数值标记的方式显示数据，这种方式的特点是简捷； (2) 采用彩色填充的方法来显示数据，既用不同的颜色来显示不同的数据，这种方法的特点是比较直观。两种方法的计算机实现也各不相同，一般来说，它们都需要将数据进行要用到的网格网格化。第一种方法必须进行等值线的追踪、光滑和标记等值线。而第二种方法可以在追踪出等值线的基础上进行，也可以不做等值线的追踪直接在网格数据上进行操作。方法实现的难易程度各不相同。本文参考了文献【 1 】填充等值线的方法原理，并针对文中的寻找出来用于填充的多边形不是最小多边形进行改进。基于计算机图形学的基于左转算法的多边形自动搜索方法可以有效的识别最简单多边形，并结合方位角计算排除重复的多边形。借此提高了填充的效率。并且，结合计算机绘图的原理，本文还在填充的基础上，实现了等值线的追踪，相对经典的等值线追踪算法，此法更加简单，易于编程。针对非规则数据（即散乱点数据），本文同样提出了构造等值线的方法，首先采用计算机图形学中的二维。。。生成非规则的三角形网格，然后针对每个三角形使用类似规则矩形的处理方式，可顺利解决不规则等值线的绘制问题。 2 散乱点数据的三角网生成针对不规则形状的等值面，需要对特殊情况进行边界的处理，用规则网格情况下，经常进行等值线的边界进行先扩充再裁剪等方式，结果使得等值面的边界为锯齿状边界；然后利用三角形来构造边界，则会使得边界区域光滑，从而消除锯齿的产生。因此，在处理由散乱点数据构成的不规则等值面时，需要首先对所有的数据点进行三角网的生成，用三角网来构建等值面。 3设计的技术细节关键点 1 、等值线的标注：标注的数值通常写在曲线比较平坦的部分，方法如下： (1) 寻找标注位置。为寻找曲线比较平坦的部分，依次找出 3 点，计算 3 点间两线段的夹角，若夹角大于 120~ ，则认为该处适合标注。 (2) 调整等值点顺序。要求标注的数值写至等值线中间时，需断开原等值线。若原等值线是非闭合曲线，则被分成两段，原来的等值线起始点和终止点不变，但在切断处增加一个新的终止点和一个新的起始点；若原等值线是闭合曲线，则可当作非闭合曲线处理，把起始点和终止点位置调整到切断的位置。 2 、等值线的追踪：从图形角度分析，可利用当前点的颜色值，确定出一条等值线。 3 、等值线的光滑处理：三次 B 样条函数处理插值处理等值线的计算判断格网的一条边是否与雨量值为的等高线相交，要看这条边的两个端点的雨量值是否含有这个值，例如点 A 、 B 是某个三角网的两个顶点，其雨量值分别为及，则边 AB 是否与雨量值为的等高线相交，应判断不等式 ( 一 )(He 一 ) 0 是否满足，就可以知道边 AB 是否与等高线相交。以往的此类算法为 J 编程的简单，对于 W= 或： He 的情况，采用将雨量值增加微小值的方法，对于此类情况作了专门处理，不需要改动雨量值而是直接追踪，使生成的雨量线更为准确。如图 1 ，穿过点 A 的雨量线可以看成如虚线的雨量线来处理，只是点 F 和点 G 退化到了点 A ，这样追踪时就要经过边 AB 、边 AE ，相当于绕着顶点转到了边 DE 。判断一条边 AB 是否与等值线 W 相交的依据为：升级处理：计算机中，除法容易导致崩溃，因此采用乘法处理： 4 、以颜色表为等值线值 5 、程序实现应该用类似于计算机图形学的东西来实现，并且针对三角网等图元，采用面向对象的思路，使得每个图形元素的属性值可以得到灵活的操作性。点 --- 线 --- 三角形相同属性的点构成线；相同属性的线封闭构成块；点又可分为普通的数据点（控制点）、等值点（用于构成等值线）。线于是也可分成边界控制线（由普通电构成）和等值线（由等值点构成）。功能设计：点： Cmou_Point ID 号？坐标属性（ x ， y ）、具体的属性值（ V ）所属的线号（ list_ID_Line ）？点的类型（原始数据点，等值点） Note ：在设计过程中，为了保证数据的完整性，基于点构造出来的段、线、三角形等包含的点信息，一律采用点的 ID 号表示，这样，针对点的修改就可以很容易实现，修改一处，用到该点的其他地方就不用重复修改了。同样，线号、段号都是这个用处！段： Cmou_Segment ID 号包含的起点和终点 StartPoint 、 EndPoint 所属的线号 (list_ID_Line) 所属的三角形编号（ list_ID_Triangle ）段的类型（想对于三角形来说：普通边、等值边，即含有等值点的边）线： Cmou_Line ID 号（ ID ）线的类型（三角形边线，等值线，）包含的数据点集（ list_Point ）线所属的三角形 ID 号 (list_ID_Triangle) 三角形： Cmou_Triangle ID 号 // 三角形包含的边线（ list_Line ）三角形包含的线段 : （ Cmou_Segment 类型） Edge0 、 Edge1 、 Edge2 利用线段构成了三角形在三角形边上找到等值点后，三角形需要细分为多个三角形？点集： list_Point_Scatter 原始的散乱点数据集 List_Point 所有用来生成三角形网格的数据点（包括原始数据点和新增的等值点）三角形的等值线追踪时，可以通过三角形边线上的 ID_Triangle 追踪到与之相邻的三角形（两个相邻的三角形共边）等值线？？ Cmou_ContourLine ID 编号关于三角形的追踪，可以构造出一条条的 Cmou_Line ，然后绘制显示即可。 // 关于三角形的填充，可以最后根据三角形所含的数据点的 V 值，构造出人意形状的多边形， // 然后按照等值线的数值进行填充。关于等值线的填充，完全可以按照等值线的值的大小排列，由两条等值线构成多边形，然后再用对应的颜色填充。多边形： Cmou_Polygon ID List_Point 包含的点集 Vstart 、 Vend 属性值信息等值线追踪算法描述： (1) 非闭合等值线对应等值边系列的搜索。 ① 以某等值线的数值为依据，先在边界边上找到一条等值边作为起始边，若找不到这样的起始边，则说明该等值线闭合，执行 (2) 。将该边记录到等值边系列后，从待搜索边系列中剔除。 ② 在起始边相关三角形的相关边上寻找第二条等值边，找到后加入等值边系列，并将其从待搜索边系列中剔除。 ③从待搜索三角形系列中剔除等值线已经过的三角形，则最新找到的等值边只有一个相关三角形，在该三角形内搜索下一条等值边，找到后加入等值边系列，并将其从待搜索边系列中剔除。 ④递归执行③ ，直到找到的最后一条等值边是边界边。 ⑤ 一条非闭合等值线的等值边系列搜索完毕。 (2) 闭合等值线对应等值边系列的搜索。 ① 任找一条等值边作为起始边，若找不到这样的起始边，则说明分析不出该等值线，应退出该等值线的分析而开始另一条等值线的搜索。将该边记录到等值边系列，并在该边上作一标志。 ②在起始边的一个相关三角形中寻找第二条等值边，找到后加入等值边系列，并将其从待搜索边系列中剔除。 ③从待搜索三角形系列中剔除等值线已经过的三角形，则最新找到的等值边只有一个相关三角形，在该三角形内搜索下一条等值边，找到后加入等值边系列，并将其从待搜索边系列中剔除。 ④递归执行③ ，直到找到最后一条等值边是起始边。 ⑤一条闭合等值线的等值边系列搜索完毕。 (3) 循环执行 (1) 、 (2) 直到找到所有等值线对应的等值边系列。用线性插值的方法求等值边上对应等值点的坐标。将这些等值点有序地连起来即实现了等值线的自动分析。等值线追踪相关【 3 】：对每条等值线值，等值线的游走可按如下 3 个步骤进行。 (1) 搜索存在等值点的所有三角形：首先在三角剖分后得到的三角形链表中进行搜索，找出所有存在等值点的三角形，并将此三角形添加到一个临时建立的三角形链表中供以后使用 ( 此链表记为 TriCheckedAngleList) 。 (2) 搜索开曲线等值线：从凸边三角形链表 (TriChimbAngleList) 中搜索等值点存在的三角形，找出等值线的起始点，记下点的位置和点所在的边 ( 即两个三角形的公共边 ) 。然后以此公共边在 TfiCheckedAngleList 链表中寻找包含此边的新三角形，找到后，在新三角形中进行等值点的判断和计算，记录等值点和新的公共边，并以新公共边按上述方法继续在 TriCheckedAngleList 链表中游走，直至找不到包含新公共边的三角形为止。需要注意的是在游走过程中，必须将每次找到的新三角形从 TfiChecke3dAngleList 中删除，否则等值点会出现重复。按此方法进行等值线游走后，就得到了两端经过三角形网格边界的开曲线等值线。 (3) 搜索闭合等值线：完成开曲线等值线搜索后，在剩下的 TriCheckedAngleList 链表的三角形中取第一个三角形，在其边上找出等值点后，按步骤 (2) 同样的方法进行等值线游走，直到 TriCheekedAngleList 链表的三角形为空，这样就可搜索出值的所有闭合等值线。 Note ：关键在于如何处理三角形中搜索等值边的递归关系。参考文献 : 庞世明 , 蔡玉华 , 靳文芳 . 等值线图的彩色填充方法 . 计算机应用 . 2004.1 Vol.24,NO.1, 60~62. 李顺新 , 刘俊 , 陈建勋等 . 利用不规则三角网法绘制三峡雨量等值线图 . 2005.4,Vol.36,No.4, 44~46. 赵伟 , 赵卓宁 , 李五生 . 一种有效的离散数据场等值线生成方法 . 成都信息工程学院学报 .2007.2,Vol.22,NO.1 115~121. 2010-2-10 等值线的追踪工作基本完成 2010-2-11 关于等值线的填充：需要制定基于单个三角形的填充，将所有的数据点（包括原始的散乱点、等值点、以及将要添加进去的圆滑插值点）进行任意形状的填充。由此，形成有三套数据点集。每个三角形进行填充的时候都是需要查询这些点集，找出自己的点，然后根据点的属性值构造出任意多边形，再进行填充。终于找到错误的原因了！！！初步确定问题为三角形中的等值点没有连续。如：上面的 44 号三角形（ 102-106-107 ）中顶点和等值点是： 93.877 ， 94.812 ， 94.812 ， 96.260 ， 98.675 （除了红色为等值点，剩下的为顶点）而控制它们的等值线值为： 91.682 ， 94.812 ， 97.943 于是，最后的一个点 98.675 成了孤立点，不能参与到三角形的填充搜索中。解决办法：仔细调试后，发现问题应该是出在等值线的追踪过程中。因此，修改了追踪算法中的一个条件，使得在一般情况下，不会出现上述问题。但是，上面的那种情况没有做处理，只是认为正常的等值线追踪情况下，不可能出现那样的等值点不连续的情况。关于等值线值相应的颜色填充相应的颜色填充，可根据前面等值线填充中的判断等值点的值属于受哪个等值线值控制，取对应的颜色。下标范围是 [ 最小，最大 ) 下一步工作： 1、等值线的光滑 2、等值线的标注 3、等值线的颜色改进 4、任意形状处理 2010-2-23 改进之增加颜色选择按钮修改等值线颜色修改等值线值的字体颜色修改等值线的背景颜色（在等值线填充的情况下无效）增加了图片保存功能

个人分类: 算法研究|26048 次阅读|9 个评论

[转载]数据挖掘领域的十大经典算法

热度 1 limer 2010-3-14 12:29

国际权威的学术组织the IEEE International Conference on Data Mining (ICDM) 2006年12月评选出了数据挖掘领域的十大经典算法：C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Naive Bayes, and CART. 不仅仅是选中的十大算法，其实参加评选的18种算法，实际上随便拿出一种来都可以称得上是经典算法，它们在数据挖掘领域都产生了极为深远的影响。 1. C4.5 C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法. C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进： 1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足； 2) 在树构造过程中进行剪枝； 3) 能够完成对连续属性的离散化处理； 4) 能够对不完整数据进行处理。 C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。 2. The k-means algorithm 即K-Means算法 k-means algorithm算法是一个聚类算法，把n的对象根据他们的属性分为k个分割，k n。它与处理混合正态分布的最大期望算法很相似，因为他们都试图找到数据中自然聚类的中心。它假设对象属性来自于空间向量，并且目标是使各个群组内部的均方误差总和最小。 3. Support vector machines 支持向量机，英文为Support Vector Machine，简称SV机（论文中一般简称SVM）。它是一种監督式學習的方法，它广泛的应用于统计分类以及回归分析中。支持向量机将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面。分隔超平面使两个平行超平面的距离最大化。假定平行超平面间的距离或差距越大，分类器的总误差越小。一个极好的指南是C.J.C Burges的《模式识别支持向量机指南》。van der Walt 和 Barnard 将支持向量机和其他分类器进行了比较。 4. The Apriori algorithm Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。 5. 最大期望(EM)算法在统计计算中，最大期望（EM，ExpectationMaximization）算法是在概率（probabilistic）模型中寻找参数最大似然估计的算法，其中概率模型依赖于无法观测的隐藏变量（Latent Variabl）。最大期望经常用在机器学习和计算机视觉的数据集聚（Data Clustering）领域。 6. PageRank PageRank是Google算法的重要内容。2001年9月被授予美国专利，专利人是Google创始人之一拉里佩奇（Larry Page）。因此，PageRank里的page不是指网页，而是指佩奇，即这个等级方法是以佩奇来命名的。 PageRank根据网站的外部链接和内部链接的数量和质量俩衡量网站的价值。PageRank背后的概念是，每个到页面的链接都是对该页面的一次投票，被链接的越多，就意味着被其他网站投票越多。这个就是所谓的链接流行度衡量多少人愿意将他们的网站和你的网站挂钩。PageRank这个概念引自学术中一篇论文的被引述的频度即被别人引述的次数越多，一般判断这篇论文的权威性就越高。 7. AdaBoost Adaboost是一种迭代算法，其核心思想是针对同一个训练集训练不同的分类器(弱分类器)，然后把这些弱分类器集合起来，构成一个更强的最终分类器 (强分类器)。其算法本身是通过改变数据分布来实现的，它根据每次训练集之中每个样本的分类是否正确，以及上次的总体分类的准确率，来确定每个样本的权值。将修改过权值的新数据集送给下层分类器进行训练，最后将每次训练得到的分类器最后融合起来，作为最后的决策分类器。 8. kNN: k-nearest neighbor classification K最近邻(k-Nearest Neighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。 9. Naive Bayes 在众多的分类模型中，应用最为广泛的两种分类模型是决策树模型(Decision Tree Model)和朴素贝叶斯模型（Naive Bayesian Model，NBC）。朴素贝叶斯模型发源于古典数学理论，有着坚实的数学基础，以及稳定的分类效率。同时，NBC模型所需估计的参数很少，对缺失数据不太敏感，算法也比较简单。理论上，NBC模型与其他分类方法相比具有最小的误差率。但是实际上并非总是如此，这是因为NBC模型假设属性之间相互独立，这个假设在实际应用中往往是不成立的，这给NBC模型的正确分类带来了一定影响。在属性个数比较多或者属性之间相关性较大时，NBC模型的分类效率比不上决策树模型。而在属性相关性较小时，NBC模型的性能最为良好。 10. CART: 分类与回归树 CART, Classification and Regression Trees。在分类树下面有两个关键的思想。第一个是关于递归地划分自变量空间的想法；第二个想法是用验证数据进行剪枝。

个人分类: 生活点滴|7874 次阅读|3 个评论

关于火车票实名制的一个新算法

billzhenxing 2010-2-23 23:05

过年,一张小小的火车票, 愁死这么多人. 作为一个搞计算机的人来说，我很惭愧, 对于火车票的购买就没有一个好的算法来解决吗? 完全可以让我们这个领域的牛人（不是我）设计一个合理的算法. 命题的适用范围（需要解决的问题）: 1. 我的算法可以有效解决一人购买多张票(即可防止黄牛倒票) 2. 可以杜绝假票.(假票估计现在的系统就可以杜绝大部分假票) 3. 现在的火车票上的个人信息太多，容易泄漏。算法描述:(我有没想到地方大家给我补充,给我提出新的问题,我在完善我的算法) 1. 我们可以像公交车的交通卡一样, 给买火车票的人办一张这样的卡, 反正这些过年回家的农民工兄弟,学生....每年至少也要做2次火车(即返乡一次), 所以可以用几十年(甚至终生), 2, 这张卡里保存本人的身份证号,以及火车的目标站信息(比方说目标是B站)。这样一个人在一天（假设到达目标站需要1天）之内只能买一次。到达目标站之后，出站的时候交通卡消磁，然后才可以买返程的火车票。这样顺便也杜绝了逃票的现象。如果是往返，那么就在往返的期限内只能买一次这个区域的车票。如果还想去别的地方，这样的交通卡如果制作，具体不知道多少钱，估计不会太贵。这个成本费我认为农民工也可以负担，因为这张卡受用终身，而且可以保证如果有座的情况下可以买到票。所以大部分人愿意办理。如果以后效果好，可以强制办理。 3，这个交通卡的办理可以到提前到车站派出所办理，或者其他的派出所办理，代售火车票的地方不可以代办。如果有黄牛办理这种假的交通卡，也可以杜绝。方法如下： a, 首先这张卡全国独一无二，如果别人用了你的卡买了火车票导致你买不到火车票，你马上可以到车站相关公安部门举报，只要你带着身份证，证明你de卡被别人盗用，那么这张卡的信息马上就可以在系统查到，持假卡的人在哪里下车，那么在系统上修改，这个持假卡的人就出不了站，自然可以抓到他，问他从哪里买的假卡，从而可以抓到高科技的黄牛。这个黄牛跟盗取别人信用卡的罪名差不多（具体这里不讨论）， b, 举报以后，你的交通卡就又可以正常买票了。最起码你买上票以后。黄牛即使还拥有你身份证号的假交通卡，他们也定不上票了。除非他们认识公安里边的内鬼。 c, 如果没有抓到高科技黄牛，那么你的卡还可能被盗，你以后还是有可能被黄牛抢先一步买票。这个问题的解决就需要，订票的时候来解决。 3, 订票的时候预防靠科技黄牛抢先订票，这个牵扯到手机的实名制（或者网络实名制）。 a, 如果交通卡也是实名制，手机也是实名制，那么订票的时候，可以用手机收到的识别码来解决这个问题。这个识别码是即时任意产生的。不可能被盗用，而且它只能发给本人的手机，高科技黄牛也没有招。 b, 现在还没有实行手机实名制，被黄牛抢先订票，只能就是按照3a的办法作了。

个人分类: 科研相关|12 次阅读|0 个评论

算法的力量—— 李开复

eaglezxw 2010-1-18 13:06

算法是计算机科学领域最重要的基石之一，但却受到了国内一些程序员的冷落。许多学生看到一些公司在招聘时要求的编程语言五花八门就产生了一种误解，认为学计算机就是学各种编程语言，或者认为，学习最新的语言、技术、标准就是最好的铺路方法。其实大家都被这些公司误导了。编程语言虽然该学，但是学习计算机算法和理论更重要，因为计算机算法和理论更重要，因为计算机语言和开发平台日新月异，但万变不离其宗的是那些算法和理论，例如数据结构、算法、编译原理、计算机体系结构、关系型数据库原理等等。在“开复学生网”上，有位同学生动地把这些基础课程比拟为“内功”，把新的语言、技术、标准比拟为“外功”。整天赶时髦的人最后只懂得招式，没有功力，是不可能成为高手的。算法与我当我在1980年转入计算机科学系时，还没有多少人的专业方向是计算机科学。有许多其他系的人嘲笑我们说：“知道为什么只有你们系要加一个‘科学’，而没有‘物理科学系’或‘化学科学系’吗？因为人家是真的科学，不需要画蛇添足，而你们自己心虚，生怕不‘科学’，才这样欲盖弥彰。”其实，这点他们彻底弄错了。真正学懂计算机的人（不只是“编程匠”）都对数学有相当的造诣，既能用科学家的严谨思维来求证，也能用工程师的务实手段来解决问题——而这种思维和手段的最佳演绎就是“算法”。记得我读博时写的Othello对弈软件获得了世界冠军。当时，得第二名的人认为我是靠侥幸才打赢他，不服气地问我的程序平均每秒能搜索多少步棋，当他发现我的软件在搜索效率上比他快60多倍时，才彻底服输。为什么在同样的机器上，我可以多做60倍的工作呢？这是因为我用了一个最新的算法，能够把一个指数函数转换成四个近似的表，只要用常数时间就可得到近似的答案。在这个例子中，是否用对算法才是能否赢得世界冠军的关键。还记得1988年贝尔实验室副总裁亲自来访问我的学校，目的就是为了想了解为什么他们的语音识别系统比我开发的慢几十倍，而且，在扩大至大词汇系统后，速度差异更有几百倍之多。他们虽然买了几台超级计算机，勉强让系统跑了起来，但这么贵的计算资源让他们的产品部门很反感，因为“昂贵”的技术是没有应用前景的。在与他们探讨的过程中，我惊讶地发现一个O(n*m)的动态规划(dynamicprogramming)居然被他们做成了O(n*n*m)。更惊讶的是，他们还为此发表了不少文章，甚至为自己的算法起了一个很特别的名字，并将算法提名到一个科学会议里，希望能得到大奖。当时，贝尔实验室的研究员当然绝顶聪明，但他们全都是学数学、物理或电机出身，从未学过计算机科学或算法，才犯了这么基本的错误。我想那些人以后再也不会嘲笑学计算机科学的人了吧！网络时代的算法有人也许会说：“今天计算机这么快，算法还重要吗？”其实永远不会有太快的计算机，因为我们总会想出新的应用。虽然在摩尔定律的作用下，计算机的计算能力每年都在飞快增长，价格也在不断下降。可我们不要忘记，需要处理的信息量更是呈指数级的增长。现在每人每天都会创造出大量数据（照片，视频，语音，文本等等）。日益先进的纪录和存储手段使我们每个人的信息量都在爆炸式的增长。互联网的信息流量和日志容量也在飞快增长。在科学研究方面，随着研究手段的进步，数据量更是达到了前所未有的程度。无论是三维图形、海量数据处理、机器学习、语音识别，都需要极大的计算量。在网络时代，越来越多的挑战需要靠卓越的算法来解决。再举另一个网络时代的例子。在互联网和手机搜索，如果要找附近的咖啡店，那么搜索引擎该怎么处理这个请求呢？最简单的办法就是把整个城市的咖啡馆都找出来，然后计算出它们的所在位置与你之间的距离，再进行排序，然后返回最近的结果。但该如何计算距离呢？图论里有不少算法可以解决这个问题。这么做也许是最直观的，但绝对不是最迅速的。如果一个城市只有为数不多的咖啡馆，那么这么做应该没什么问题，反正计算量不大。但如果一个城市里有很多咖啡馆，又有很多用户都需要类似的搜索，那么服务器所承受的压力就大多了。在这种情况下，我们该怎样优化算法呢？首先，我们可以把整个城市的咖啡馆做一次“预处理”。比如，把一个城市分成若干个“格子(grid)”，然后根据用户所在的位置把他放到某一个格子里，只对格子里的咖啡馆进行距离排序。问题又来了，如果格子大小一样，那么绝大多数结果都可能出现在市中心的一个格子里，而郊区的格子里只有极少的结果。在这种情况下，我们应该把市中心多分出几个格子。更进一步，格子应该是一个“树结构”，最顶层是一个大格——整个城市，然后逐层下降，格子越来越小，这样有利于用户进行精确搜索——如果在最底层的格子里搜索结果不多，用户可以逐级上升，放大搜索范围。上述算法对咖啡馆的例子很实用，但是它具有通用性吗？答案是否定的。把咖啡馆抽象一下，它是一个“点”，如果要搜索一个“面”该怎么办呢？比如，用户想去一个水库玩，而一个水库有好几个入口，那么哪一个离用户最近呢？这个时候，上述“树结构”就要改成“r-tree”，因为树中间的每一个节点都是一个范围，一个有边界的范围（参考:http://www.cs.umd.edu/~hjs/rtrees/index.html）。通过这个小例子，我们看到，应用程序的要求千变万化，很多时候需要把一个复杂的问题分解成若干简单的小问题，然后再选用合适的算法和数据结构。并行算法：Google的核心优势上面的例子在Google里就要算是小case了！每天Google的网站要处理十亿个以上的搜索，GMail要储存几千万用户的2G邮箱，GoogleEarth要让数十万用户同时在整个地球上遨游，并将合适的图片经过互联网提交给每个用户。如果没有好的算法，这些应用都无法成为现实。在这些的应用中，哪怕是最基本的问题都会给传统的计算带来很大的挑战。例如，每天都有十亿以上的用户访问Google的网站，使用Google的服务，也产生很多很多的日志(Log)。因为Log每份每秒都在飞速增加，我们必须有聪明的办法来进行处理。我曾经在面试中问过关于如何对Log进行一些分析处理的问题，有很多面试者的回答虽然在逻辑上正确，但是实际应用中是几乎不可行的。按照它们的算法，即便用上几万台机器，我们的处理速度都根不上数据产生的速度。那么Google是如何解决这些问题的？首先，在网络时代，就算有最好的算法，也要能在并行计算的环境下执行。在Google的数据中心，我们使用的是超大的并行计算机。但传统的并行算法运行时，效率会在增加机器数量后迅速降低，也就是说，十台机器如果有五倍的效果，增加到一千台时也许就只有几十倍的效果。这种事半功倍的代价是没有哪家公司可以负担得起的。而且，在许多并行算法中，只要一个结点犯错误，所有计算都会前功尽弃。那么Google是如何开发出既有效率又能容错的并行计算的呢？ Google最资深的计算机科学家JeffDean认识到，Google所需的绝大部分数据处理都可以归结为一个简单的并行算法：MapandReduce（http://labs.google.com/papers/mapreduce.html）。这个算法能够在很多种计算中达到相当高的效率，而且是可扩展的（也就是说，一千台机器就算不能达到一千倍的效果，至少也可以达到几百倍的效果）。MapandReduce的另外一大特色是它可以利用大批廉价的机器组成功能强大的serverfarm。最后，它的容错性能异常出色，就算一个serverfarm宕掉一半，整个fram依然能够运行。正是因为这个天才的认识，才有了MapandReduce算法。借助该算法，Google几乎能无限地增加计算量，与日新月异的互联网应用一同成长。算法并不局限于计算机和网络举一个计算机领域外的例子：在高能物理研究方面，很多实验每秒钟都能几个TB的数据量。但因为处理能力和存储能力的不足，科学家不得不把绝大部分未经处理的数据丢弃掉。可大家要知道，新元素的信息很有可能就藏在我们来不及处理的数据里面。同样的，在其他任何领域里，算法可以改变人类的生活。例如人类基因的研究，就可能因为算法而发明新的医疗方式。在国家安全领域，有效的算法可能避免下一个911的发生。在气象方面，算法可以更好地预测未来天灾的发生，以拯救生命。所以，如果你把计算机的发展放到应用和数据飞速增长的大环境下，你一定会发现；算法的重要性不是在日益减小，而是在日益加强。

个人分类: 科研短讯|2085 次阅读|0 个评论

多一点思想

sgshan 2010-1-5 14:05

要是从研究生算起，自己从事科研工作也已经10年有余了。所谓十年磨一剑，应该说自己一直在努力，想磨一把利剑出来，但这谈何容易？愚钝如我之人，没有长期的积累，哪里会有利剑？所以，实际上自己手中的剑还是磨得很钝。

个人分类: 未分类|24 次阅读|0 个评论

OpenCV 开源算法库小小的介绍

bluewind23 2009-10-22 10:19

OpenCV是Intel资助的开源计算机视觉库。它由一系列 C 函数和少量 C++ 类构成，实现了图像处理和计算机视觉方面的很多通用算法。 OpenCV 拥有包括 300 多个C/C++函数的跨平台的中、高层 API。它不依赖与其它的外部库，尽管也可以使用某些外部库。 OpenCV 对非商业应用和商业应用都是免费（FREE）的。（细节参考发布版本的 license）。另外OpenCV 也为Intel公司的 Integrated Performance Primitives (IPP) 提供了透明接口。 OpenCV 主要库特征：图像数据的操作 ( 分配、释放、复制、设置和转换)。图像与视频的输入输出I/O （文件与摄像头的输入、图像和视频文件输出）。矩阵和向量的操作以及线性代数的算法（矩阵积、解方程、特征值以及奇异值等）。各种动态数据结构（列表、队列、集合、树、图等）。基本的数字图像处理（滤波、边缘检测、角点检测、采样与差值、色彩转换、形态操作、直方图、图像金字塔等）。结构分析（连接部件、轮廓处理、距离变换、各自距计算、模板匹配、Hough变换、多边形逼近、直线拟合、椭圆拟合、Delaunay 三角划分等）。摄像头定标（发现与跟踪定标模式、定标、基本矩阵估计、齐次矩阵估计、立体对应）。. 运动分析（光流、运动分割、跟踪）。目标识别（特征提取、特征法、隐马尔可夫模型：HMM）。基本的GUI （图像与视频显示、键盘和鼠标事件处理、滚动条）。图像标注（线、二次曲线、多边形、画文字） OpenCV 主要库模块： cv 主要的OpenCV 函数。 cvaux 辅助的（实验性的）OpenCV 函数。 cxcore 数据结构与线性代数支持。 highgui 图像界面函数。 ml - 机器学习函数（统计分类、回归以及聚类等）中文官方网站： http://www.opencv.org.cn/ 软件下载： http://sourceforge.net/projects/opencvlibrary/ YAHOO讨论组： http://groups.yahoo.com/group/OpenCVOpenCV 参考本书以及OpenCV安装包中提供的例子：大量的样例程序是了解OpenCV最直接的方法

个人分类: 学习研究|14463 次阅读|0 个评论

科学网读者算法1

liux831 2009-10-10 22:05

科学网约有2500个注册用户，62000个读者。在生态学上，可以标识抽样，估算总样本。采用我们发明的标识法测算，注册用户和未注册用户为1：25. 在科学家这个群体，在科学网注册的用户很少。国外和国内的科学家关注科学网还很不够。要办好科学网，需要采取以下措施： 1.征集优秀的博文，像中国杂志办成SCI一样 2.吸引广大科学家来科学网，关注科学网 3.加强科学网管理，主动出击 4.全民办网 5.推崇精品 6.征集Good ideas 7.全面优化 8.大联合拥有更多读者，创造和谐氛围，能人办刊，采用国际规则，都是办好科学网的有力措施。办出特色，力争一流，正是科学网的强兵之策。

个人分类: 未分类|1730 次阅读|2 个评论

Matlab 2009b 已经发布

wdz 2009-9-27 12:04

MATLAB 是一种用于算法开发、数据可视化、数据分析以及数值计算的高级技术计算语言和交互式环境。使用 MATLAB，您可以较使用传统的编程语言（如 C、C++ 和 Fortran）更快地解决技术计算问题。 MATLAB 的应用范围非常广，包括信号和图像处理、通讯、控制系统设计、测试和测量、财务建模和分析以及计算生物学等众多应用领域。附加的工具箱（单独提供的专用 MATLAB 函数集）扩展了 MATLAB 环境，以解决这些应用领域内特定类型的问题。 MATLAB 提供了很多用于记录和分享工作成果的功能。可以将您的 MATLAB 代码与其他语言和应用程序集成，来分发您的 MATLAB 算法和应用。主要功能此高级语言可用于技术计算此开发环境可对代码、文件和数据进行管理交互式工具可以按迭代的方式探查、设计及求解问题数学函数可用于线性代数、统计、傅立叶分析、筛选、优化以及数值积分等二维和三维图形函数可用于可视化数据各种工具可用于构建自定义的图形用户界面各种函数可将基于 MATLAB 的算法与外部应用程序和语言（如 C、C++、Fortran、Java、COM 以及 Microsoft Excel）集成 Release 2009b 的新功能 Release 2009b 包括 MATLAB 和 Simulink的若干新功能，以及对其它 83 款产品的更新和缺陷修复。R2009b 增加了对 64-位 Mac 平台的支持。已经购买 MathWorks 软件维护服务的用户可以下载产品更新。R2009b 也提供了增强的许可中心功能。许可中心是用于激活软件以及管理许可证和用户信息的一个在线工具。 MATLAB 产品系列的新功能包括：重新设计的帮助浏览器，支持从 MATLAB 直接访问 MATLAB Central 文件交换，及其它桌面增强功能扩展了对 MATLAB 和 Image Processing Toolbox 中函数的多核支持，以及对 Statistics Toolbox 中函数的并行支持 Parallel Computing Toolbox 的全新界面，可访问和处理集群上的分布式数组 Image Processing Toolbox 支持处理任意大型图像文件 Mapping Toolbox 支持从网络地图服务 (WMS) 服务器搜索和检索地理数据集在 Fixed-Point Toolbox 进行全局设置，以简化带有使用定点变量的运算 Simulink 产品系列的新功能包括： Simulink、Signal Processing Blockset 和嵌入式 MATLAB中支持用于仿真和代码生成的可变维度信号和数据可用于管理 Simulink 和 Real-Time Workshop 设计方案的模型变量可立即在Simulink 中使用的PID 控制器，以及 Simulink Control Design 的自动调优减少了 Real-Time Workshop 的数据副本，可自定义矩阵运算以用于生成嵌入式信号处理代码 Simulink Verification and Validation 中用于管理和部署配置及自定义检查的Model Advisor Configuration Editor (模型顾问配置编辑器) 新的交互式编译报告,可分析数组大小和其它嵌入式 MATLAB 代码特性 System Requirements Windows Operating Systems 32-bit MathWorks Products Windows XP Service Pack 2 or 3 Windows Server 2003 Service Pack 2 or R2 Windows Vista Service Pack 1 or 2 Windows Server 2008 Processors Intel Pentium 4 and above Intel Celeron** Intel Xeon Intel Core Intel Atom** AMD Athlon 64** AMD Opteron AMD Sempron** Disk Space 680 MB* (MATLAB only) RAM 512 MB (At least 1024 MB recommended) 64-bit MathWorks Products Windows XP x64 Service Pack 2 Windows Server 2003 x64 Service Pack 2 or R2 Windows Vista Service Pack 1 or 2 Windows Server 2008 Processors Intel Pentium 4 and above Intel Celeron** Intel Xeon Intel Core AMD64 Disk Space 680 MB* (MATLAB only) RAM 1024 MB (At least 2048 MB recommended) ====================== * Disk space requirement varies depending on size of partition. The MATLAB installer will inform you of the hard disk space requirement for your particular partition. Installation size will be determined by the installer and can vary for NTFS and FAT formats. ** Processor must support SSE2 instruction set. Graphics 16-, 24-, or 32-bit OpenGL capable graphics adapter License Management Some license types require a license server running FLEXnet 11.6.1, which is provided by the MathWorks installer. TCP/IP is required on all platforms when using a license server. Additional Requirements Microsoft Word 2002, 2003, or 2007 is required to run the Notebook tool in MATLAB. Microsoft Excel 2002, 2003, or 2007 is required to run MATLAB Builder EX (for Microsoft Excel) and Spreadsheet Link EX (for Microsoft Excel). Matlab现在每半年发布一个版本，a为上半年版本，b为下半年版本。下载地址： http://www.verycd.com/topics/2768208/ 迅雷、脱兔、vagaa等吸血客户端用户无法下载

个人分类: 学习|2471 次阅读|0 个评论

[网络资源]ACM TOMS算法源程序下载

fswdong 2009-6-20 08:38

这里提供了ACM TOMS建刊以来所有发表文章相应的算法源程序，宝贵资源，链接地址如下： http://calgo.acm.org/

个人分类: 科研资源|4063 次阅读|1 个评论

劈窗算法LST精度评价和参数敏感性分析

maokebiao 2009-5-29 08:30

摘　要: 介绍了大气模拟数据法，并用此方法分析和评价了作者提出的劈窗算法．采用模拟大气参数计算得到的地表温度平均精度为0．46℃；利用间接方法(即大气透过率是由大气水汽含量计算得到)得到的平均精度为0．60℃．同时对MODIS地表温度产品与我们用MODIS影像反演出来的结果对比分析表明作者提出的劈窗算法是可行的．敏感性分析表明此算法对参数透过率、比辐射率都不敏感．毛克彪，覃志豪，宫鹏 , 余琴 , 劈窗算法精度评价及参数敏感性分析，中国矿业大学学报 ,2005(3):318-322 . PDF下载: 劈窗算法精度评价及参数敏感性分析

个人分类: 星星点灯|5610 次阅读|0 个评论

一份基金标书主要内容

wangyong77 2009-5-3 13:40

一份标书主要内容标书下载

个人分类: 我的想法公开与共享|2272 次阅读|0 个评论

【转载，BYHH BBS】各种算法在追MM过程中的可行性应用和分析

freton 2008-10-29 00:58

动态规划　　你追一个MM的时候，需要对该MM身边的各闺中密友都好，这样你追MM这个问题就分解为对其MM朋友的问题，只有把这些问题都解决了，最终你才能追到MM。　　该方法适用于聪明的MM，懂得看一个人，不是看他如何对你，而是看他如何对他人。的道理，并且对付这样的MM总能得到最优解。　　该方法的缺点是开销较大，因为每个子问题都要好好对待。。。。 -------------------------------------------------------------------- 贪心法　　你追一个MM的时候，从相识到相知，每次都采用最aggressive的方式，进攻进攻再进攻！从不采用迂回战术或是欲擒故纵之法！目标是以最快的速度确立两人关系。　　该法优点是代价小，速度快，但缺点是不是每次都能得到最优解。。。。。 -------------------------------------------------------------------- 回溯算法　　追一个MM，但也许你还是情窦初开的新手，不知道如何才能讨得MM的欢心，于是你只好一条路一条路的试，MM不开心了，你就回溯回去换另一种方式。当然其间你也许会从某些途径得到一些经验，能够判断哪些路径不好，会剪枝（这就是分支估界了）。你也可以随机选择一些路径来实施，说不定能立杆见影（这就是回溯的优化了）但总的来说，你都需要一场持久战。。。。　　该算法一般也能得到最优解，因为大多数MM会感动滴！！但其缺点是开销大！除非你是非要谈一场恋爱不可，否则不推荐使用。特别是你可能还有许多其他的事情要做，比如学习，比如事业。。。。 -------------------------------------------------------------------- 老赵提问：假如一个mm对应NP完全问题,老大给个有效解法俺回答：呵呵，那你为什么那么贱，非要去追呢？记住：天涯何处无芳草！不过如果你非如此不可的话，建议升级你的硬件，好好学习，好好工作，加强实力，人到中年的时候也许你能解开NP难。。。。 Ranger补充：这种MM可遇而不可求了，也就是eshow的终极目标。eshow其实已经开发出了解决NP完全问题的对数级算法，但是不愿意告诉偶们 //////////////////////////////////////////////////////////////////// 在认真研读思考之后，周MM举一反三，对深度优先和广度优先也做了总结：深度优先就是追一个mm追到底，直到失败然后换个mm继续追广度优先就是同时追多个mm，一起发展 //////////////////////////////////////////////////////////////////// 大家都开始集思广益老马：二叉树的前序、中序和后序周游：前序就是直接搞定MM，然后搞定她爸妈（左）和你自己爸妈（右）中序就是先搞定未来岳父岳父，然后搞定她，最后告诉你爸妈后续就是，让未来的岳父岳母和自己爸妈都觉得你们合适之后，才对MM下手，这个时候就没有障碍了啊 --

个人分类: 生活哲思|3079 次阅读|0 个评论

用VBA实现文献计量分析研究中的数据预处理技术

huabolin 2008-10-24 12:16

用VBA实现文献计量分析研究中的数据预处理技术化柏林 ( 中国科学技术信息研究所北京 100038) （发表于《现代图书情报技术》2007年第3期）【摘要】首先对网页数据的特点进行简单分析，针对网页数据的特点设计统计分析的预处理流程，对每一步处理过程都用几种不同的算法进行实验，以期得到最优的解决方案。实验证明，通过减少 IO操作、提高处理粒度、适当使用词表等方法可以提高程序运行速度与准确率。【关键词】　计量分析　实现技术　预处理技术　算法　 excel VBA 【分类号】　 TP311，G35 Implementation of preprocess technology in bibliometric and analytic research via VBA Hua Bolin ( Institute of Scientific and Technical Information of China, Beijing 100038, china) 【 Abstract 】 Process of statistic is designed in accordance with character of web data after analyzing them . Each stage is experimented with some different algorithms in order to achieve optimal solution. According to experiment, efficiency and effectiveness can be improved by decreasing IO operation, increasing process granularity and using lexicon. 【 Keywords 】 bibliometric, implement technology, preprocess technology, arithmetic, excel, VBA 1 　引言从网页上复制来的题录数据，由于不符合关系范式（连 1NF都不符合），直接导入数据库处理起来也很不方便。当前的统计分析，要么直接用统计软件的工具(如SPSS、SAS等)进行统计；要么就直接做成管理信息系统并封装起来，把统计做成与导入、查询相并行的模块，对用户的开放性不够。这类论文(如文献 )的论述主要是关注数据库结构、数据访问接口或检索实现等，而对统计实现以及计量分析技术的探讨很不充分，对关注文献计量的非技术人员的启迪也较少。目前的应用型文献统计分析缺乏把二者结合起来，在相应的统计软件里进行简单的编程实现多式多样的统计，把简单的工具用活用好来解决现实的复杂问题。因此几万条之内的小数据量统计分析的量佳方案是通过 VBA在excel里进行,因为它不需要很强的计算机编程能力，只要掌握好for 循环、条件判断和常用字符串处理函数就够了。 2 数据来源格式分析中国期刊全文数据库(清华同方)与中文科技期刊全文数据库(重庆维普)都提供每页显示50条详细记录，如图1所示。数据库商的检索结果是单列的形式，把它复制到excel表格里时，字段名与记录值分布在同一列里，这是因为在显示检索结果的网页里，字段名与记录值在同一个TD/TD标签对里。分析时除标题外，其它字段皆从]的后一个字符开始取就是记录的值。网页复制过来的数据预处理主要包括以下几个步骤：通过转换把它变成二维表格的形式；滤掉通知类非正式文献；根据标记符拆分作者、关键词、分类号等字段；析取多项目字段，从机构字段中提取作者单位、城市名、邮编等，从期刊字段中析取期刊名、年、卷期号、起止页码等信息。图 1 　重庆维普期刊全文数据库检索结果全记录显示示例图 3 行列转换与过滤从图1复制过来的数据，首先要把它转换成二维表格的形式，就是把单列数据按不同字段转换成多行多列的形式，其关键是识别一条记录的始末，具体处理方法如下所述。算法一。遍历所有有效行，如果行数被iFieldCount整除，把源表的单元格值赋给目标表相应行的末列；如果不是整除行，就把源表的单元格值赋给目标表相应行的余数列。此算法对于缺乏程序设计思想的人比较容易理解，类似于最直接的手工操作方式，一个值一个值地赋，一条数据结束后回车换行。 1: For i = 1 To iRowCount 2: sTemp = Trim(Worksheets(sSrce).Cells(i, 1)) ' 如果整除就换行，不整除就放在当前行相应的列里 3: If i Mod iFieldCount = 0 Then 4: Worksheets(sDest).Cells(k, iFieldCount) = sTemp 5: k = k + 1 6: Else 7: Worksheets(sDest).Cells(k, i Mod iFieldCount) = sTemp 8: End If 9: Next 算法二。每遇到一条记录进行一次操作，一次把该记录的所有字段赋过去。算法比较容易理解，特别是对具有关系数据思想的人。两重for循环合起来（iRowCount除以iFieldCount再乘以iFieldCount）的赋值语句执行次数与算法一相当，速度要快一些，因为不用执行条件判断。程序代码如下： 1: For i = 1 To iRowCount step iFieldCount 2: k = k + 1 3: For j=1 to iFieldCount 4: sTemp = Trim(Worksheets(sSrce).Cells(i-j, 1)) 5: 　 Worksheets(sDest).Cells(k, j) = sTemp 6: Next 7: Next 算法三。此算法把条件写到控制目标表行列的变量里去，用i与iFieldCount的商控制行，用它们的余数控制列。程序代码简单，可读性差。 1: For i = 1 To iRecCount 2: sTemp = Trim(Worksheets(sSrce).Cells(i, 1)) 3: Worksheets(sDest).Cells(i / iFieldCount + 1, (i - 1) Mod iFieldCount + 1) = sTemp 4: Next 经过行列转换后滤掉所有通知类文献，包括征稿简则、会讯通知、年度索引等。此类文献的特征是没有作者或作者单位，作者为无，作者单位为不详。数据处理完的结果如图2所示。图 2 　行列转换后的数据格式示例图 4 拆分格式转换后有两类字段不符合一范式，一类是多值同字段，如作者、机构、关键词、分类号等，一篇文章有多个作者、多个关键词、多个分类号等，但这些词的属性是同质的。另一类是多值异字段，如清华同方的单位或重庆维普的机构都含有三项内容，分别为作者所在单位、地名、邮编等信息，这些字段是异构的，数据类型、长度与取值范围都有所不同，重庆维普的刊名也含有很多信息，包括期刊名称、年、卷、期、起止页码等，需要进行拆分。在维普中文科技期刊数据库里，多于一个作者的都会加上标记，并在其后加上空格；对于机构，在多机构的前面加，不同的机构间以空格分开；关键词、分类号用空格自然切分。如果是清华同方的数据库，则每位作者后都会有分号，而关键词之间用双分号相隔。具体处理方法如下：算法一。如果待分析串里含有标记符，就析取标记符前面的值，同时把指针移到分隔符后面的位置，也就是截取待分析串。如果待分析串里已没有分隔符，则把最后一个值赋过去。 1: For i = 1 To iRecCount 2: sTemp = Worksheets(sSrce).Cells(i, iCol) 3: For j = 1 To 20 4: iFind= InStr(1, sTemp, sFlag) 5: 如果含标记符就析取 6: If iFind 0 Then 7: Worksheets(sDest).Cells(i, j) = Mid(sTemp, 1, iFind - 1) 8: sTemp = Mid(sTemp, iFind+ iFlagLen) 9: Else 10: Worksheets(sDest).Cells(i, j) = sTemp 11: Exit For 12: End If 13: Next 14: Next 算法二。从字串首字符到末尾，如果是分隔符，则把前面的值赋过去，并把存放分隔符前面值的变量清空；如果不是分隔符，则把该字符压入队列，相对于队列的零存整取操作。同算法一比较，内循环的执行次数显然增多，但中间计算比较简单。 1: For i = 1 To iRecCount 2: sTemp = Worksheets(sSrce).Cells(i, iCol) 3: For j = 1 To len(sTemp) 4: If mid(sTemp, j, 1) =sFlag Then 5: Worksheets(sDest).Cells(i, j) =sSplit 6: sSplit= 7: Else 8: sSplit=sSplit mid(sTemp, j, 1) 9: End If 10: Next 11: Next 仅仅通过标题来确定一条记录并不可行，标题不能作为主码，因为标题会有重复，为每篇文章加一个ID是个好的选择。本实验中并未作主码处理，需要其它信息时再去图3所示的表里找，因为图3显示内容与图2显示内容是行对应的。拆分完的结果如图3所示。　图3 关键词拆分结果示例图 5 提取关键词与作者的拆分属于同构拆分，还有一些列的拆分属于异构拆分。就是一个单元格里存在着多个字段内容。如机构、期刊等信息不符合第一范式（1NF），这些字段可以再分。拆分过的机构包含作者单位、城市、邮编等信息，如南京大学信息管理系，南京210093，特点是单位与城市名间以逗号分隔，城市名与邮编紧密相连。作者单位的提取从字符串开头取，取到逗号分隔符；城市名的提取比较困难一些，有的城市名是两个字符，而有的城市名是三个字符，所以不能用从逗号的下一个字符开始取定数个字符，可以采用从逗号的下一个字符开始取，取到数字为止，或者先去掉右6位，再从逗号开始取，因为邮编都是6位，无一例外。可是由于有些编辑部要求不严或数据库加工商粗糙等原因致使机构的信息非常复杂，机构主要有以下几种情况：类别特征描述举例问题责任者项目齐全、内容完整、格式规范单位与城市名间加逗号，城市与邮编中间加空格的形式武汉大学信息资源研究中心，武汉 430072 正常项目齐全、内容完整、格式不规范单位与城市名中间缺少逗号，或者地名与邮编中间缺少空格南京理工大学经济管理学院南京 210094 编辑部或数据加工商项目齐全、内容完整、格式规范、地名表述不规范城市名后带有市标记城市名前加省名，直接用省名代替城市名河北工业大学图书馆，天津市 300130 江汉石油学院，湖北荆州 434102 聊城大学图书馆，山东 252059 编辑部或数据加工商一人多单位情况单位之间用双斜杠加以区分河北大学管理学院，保定 071002 ／／中科院研究生院，北京 100039 ，正常项目不齐全、内容完整缺少邮编缺少城市和邮编美国密苏里大学，美国江苏理工大学图书馆编辑部项目不齐全、内容不完整单位名称不完整，或城市名不完整，或邮编不是 6 位南京大学信息管理系，南数据加工商作者单位所在的城市大都是地级市以上的城市，落座在县级市的也有，如曲阜师范大学就落座在山东的曲阜。因为有了邮编，所以不需要在城市名前加省名。如果含有邮编, 先把邮编取出来，因为邮编肯定是数字，正常情况下应该是六位，而且在末尾。如果含有标记符，根据标记符提取，把逗号左边的内容提取出来作为机构，逗号后面的内容为城市名；如果不含标记符，可以用城市列表来从右边进行匹配，这种办法准确率高，但会影响速度，前提是有权威的中国城市名库。也可以用机构名后缀进行截取，需要人工分析机构名后缀特征，然后构造数组来进行匹配。简单处理算法如下：邮编处理 1: If Asc(Right(sTemp, 1)) 47 And Asc(Right(sTemp, 1)) 58 Then 2: sPostcode = Right(sTemp, 6) 3: sTemp = Mid(sTemp, 1, Len(sTemp) - 6) 4: End If 串中含标记符，如分号、逗号等 5: If InStr(1, sTemp, sFlag) 1 Then 6: sAffiliation = Left(sTemp, InStr(1, sTemp, sFlag) - 1) 7: sCity = Mid(sTemp, Len(sAffiliation) + 2) 8: Else 单位与地名之间无标记符，可以利用定义好的数组进行处理，如系、学院、所等 9: For m = 1 To Ubound(sIdentify) 10: If InStr(1, sTemp, sIdentify(m)) 0 Then 11: sAffiliation = Left(sTemp, InStr(1, sTemp, sIdentify(m)) + Len(sIdentify(m)) - 1) 12: sCity = Mid(sTemp, Len(sAffiliation) + 1) 13: Exit For 14: End If 15: Next 16: End If 邮编处理完以后判断机构与城市间是否存在标记符，如果存在标记符，分别提取就可以；如果不存在标记符，可以用后缀截取法进行分割，因为机构名有规律可寻，大都以学院、系、所、中心、室、公司、馆等结尾，可以用特征枚举的方式构造数组，如程序中的sIdentify。但这种处理方式是没法保证结果的准确性，最好的方式还是获取官方数据，包括机构和城市列表。在具体处理中还可以利用其它信息(如作者和邮编)对不规范的机构数据进行自动修正，例如，利用规范的同一作者同一邮编的机构来修正不规范的机构(排除改名因素)。期刊可以分为刊名、年、期、卷、起止页码等信息，如情报学报-2005.24(3).-363-370。刊名后以短横线接年，年后以句点接卷，卷号用圆括号把期号括起来，卷期后加句点是起止页码，起始页码和终止页码前都有短横线。而像清华同方的数据就不需要这项分隔了。 1: For i = 1 To iRecCount 2: sTemp = Worksheets(sSrce).Cells(i, iCol) 3: Worksheets(sDest).Cells(i, 1) = Mid(sTemp, 1, InStr(1, sTemp, -) - 1) 4: Worksheets(sDest).Cells(i, 2) = Mid(sTemp, InStr(1, sTemp, -) + 1, 4) 5: Next 6 总结经过上述处理，就可以进行统计了。文献计量统计分析的流程包括数据获取、数据预处理、统计计算与应用四大模块。数据预处理也是关键一环，数据预处理的精确程度直接决定着统计计算的质量，从而决定着统计分析的结果。数据过滤与筛选，主要是把符合某种条件或不符合某种条件的数据滤掉。过滤是根据条件滤掉记录，拆分是根据字符串内的标记符分成同构的字段，而提取则是根据字符串内的标记符分成不同的字段。数据的预处理流程比较简单，技术实现也比较简单，无非就是行列转换、数据过滤、拆分与提取等几个步骤，所有的步骤只用了for循环、条件判断与常用字符串处理函数。实验中，对关键的处理都采取了几种不同的算法，并从执行速度、程序复杂度等方面对算法进行了比较，总结如下：涉及反复操作一定要读到内存，减少IO读写；循环内的处理过程越简单越好，能放在循环外的尽量往外放；数据处理的粒度尽可能地大，在不影响准确度的情况下，数据处理粒度越大，效率就会越高。地名与机构等信息的内容提取有相当的难度，准确率也难以保证，但通过复杂情况的归类以及支撑资源的不断更新，然后回溯分析，可以渐渐地提高准确率，尤其是一级单位与二级单位的划分开始涉及自然语言处理的浅层次问题。在实验中用重庆维普的数据时发现作者统计结果可信度也非常低，简单记录和详细记录的作者信息差别非常大，似乎从不同的数据表里取出来一样，这个问题不是算法本身的问题，没有好的算法能解决数据遗漏的问题。在涉及自然语言处理的问题上，资源的支撑显得相当重要，回溯分析也会提高准确度。参考文献 1 陈涛．武警学院学术论文统计系统开发及功能实现．武警学院学报， 2005(3) ：94-96 2 张守胜．基于 Web 的科技论文统计信息系统的应用研究．安徽理工大学学报 ( 自然科学版 ) ， 2004(01) ： 59-63 3 袁通路．基于 ASP 的学术论文信息检索统计系统．微机发展， 2004(02) ： 57-60

个人分类: 文献计量|5626 次阅读|0 个评论

一篇"卫星激光测距"的优秀论文

jlpemail 2008-10-10 08:51

2007年冶金自动化研究设计院优秀硕士学位论文：学生姓名指导老师论文题目赵永丽房庆海卫星激光测距自动数据处理算法的研究切入卫星激光测距这个主题的角度可以有多种。这篇属于自动化的，还有光学角度的，也有大地测量与地球动力学角度的。当然，更多的是天文学角度的。

个人分类: 时空与重力场|4485 次阅读|1 个评论

帐号		自动登录	找回密码
密码			注册

关闭安全验证

标签: 算法

相关帖子

相关日志

关闭 安全验证

标签: 算法

相关帖子

相关日志

关闭安全验证