六个经典算法研究：A*.Dijkstra.动态规划.红黑树等算法[不断更新]

v_JULY_v
博客专家认证
2011-01-10 05:23:35
加精
本人这个经典算法研究系列，目前暂时只写了6篇，正在不断更新中。
已经写或编写的六个算法，如下（有问题，望不吝指出）：

经典算法研究系列：一、A*搜索算法
http://blog.csdn.net/v_JULY_v/archive/2010/12/23/6093380.aspx
1.A* 搜寻算法

1968年，的一篇论文，“P. E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths in graphs. IEEE Trans. Syst. Sci. and Cybernetics, SSC-4(2):100-107, 1968”。从此，一种精巧、高效的算法------A*算法横空出世了，并在相关领域得到了广泛的应用。
...................

经典算法研究系列：二、Dijkstra 算法
http://blog.csdn.net/v_JULY_v/archive/2010/12/24/6096981.aspx
Dijkstra 算法，又叫迪科斯彻算法（Dijkstra），
是由荷兰计算机科学家艾兹格·迪科斯彻（Edsger Wybe Dijkstra）发明的。
算法解决的是有向图中单个源点到其他顶点的最短路径问题。

举例来说，如果图中的顶点表示城市，而边上的权重表示著城市间开车行经的距离，
迪科斯彻算法可以用来找到两个城市之间的最短路径。
.....................


经典算法研究系列：三、动态规划算法解微软一道面试题[第56题]
http://blog.csdn.net/v_JULY_v/archive/2010/12/31/6110269.aspx
ok，咱们先来了解下什么是动态规划算法。
动态规划一般也只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解
(对有些问题这个要求并不能完全满足，故有时需要引入一定的近似)。
简单地说，问题能够分解成子问题来解决。
...............



经典算法研究系列：四、教你通透彻底理解：BFS和DFS优先搜索算法
http://blog.csdn.net/v_JULY_v/archive/2011/01/01/6111353.aspx
本人参考：算法导论
本人声明：个人原创，转载请注明出处。

ok，开始。
翻遍网上，关于此类BFS和DFS算法的文章，很多。但，都说不出个所以然来。
读完此文，我想，
你对图的广度优先搜索和深度优先搜索定会有个通通透透，彻彻底底的认识。
.........



经典算法研究系列：五、红黑树算法的实现与剖析
http://blog.csdn.net/v_JULY_v/archive/2010/12/31/6109153.aspx
昨天下午画红黑树画了好几个钟头，总共10页纸。
特此，再深入剖析红黑树的算法实现，教你如何彻底实现红黑树算法。

经过我上一篇博文，“教你透彻了解红黑树”后，相信大家对红黑树已经有了一定的了解。
个人觉得，这个红黑树，还是比较容易懂的。
不论是插入、还是删除，不论是左旋还是右旋，最终的目的只有一个：
即保持红黑树的5个性质，不得违背。
.........


经典算法研究系列：六、教你从头到尾彻底理解KMP算法
http://blog.csdn.net/v_JULY_v/archive/2011/01/01/6111565.aspx
-----------------------
本文参考：数据结构（c语言版） 李云清等编著、算法导论
作者声明：个人July 对此24个经典算法系列，享有版权，转载请注明出处。

引言：
在文本编辑中，我们经常要在一段文本中某个特定的位置找出 某个特定的字符或模式。
由此，便产生了字符串的匹配问题。
本文由简单的字符串匹配算法开始，经Rabin-Karp算法，最后到KMP算法，教你从头到尾彻底理解KMP算法。
.............


=============================
第一个和第二个算法，写的不怎么好，望各位见谅。
其余文章，写的不够好之处，请不吝批评指正。谢谢。

更多详情，请参考以上我博客里的博文。
My Blog：
http://blog.csdn.net/v_JULY_v
(欢迎，博客里留言评论，批评指正。)

-----------------------
作者声明:
本人July对本博客所有任何内容和资料享有版权，转载请注明作者本人July及出处。
永远，向您的厚道致敬。谢谢。July、二零一一年一月十日。
...全文
9219 230 打赏 收藏 转发到动态 举报
写回复
用AI写文章
230 条回复
切换为时间正序
请发表友善的回复…
发表回复
Aoner_1 2011-04-26
  • 打赏
  • 举报
 回复
感谢楼住的分享精神!
v_JULY_v 2011-04-21
  • 打赏
  • 举报
 回复 
#include <iostream.h>



void reset(int* ip)

{

	*ip=0;

	ip=0;

}



int main()

{

	int i=42;

	int* p=&i;

	cout<<"i:"<<*p<<endl;

	cout<<p<<endl;



	reset(p);

	cout<<"i:"<<*p<<endl;

	cout<<p<<endl;

	return 0;

}


i:42

0x0012FF7C

i:0

0x0012FF7C

Press any key to continue
v_JULY_v 2011-02-22
  • 打赏
  • 举报
 回复
十、从头到尾彻底理解傅里叶变换算法、中
http://blog.csdn.net/v_JULY_v/archive/2011/02/22/6200945.aspx
opmic 2011-02-22
  • 打赏
  • 举报
 回复
把贴顶到前面，容易看到
v_JULY_v 2011-02-21
  • 打赏
  • 举报
 回复
http://www.dspguide.com/pdfbook.htm
v_JULY_v 2011-02-21
  • 打赏
  • 举报
 回复
十、从头到尾彻底理解傅里叶变换算法、上
http://blog.csdn.net/v_JULY_v/archive/2011/02/20/6196862.aspx
修石 2011-02-20
  • 打赏
  • 举报
 回复
收藏 很不错的东西
v_JULY_v 2011-02-20
  • 打赏
  • 举报
 回复
http://blog.csdn.net/dznlong
longwin798 2011-02-20
  • 打赏
  • 举报
 回复
顶楼主。。
我们老师都没讲这些。。
v_JULY_v 2011-02-17
  • 打赏
  • 举报
 回复
经典算法研究系列：九、图像特征提取与匹配之SIFT算法
http://blog.csdn.net/v_JULY_v/archive/2011/02/15/6186942.aspx
Oo纳兰筱DoO 2011-02-16
  • 打赏
  • 举报
 回复
算法比较难，只能观望
yayang17 2011-02-14
  • 打赏
  • 举报
 回复
这里是学生问作业区，我看明白了，所以就此告别csdn。
v_JULY_v 2011-02-14
  • 打赏
  • 举报
 回复
http://blog.csdn.net/v_JULY_v/archive/2011/01/01/6111353.aspx

经典算法研究系列：一、A*搜索算法
http://blog.csdn.net/v_JULY_v/archive/2010/12/23/6093380.aspx

I、经典算法研究系列：二、Dijkstra 算法初探
http://blog.csdn.net/v_JULY_v/archive/2010/12/24/6096981.aspx

II、经典算法研究系列：二之续、彻底理解Dijkstra算法
http://blog.csdn.net/v_JULY_v/archive/2011/02/13/6182419.aspx

几个最短路径算法比较：
http://blog.csdn.net/v_JULY_v/archive/2011/02/12/6181485.aspx

yyfhz 2011-02-11
  • 打赏
  • 举报
 回复
好东西,不顶不行啊!
v_JULY_v 2011-02-11
  • 打赏
  • 举报
 回复
[Quote=引用 208 楼 wo_long 的回复:]
Dijkstra属于DP
[/Quote]

准确的说，属于贪心算法问题。
v_JULY_v 2011-02-11
  • 打赏
  • 举报
 回复
经典算法研究系列：八、再谈启发式搜索算法
http://blog.csdn.net/v_JULY_v/archive/2011/02/10/6177380.aspx

wo_long 2011-02-07
  • 打赏
  • 举报
 回复
Dijkstra属于DP
加载更多回复（104）
十五个经典算法研究与总结、目录+索引.zip
本经典算法研究系列，涵盖 A*.Dijkstra.DP.BFS/DFS.红黑树.KMP.遗传.启发式搜索.图像 特征提取 SIFT.傅立叶变换.Hash.快速排序.SPFA.快递选择 SELECT 等 15 个经典基础算法， 共计 31 篇文章，包括算法理论的研究与阐述，及其编程的具体实现。很多个算法都后续写 了续集，如第二个算法：Dijkstra 算法，便写了 4 篇文章；sift 算法包括其编译及实现，写 了 5 篇文章；而红黑树系列，则更是最后写了 6 篇文章，成为了国内最为经典的红黑树教程。
十五个经典算法研究与总结
本经典算法研究系列，涵盖A*.Dijkstra.DP.BFS/DFS.红黑树.KMP.遗传.启发式搜索.图像 特征提取SIFT.傅立叶变换.Hash.快速排序.SPFA.快递选择SELECT等15个经典基础算法， 共计31篇文章，包括算法理论的研究与阐述，及其编程的具体实现。很多个算法都后续写 了续集，如第二个算法：Dijkstra 算法，便写了4篇文章；sift算法包括其编译及实现，写 了5篇文章；而红黑树系列，则更是最后写了6篇文章，成为了国内最为经典的红黑树教程。
区块链核心：共识算法
​什么是共识算法背景分布式系统集群设计中面临着一个不可回避的问题，一致性问题对于系统中的多个服务节点，给定一系列操作，如何试图使全局对局部处理结果达成某种程度的一致？这个一致性问题大致有如下的场景：节点之间通讯不可靠的，延迟和阻塞节点的处理可能是错误的，甚至节点自身随时可能宕机节点作恶举例说明，就比如有两家电影院同时售卖总量一定的电影票，在这样的场景下，要如何设计方式来保证两家电影院协调同步不出现超卖或者错卖的问题呢？共识算法，就是解决对某一提案（目标，投票等各种协作工作），大家达成一致意见的过程比如上述的买票问题，就可以有如下的设计：1.每次卖票打电话给其他电影院，确认当前票数2.协商售卖时间，比如一三五A卖，二四六B卖3.成立个第三方存票机构，它统一发票通过以上的设计，可以看出一个很重要的解决一致性算法的解决思路，即：将可能引发不一致的并行操作进行串行化，就是现在计算机系统里处理分布式一致性问题基础思路和唯一秘诀 著名的共识设计理论FLP 不可能性原理  共识算法的理论下限提出该定理的论文是由 Fischer, Lynch 和 Patterson 三位作者于 1985 年发表，该论文后来获得了 Dijkstra（就是发明最短路径算法的那位）奖。FLP 原理认为对于允许节点失效情况下，纯粹异步系统无法确保一致性在有限时间内完成。三人三房间投票例子三个人在不同房间，进行投票（投票结果是 0 或者 1）。三个人彼此可以通过电话进行沟通，但经常会有人时不时地睡着。比如某个时候，A 投票 0，B 投票 1，C 收到了两人的投票，然后 C 睡着了。A 和 B 则永远无法在有限时间内获知最终的结果。如果可以重新投票，则类似情形每次在取得结果前发生带入到计算机领域就是说，即便在网络通信可靠情况下，一个可扩展的分布式系统的共识问题的下限是无解。即可靠性的下限是0%CAP  分布式系统领域的重要原理CAP 原理最早由 Eric Brewer 在 2000 年，ACM 组织的一个研讨会上提出猜想，后来 Lynch 等人进行了证明• C（一致性）：所有的节点上的数据时刻保持同步，即数据一致• A（可用性）：每个请求都能在一定时间内接受到一个响应，即低延迟• P（分区容错）：当系统发生分区时仍然可以运行的定理：任何分布式系统只可同时满足二点，没法三者兼顾。即数据一致，响应及时，可分区执行不可能同时满足。举个例子：一个分布式网路上，某一个节点有一组依赖数据A，当网络无延迟，无阻塞时，依赖于X的操作可正常进行。但网络无延迟阻塞在现实世界中是没法100%保证的，那么当网络异常时，必然会产生分布式系统的分区和孤岛，那当一个执行操作在A分区之外时，如果要保证P,即当系统发生分区时仍可运行，就需要在分布式系统中多个节点有X的备份数据，以应对分区情况。则这时候就需要在C,A之间做出选择。假如选择C，即要保证数据在分布式网络中的一致性，那么就需要在X每次改动时，需要将全网节点的X数据同步刷新成最新的状态，那么在等待数据刷新完成之前，分布式系统是不可响应X的依赖操作的，即A的功能缺失假如选择A，即要突出低延迟的实时响应。那么在响应的时候，可能全节点的X数据并没有同步到最新的状态，则会导致C的缺失。上面看上去有些绕，那么你只要记住这句话，CAP原理在分布式网络系统的应用讨论，其实就是讨论在允许网络发生故障的系统中，该选择一致性还是可靠性？如果系统重视一致性，那么可以基于ACID原则做系统设计即 Atomicity（原子性）、Consistency（一致性）、Isolation（隔离性）、Durability（持久性）。ACID 原则描述了对分布式数据库的一致性需求，同时付出了可用性的代价。• Atomicity：每次操作是原子的，要么成功，要么不执行；• Consistency：数据库的状态是一致的，无中间状态；• Isolation：各种操作彼此互相不影响；• Durability：状态的改变是持久的，不会失效相应的有一个BASE原则，（Basic Availiability，Soft state，Eventually Consistency）则强调了可用性。 经典的共识算法设计业内，针对节点异常的情况，会有两种分类1.故障的，不响应的节点，成为非拜占庭错误2.恶意响应的节点，称为非拜占庭错误Paxos 最早的共识算法  非拜占庭算法的代表Paxos有三种角色：• proposer：提出一个提案，等待大家批准为结案。客户端担任该角色；• acceptor：负责对提案进行投票。往往是服务端担任该角色；• learner：被告知结案结果，并与之统一，不参与投票过程。即普通节点系统运行由proposer驱动，当合法提案在一定时间内收到1/2以上投票后达成共识。因此，可得出无法达成共识的条件：1.proposer故障2.二分之一以上acceptor故障拜占庭问题与BFT(Byzantine Fault Tolerant) 算法Leslie Lamport 1982 年提出用来解释一致性问题的一个虚构模型。拜占庭是古代东罗马帝国的首都，由于地域宽广，守卫边境的多个将军（系统中的多个节点）需要通过信使来传递消息，达成某些一致的决定。但由于将军中可能存在叛徒（系统中节点出错），这些叛徒将努力向不同的将军发送不同的消息，试图会干扰一致性的达成。拜占庭问题即为在此情况下，如何让忠诚的将军们能达成行动的一致。对于拜占庭问题来说，假如将军总数为 N，叛变将军数为 F，则当N>=3F+1 时，问题才有解，即叛变的将军不超过1/3时，存在有效的算法，如BFT，不论叛变者如何折腾，忠诚的将军们总能达成一致的结果。这是一个数学论证的结论，有兴趣的同学可以自行推导。PBFT  一种高效拜占庭容错共识算法PBFT是Practical Byzantine Fault Tolerance的缩写，意为实用拜占庭容错算法。该算法是Miguel Castro 和Barbara Liskov（2008年图灵奖得主）在1999年提出来的，解决了原始拜占庭容错算法效率不高的问题。他的核心思想是：对于每一个收到命令的将军，都要去询问其他人，他们收到的命令是什么。如上图，假设命令由A将军分发，假如A是作恶异常，分发给B,C,D的操作分别是1,2,3.意图扰乱共识。拜占庭容错算法上设计实现是，当B,C,D收到命令后，相互之间也会沟通从A收到的命令是否一致，从而达到识破干扰的目的。其容错的极限值就是N>=3F+1。PBFT 在区块链上的实现区块链的节点分为记账节点和普通节点两个角色记账节点负责向全网提供记账服务，并维护全局账本，每过一段时间从记账节点中选一个议长，进行命令的分发，其他记账节点则作为议员进行验证将军就是记账节点，拥有全局账本，并验证交易的有效性，过互相传达验证结果，在f共识的一般流程如下：1.任一节点接收到发送者签名的交易数据请求后，向全网广播2.所有记账节点均独立监听全网的交易数据，并记录在内存3.议长在经过t后发送共识请求提案request4.议员在收到提案后，进行相关验证，发送响应response5.任意节点在限定时间内收到至少F+1个response后，共识达成，把交易记录入区块并发布给全网，如果超时，则更换视图和议长6.任意节点在收到完整区块后，把包含的交易从内存中删除开始下一个共识循环区块产生间隔t,    记账节点n,  可容错节点数f， 视图编号v,  区块高度h, 议长编号p,  议员编号i p=(h-v)%n  未来的发展POW算法建立了比特币帝国，具有划时代的意义。但其能耗和速度问题却是制约区块链普及的两大难以解决的问题。目前POS算法是一大趋势，以太坊的Casper，EOS的DPos等都是借鉴了上述前人的设计理念做的基于应用场景的优化改造，但万变不离其宗，我和大家一样，需要不断的学习和思考，没准，能有发明出自己的共识算法的一天呢。 
软件开发中的十五个经典算法研究
本经典算法研究系列，涵盖 A*.Dijkstra.DP.BFS/DFS.红黑树.KMP.遗传.启发式搜索.图像特征提取SIFT.傅立叶变换.Hash.快速排序.SPFA.快递选择 SELECT 等15 个经典基础算法，共计 31 篇文章，包括算法理论的研究与阐述，及其编程的具体实现。很多个算法都后续写了续集，如第二个算法：Dijkstra 算法，便写了 4 篇文章；sift 算法包括其编译及实现，写了5篇文章；而红黑树系列，则更是最后写了6篇文章，成为了国内最为经典的红黑树教程。
十五个经典算法研究与总结、目录+索引（by_....pdf
十五个算法包括：A*算法、Dijkstra 算法、动态规划算法、BFS 和 DFS 优先搜索算法、KMP 算法、遗传算法、sift 算法、SIFT 算法、红黑树、快速排序算法、Hash 表算法等等。
数据结构与算法

33,010

社区成员

35,328

社区内容

发帖
与我相关
我的任务
社区描述
数据结构与算法相关内容讨论专区
社区管理员
  • 数据结构与算法社区
加入社区
  • 近7日
  • 近30日
  • 至今

加载中

查看更多榜单
社区公告
暂无公告

试试用AI创作助手写篇文章吧

+ 用AI写文章