Brains


Algorithm、Machine Learning、Search、cloud computing
on Algorithm, 启发式搜索

启发式搜索

最近为了解决一个问题,粗略的学习了一些搜索算法,我真正动手实现的只有里面的2种,忽然感觉饶了一大圈又跑到机器学习的领域上去了。。。 写在前面 为了解决一个关于查找最短路径的问题,我查找了很多资料,学习到了一些新的算法。这篇文章我打算叙述两个部分,一个关于局部最优问题,一个关于启发式搜索问题。 问题的引入 这个问题来源于某公司的一个挑战赛中,是一个NP-hard问题,类似于旅行商问题和邮递员问题。其主要解决的问题就是在指定拓扑图G(V, E)中,找到一条尽量最优的路径,且这条路径不存在回路,且经过指定顶点集。 最短路径问题 想到最短路径问题,立马想到了Dijkstra算法了。。。这是一个非常高效的算法,它是基于贪心的算法思想。但上述题目并不具有贪心选择性质,会陷入局部最优。好的的情况下,会生成一条不是最优的路径;但差的情况下,甚至找不到一条有效路径。。 局部最优的情况 我第一次接触局部最优问题是在机器学习中的,比如逻辑回归在训练的过程中,采用梯度下降法对一些参数的优化的时候,会产生一些局部最优解。这是因为它的损失函数不是凸函数的缘故,因为这个函数有多个极值嘛。 在这个问题中,直接使用Dijkstra算法也会陷入局部最优的情况,如何跳出这个局部最优呢?比较典型的算法,哦不对应该是算法思想吧,模拟退火。这一题我之前就是用这个算法求解的,但效果不太理想。模拟退火算法属于一种启发式的搜素算法。 启发式的搜索
Read More
on Algorithm, 图的基础算法

图的常用算法

纸上得来终觉浅,绝知此事要躬行。打算把图的常用算法梳理一遍,加深一下记忆和理解。 简介 前面写了一遍关于图的存储结构和遍历算法的文章,这一篇打算回顾一下图的一些常用算法,包括最小生成树、最短路径算法。这些算法很基础,在生活中经常用到,打算自己动手实现一下,加深理解~~ 最小生成树 生成树的概念:r若图是连通的无向图或强连通的有向图,则从任何一个顶点出发调用一次BFS或者DFS便可访问图中所有的顶点,这种情况下,图中所有顶点加上遍历过程中经历的边构成的子图成为原图的生成树。对于不连通和不是强连通的有向图,这样得到的是生成森林。 最小生成树:对于加权图,权值最小的生成树成为最小生成树。可以用kruskal(克鲁斯卡尔)算法或prim(普里姆)算法求出,这两种算法依据的思想是贪心思想。 prim(普利姆)算法 第一步:选择一个初始顶点V1,设置一个访问数组visit[]和最小距离数组distance[]。最小距离数组保存当前已访问顶点的生成树中到每个顶点最小的距离。 第二步:根据初始顶点V1,初始化visit和distance数组。 第三步:选择distance中权重最小的那个顶点,以此顶点为起始点更新distance数组,直至所有顶点都已访问。 未优化的prim算法时间复杂度为O(N^2),其C语言描述如下,: /* 输入分别为:
Read More
on Algorithm, 图的存储结构

图的基础数据结构与遍历算法

快要面临实习了,最近打算专攻一些算法,这篇主要回顾一下图的基本算法,以及基本的的数据结构。 简介 本文主要回顾本科所学的关于图的一些数据结构和基本算法,图在实际问题中应用很广泛,是一种非常重要的数据结构。第一部分叙述图的定义以及基本表示形式,第二部分叙述关于图的一些常用算法。 图的描述 图的定义 图是顶点的非空集合和顶点之间边的非空集合组成的,常用G(V,E)表示,其中G表示一个图,V代表图G中顶点的集合,E表示图中边的集合。 图主要分为两类:一种是有向图,一种是无向图。其中有向图是顶点到顶点之间的边是有方向的,而无向图说明顶点间的边是不区分方向的。还有一种特殊的图称为网:顶点间的每条边有一个权重值。 图的基本表示 邻接矩阵 邻接矩阵可以非常简单明了的描述一个图。其主要思想是用一个二维数组描述图中顶点间的关系。它也可以很方便的描述网,其中无向图的邻接矩阵是沿对角线对称的。图的邻接矩阵的C语言描述如下所示: #define MAXVEX 100 // 最大顶点数 #define MAXWEIGHT 65535 // 边的最大权重 typedef char VertextType; // 顶点表示 typedef int EdgeTypde; // 边的表示
Read More
on Algorithm, Red Black Tree

Red Black Tree

本文参考算法导论书籍以及一些博客,实现了红黑树的插入删除算法。 简介 红黑树这个算法,以后可能会再次遇到,我就在此记录一下。这个算法使用的C语言实现的。 红黑树的原理讲解 我是通过参考枫叶博主关于对红黑树讲解,以及算法导论这本书大致了解了红黑树的实现细节。具体参见红黑树删除操作。 红黑树的C实现 1 #include // 因为markdown过滤性质加了一个'\',include应直接包含stdio.h 2 #include 3 4 typedef enum Color 5 { 6 RED = 0, 7 BLACK = 1 8 }Color; 9 10 typedef struct Node 11 { 12 int value; 13 Color color; 14 struct Node * parent;
Read More
on Algorithm, AVL

平衡二叉树

本文简要的实现了平衡二叉树的插入、删除操作。为了更新节点的平衡度,新增了parent指针。 简介 这个平衡二叉树使用C语言实现的,因为写的匆忙,加上智商捉急,可能某些地方没有考虑周全,会有一点小bug,尚在排查中。本算法能基本的实现平衡二叉树的插入、删除操作,有关平衡二叉树的原理及实现,参考AVL树(一)之 图文解析 和 C语言的实现。这位博主讲解的非常详细!!虽然他给的代码中有一些错误,但从他的博文中,我受益良多,并且重写了这个AVL树,在此表示感谢 ^_^ . 数据结构 这里的parent指针很重要,它可以在平衡二叉树删除算法的调整过程中,起着很大的作用。有一点需要注明的是,那位博主的删除算法有误,选用的数据结构也不太合理。。 typedef int DataType; typedef struct Node { DataType value; int depth; // 保存节点在树中的深度,没有孩子,深度为1,负责深度为左右孩子最大深度值加1 struct Node * left;
Read More
on Algorithm, 求比特位中1的数目

计算一个数字中 1的个数 的算法

本文主要收集了一些很nice的方法,用来计算一个数,其二进制形式中1的位数。 简介 李明老师的C语言中级课程中,讲解了这一算法,无奈记性不好。。为了以后能时常看到,现记录下来。 简单相与法 比如一个二进制数0b 1111 1111 = 0xFF,只需要: 1、与0b 0000 0001 = 0x01相与,如果为真,则个数加1; 2、与0b 0000 0010 = 0x02相与,如果为真,则个数加1; .... .... n、如果这个数是16位的,必须相与到0xFFFF才能结束 核心代码如下: ... ... for( i = 0; i 1 * 2 ^ i { count++; } } ... ... 与相邻数相与法 注意这种情况:一个数与这个数减1相与,会把这个数的最后面的一位1变为0.如下情况: 0b 1000 & 0b
Read More