共计 7 篇文章

启发式搜索

最近为了解决一个问题,粗略的学习了一些搜索算法,我真正动手实现的只有里面的2种,忽然感觉饶了一大圈又跑到机器学习的领域上去了。。。 写在前面 为了解决一个关于查找最短路径的问题,我查找了很多资料,学习到了一些新的算法。这篇文章我打算叙述两个部分,一个关于局部最优问题,一个关于启发式搜索问题。 问题的引入 这个问题来源于某公司的一个挑战赛中,是一个NP-hard问题,类似于旅行商问题和邮递员问题。其主要解决的问题就是在指定拓扑图G(V, E)中,找到一条尽量最优的路径,且这条路径不存在回路,且经过指定顶点集。 最短路径问题 想到最短路径问题,立马想到了Dijkstra算法了。。。这是一个非常高效的算法, ...

图的常用算法

纸上得来终觉浅,绝知此事要躬行。打算把图的常用算法梳理一遍,加深一下记忆和理解。 简介 前面写了一遍关于图的存储结构和遍历算法的文章,这一篇打算回顾一下图的一些常用算法,包括最小生成树、最短路径算法。这些算法很基础,在生活中经常用到,打算自己动手实现一下,加深理解~~ 最小生成树 生成树的概念:r若图是连通的无向图或强连通的有向图,则从任何一个顶点出发调用一次BFS或者DFS便可访问图中所有的顶点,这种情况下,图中所有顶点加上遍历过程中经历的边构成的子图成为原图的生成树。对于不连通和不是强连通的有向图,这样得到的是生成森林。 最小生成树:对于加权图,权值最小的生成树成为最小生成树。可以用kruskal(克鲁斯卡尔) ...

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

快要面临实习了,最近打算专攻一些算法,这篇主要回顾一下图的基本算法,以及基本的的数据结构。 简介 本文主要回顾本科所学的关于图的一些数据结构和基本算法,图在实际问题中应用很广泛,是一种非常重要的数据结构。第一部分叙述图的定义以及基本表示形式,第二部分叙述关于图的一些常用算法。 图的描述 图的定义 图是顶点的非空集合和顶点之间边的非空集合组成的,常用G(V,E)表示,其中G表示一个图,V代表图G中顶点的集合,E表示图中边的集合。 图主要分为两类:一种是有向图,一种是无向图。其中有向图是顶点到顶点之间的边是有方向的,而无向图说明顶点间的边是不区分方向的。还有一种特殊的图称为网: ...

Red Black Tree

本文参考算法导论书籍以及一些博客,实现了红黑树的插入删除算法。 简介 红黑树这个算法,以后可能会再次遇到,我就在此记录一下。这个算法使用的C语言实现的。 红黑树的原理讲解 我是通过参考枫叶博主关于对红黑树讲解,以及算法导论这本书大致了解了红黑树的实现细节。具体参见红黑树删除操作。 红黑树的C实现 1 #include // 因为markdown过滤性质加了一个'\',include应直接包含stdio.h 2 #include 3 4 typedef enum Color 5 ...

平衡二叉树

本文简要的实现了平衡二叉树的插入、删除操作。为了更新节点的平衡度,新增了parent指针。 简介 这个平衡二叉树使用C语言实现的,因为写的匆忙,加上智商捉急,可能某些地方没有考虑周全,会有一点小bug,尚在排查中。本算法能基本的实现平衡二叉树的插入、删除操作,有关平衡二叉树的原理及实现,参考AVL树(一)之 图文解析 和 C语言的实现。这位博主讲解的非常详细!!虽然他给的代码中有一些错误,但从他的博文中,我受益良多,并且重写了这个AVL树,在此表示感谢 ...

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

本文主要收集了一些很nice的方法,用来计算一个数,其二进制形式中1的位数。 简介 李明老师的C语言中级课程中,讲解了这一算法,无奈记性不好。。为了以后能时常看到,现记录下来。 简单相与法 比如一个二进制数0b 1111 1111 = 0xFF,只需要: 1、与0b 0000 0001 = 0x01相与,如果为真,则个数加1; 2、与0b 0000 0010 ...