yuanyirui-CSDN博客

原创 libsvm代码与理论

如果你对模式分类有兴趣，并且对svm有一定的理解，此文和接下来的博文或许对你有帮助。首先libsvm的代码可以在http://www.csie.ntu.edu.tw/~cjlin/libsvm/下载，我在这里介绍的是libsvm的classification部分。这个部分的training部分涉及两个核心过程，选两个alpha和更新这两个algha。上海交通大学的《libsvm2.6程序

2009-11-18 21:15:00 2943

原创 SVM中的Karush-Kuhn-Tucker条件和对偶问题

因为这里公式编辑不方便，为求严谨，写在word上截图，图片边缘缺失的字，下面补上。需要满足的条件。线性组合。两个拉格朗日乘子不同的地方在于条件也是KKT条件之一。可以直接套用二次规划。如果反过来，如何将对偶式对偶回原来的目标式？

2009-10-24 00:17:00 3500 4

原创 c++类成员函数

c++的两大特色是多态和模板。其中多态是通过继承和虚函数来实现的，其中虚函数是通过每个对象里面的虚表来实现的。如果这个对象的类有虚函数，那么这个类就有一张虚表，存的是每个虚函数的入口地址，而这个类的每个对象，都会有一个4字节的指针，指向这张虚表，这个就是虚指针。上面一段话很多人都知道，但是如果问普通成员函数，编译器是怎么找到它的入口地址的呢？也就是说，怎么进行调用？为什么A类一个foo函数和B

2009-09-25 17:04:00 11358 3

原创 STL线程不安全的读写处理

采用队列处理消息大概是很多核心代码都会选择的方式，时间是天然的优先级，采用优先队列也无妨，主要是要采用临界区，这样的代码效率可能低一点，但是比起不用要健壮一些。#include #include #include using namespace std;list a; // 队列CRITICAL_SECTION cs; // 临界区#define WRITE

2009-09-22 23:20:00 1384 1

经过了一个月的有间断的研究和开发，我的泡泡堂从只有漏洞百出的AI版，到可以编辑地图的1.1版，最后到修正和提升了AI和改善了泡泡堂显示界面，并且加入泡泡堂录制和播放功能的泡泡堂1.2版终于面世了。也许大家对AI不大感兴趣，对游戏的录制和播放比较感兴趣，（或者对两者都不感兴趣:)）。那我就简要说说AI，详细说说录制和播放吧。首先要说明一点的是，这个游戏最开始的框架不是我做起来的，因为我接触游戏开发也

2009-08-27 17:50:00 4487 16

转载终于找到可以在win32 sdk下打开文件选择对话框的方法。

// 打开文件打开对话框，如果选中文件，则NewGameOPENFILENAME ofn; // 公共对话框结构。TCHAR szFile[MAX_PATH]; // 保存获取文件名称的缓冲区。 // 初始化选择文件对话框。ZeroMemory(&ofn, sizeof(ofn));ofn.lStructSize = sizeof(ofn);

2009-08-10 19:03:00 8254 4

原创 2*1格子问题

废话少说，代码说话#include static double cnt[12][1<<11];static int trans[16384][2];int rows, cols, ntrans;/* there are ((sqrt(2)+1)^c - (sqrt(2)-1)^c) * (sqrt(2)+2) / 4 transitions * which is t

2009-05-29 16:51:00 680

原创几道数论题

第二类Stirling数n个有类别的球放到m个相同的盒子中，要求不能有空盒，有多少种放法？这道题就是第二类Stirling数的经典例子，表示为S(n,m)。它有递推关系S(n,m)=m*S(n-1,m)+S(n-1,m-1) 其中n,m>=1当盒子数大于球数的时候即m>n有S(n,m)=0 盒子和球的问题这个问题在高中的排列组合中就经常碰到，下面就列

2009-02-17 22:55:00 1378 1

原创排列与字典序值的转换

给定{1，2，3，……，n}的排列为π，其字典序值为rank(π，n)。并且有这样的关系：rank(π，n) = (π[1] - 1)(n - 1)! + rank(π’，n-1)其中，π’中每个元素π’[i] = π[i + 1] – 1 若π[i + 1] > π[1]π’[i] = π[i + 1] 若π[i + 1] π[1]例如序列213除去序列第一个元素

2009-02-15 18:26:00 989

转载马的Hamilton周游问题，O(N)解决，N表棋盘规模

马的周游这个问题是搜索的经典问题，但是搜索的时间效率极低，并随着棋盘的扩大呈指数级增长，最终导致问题几万年不可解。如果题目放宽要求：1、只需要求出周游的一条路线2、棋盘的长和宽|L-W|有这两个条件就能使得问题复杂度简化，最终能在棋盘规模的复杂度下解决。定义n*n的棋盘的每一个点为图G的顶点V，n*n的棋盘的每一个点和从这个起点一步可达的点的连线为图G的边E。这样图G有n*

2009-02-15 14:43:00 4815 2

原创循环赛日程表的多边形解法

循环赛要求比赛的每两个选手都要进行一次比赛，而且每个选手每天都要比赛一场。这种题目的解法通常是用分治的思想来做，并且是分治方法解题的经典题目。下面的一种受多边形启发的方法，也能巧妙解决循环赛日程表问题。如图所示，有八个选手要进行循环赛，画七边形，每个点表示一个选手。其中最高点所代表的选手与第八位选手进行比赛，在同一水平线上的选手进行比赛。每天的比赛由旋转一次的多边形决定。这样就刚好能安排符

2009-02-15 00:37:00 2124

转载构造格雷码

学过数字电路的应该都认识格雷码，它由n位01字符串表示，相邻两个格雷码只有一位01不同。长度（位）（0，1）串N=101 N=20001 1110 N

2009-02-14 20:27:00 1732

原创 X数组和Y数组的中位数

给定的X数组和Y数组都是n个元素的有序数组，设计一个O(logn)时间的算法，找出X和Y的2n个数的中位数。（第n小的数）这个题一看就要用二分的思想来做，下面的代码套用二分的思路，大家一定不陌生。bool GetValue(int *X,int *Y,int n,int& value){ int low = 0 , high = n - 1 , mid; while(

2009-02-14 17:55:00 1940 2

原创最接近中位数的k个数

给定n个互不相同的数组成集合S，以及正整数k，设计一个O(n)时间算法找出S中最接近S的中位数的k个数。首先假定读者知道找一个无序数列中的第k小的数的select算法，这个算法的时间复杂度是O(n)的。如果给出的n是奇数，则中位数是第n/2个；如果是偶数，则中位数是第n/2和n/2 + 1个的中位数。(也可以无论n是奇是偶，都取n/2)第一步，通过select算法得到这个中位数；

2009-02-14 16:37:00 2632

原创最大值和次大值问题的最优算法

输入n个数，最坏情况下用 n + logn - 2 次比较找出当中的最大值和次大值。解题思想：根据题意出现logn，则肯定用到二分或者堆的思路，但是输入的数没有经过排序，而且题目要求的计算量也不允许排序。这样，就肯定会用到类似堆的思路，但是直接构造堆等同于排序。堆的思想跟竞标赛类似，都是父节点>=（）子节点。如果父节点都是从子节点而来，这样就是竞标赛；如果不是，这样就是堆。既然不能排序又不能构

2009-02-14 16:20:00 4066

原创对Hanoi塔问题的理解

汉诺塔的递归算法如下(递归的原理和汉诺为什么可以用递归就不详说了)： void hanoi(int n,int A,int B,int C){ if(n>0){ hanoi(n-1,A,C,B); move(n,A,B); hanoi(n-1,C,B,A); }} 可以看出它跟树的中序遍历没有多大区别，在搜索的过程中，只是按照中序遍历的方式把节点输

2009-02-13 14:16:00 732

转载顶起帖

看了楼主的帖子,不由得精神为之一振,自觉七经八脉为之一畅,七窍倒也开了六巧半,自古英雄出少年,楼主年纪轻轻,就有经天纬地之才,定国安邦之智,古人云,卧龙凤雏得一而按天下,而今,天佑我大中华,沧海桑田5000年,中华神州平地一声雷,飞沙走石,大舞迷天,朦胧中,就见顶天立地一金甲天神立于天地间,这大英雄手持双斧,二目如电,一斧下去,混沌初开,二斧下去,女娲造人,三斧下去,小生倾倒.得此大英雄,实耐

2009-02-13 13:08:00 460

转载最大间隙问题

给定n个实数x1,x2,x3...xn，求这n个数在实数轴上相邻2个数之间的最大差值，设计最大间隙问题的线性时间算法。利用抽屉原理（或称为鸽舍原理--即有4个苹果放进5个抽屉里面，肯定至少有一个抽屉没有苹果），算法如下：double maxgap(int n,double x[]){ double minx=x[mini(n,x)] , maxx = x[maxi(n,x)]; int

2009-02-13 13:04:00 1213

转载关于3n+1问题的计算效率

while(n>1){ if(n%2 == 1) n=3*n+1; else n=n/2;}该算法的下界是 logn ，算法的计算上界至今未知。算法能否在有限时间结束还是一个问题，有人测试过10^13内的自然数都能在有限步结束。人们猜测，对所有自然数，上述算法均能在有限步结束，但无法给出理论证明，因此无法分析计算时间上界。这个猜想也称为Collatz猜想。

2009-02-13 13:00:00 2811 4

libsvm理论与代码理解

这个是我看了几天之后，对libsvm的理论和代码的理解，如有疏漏纰误，望不吝赐教。由于理论和代码部分联系起来比较繁杂，希望连续几篇的个人见解能对有志研究libsvm的研究员能有一定的作用。此乃引用之文献。 libsvm：http://www.csie.ntu.edu.tw/~cjlin/libsvm/ smo: 《Fast Training of Support Vector Machines using Sequential Minimal Optimization》John C. Platt 《Improvements to Platt's SMO Algorithm for SVM Classifier Design》S.S. Keerthi 《libsvm-2.6 程序代码注释》上海交大模式分析与机器智能实验室

2009-11-17

空空如也

TA创建的收藏夹 TA关注的收藏夹

TA关注的人

yuanyirui的专栏