算法及自我感悟

人与人最小的差距在智商，最大的差距在坚持

首先，这里我表明下，我算法是自学的，也就是说，别人眼中的科班算法都玩的很溜，而我恰好不是，但是这不能代表我就会放弃算法，相反，我是一个因为兴趣去学习算法的人，我是一个享受算法的乐趣的人。

学习算法的起源--算法是循序渐进的

我最开始接触的算法是冒泡排序算法、插入排序、选择排序，实质上，这三个基础排序算法衍生出了很多优秀的算法：插入排序是一种打牌是洗牌的思路，将选择的牌依次插入到它合适的位置，虽然他是O(n^2)的算法，但是他的亲兄弟希尔排序则是一个很不错的排序算法，他是建立在插入排序上的，在原有的逐个插入变成了分段插入，先调整部分，再调整整体，看到这个思路我们又可以想到归并排序，因为它也是建立在这个思路上的，把数组一分为二，先排左边再排右边，只要保证左右两边都有序，再进行有序合并就完成了数组的排序，想想这个算法的思路，真的和分而治之算法如出一辙，从归并排序又能很快想到最优秀的快速排序,快速排序在其基础上衍生了双轴快排...等等，算法真的是循序渐进的，所有算法都是在一定的基础上衍生出的新算法，没有凭空想出的快速排序，所以我放弃了学习算法一蹴而就的想法,静下心去沉淀自我.

最开始的算法，源自我的黑白棋v0.1

我的黑白棋生涯源自大学时期自学的《C语言入门经典（第五版）》一书，因为从许多方面来说，C语言都是学习程序设计的理想起步语言。这本书是很好的入门C语言的书，这本书中讲解了很多基础语法，而且在每一章作者总会有一篇程序设计专题，而这个专题的作风就是接触问题-->分析问题-->解决问题,我每次看到这里就特别激动，因为学完一章的基础理论是很枯燥无味的，只有到最后才会上真功夫去设计自己的程序。在我学完函数再探这一章后，本章的程序设计就是--黑白棋，并且实现了初级的人机对弈。当时看到这么大一个“项目”，并且C语言是面向过程（函数）的语言，当初是完全没思路的。我就跟着作者的思路，一步步分解问题，最后硬着头皮跟着作者完全把代码“敲”出来了，当时是非常激动地，激动到那晚自己和朋友的聊天都是黑白棋对战，虽然每次机器和朋友下都是机器输，偶尔还有bug,但仍然是欢乐的，自己还会看着代码欣赏好一会.(心里留下菜鸟的泪水,对于里面优秀的思想及复杂的走棋算法我仍然没理解).因为那里的人机对战是基于穷举计算当前走棋后的棋子数的，所以就给那个版本起名为黑白棋v0.1

入门Java——升级黑白棋v0.2

在自学完C语言基础语法后，我随着同学的脚步，学习了这门优秀的面向对象语言——Java。这门语言优秀在在我们编程时竟然发现生活的一切都那么熟悉，生活的万物都抽象成——对象，在了解基础语法后，我再次尝试使用面向对象语言重写了C语言版的黑白棋，但是对于那时，我也只知道对一个简单的对象做封装，而对于里面复杂的函数我是简单理解了，最后那穷举带来的人机智商实在惨不忍睹，因为黑白棋的最基本规则——金角银边草肚皮，计算器却只会傻傻的考虑不到。我当时很自信的就百度了几篇黑白棋AI的文章，直到点进去之后才发现:What ghost!这个一分为多的结构是什么，这个alphaBeta算法怎么看半天看不懂呢?还有这个递归的操作，怎么那么让人难理解?一步步问题，驱使我去学习，那段时间做梦都在想这些事情，因为Java是学习推动的，就把这个版本的黑白棋搁置了，算是一个不完整的黑白棋v0.2吧。
(后来我才发现那么分叉的数据结构叫做树，是一种一对多的数据结构，学习树让我了解了算法是依赖数据结构的，所以数据结构是基础。而递归那个操作，我的脑回路往往想不到那么深去，我为什么需要去想呢，为什么人的思考要follow机器的执行呢?随着我去深入学习树这种数据结构，处理了越来越多的递归，我慢慢意识到，我完全不用跟着递归的调用都展开进入下一层，我只需要转变当前的角色，把初始条件转变，完全就是上一个重复的我，执行上一步该走的逻辑，只要保证逻辑没有问题，我的大脑终于有了“递”也有“归”了，后续的事务也才能慢慢推动了。学习了递归，让我从站在不同的高度去思考一个问题，看的更全面，更加不容调入细节陷阱了)

站在巨人的肩膀上——黑白棋v1.0

学习完Java后，时间又逐渐开始充裕起来，我的兴趣又回到了最初的起点——黑白棋，这次的我和以前不一样了，我知道数据结构和算法的重要性，至此，我就开始了我的算法学习之旅。从网上了解到，数据结构入门最好的书籍就是严教授的《数据结构——C语言版|第二版》，我配合这本和《算法4》一起买了下来。接下来的日子里，我每天沉浸在数据结构的海洋里（可惜那时候不知道git，基础代码都丢失了），手写翻转链表、二叉树...等等（现在已经忘完了）。知道有一天，看到了树，才有我上面一段话的描述。最后，我把这本书的习题和基础学习了80%后（兴趣告诉我，我还有我的黑白棋没有写完，所以这本书对于不感兴趣的部分就略过了），我打开了重新打开了我的黑白棋之旅。同样的，在写完基础模块封装后，我遇到了我半年前遇到的最大的敌人——alphaBeta剪枝算法，上次的直觉告诉我，这家伙不简单，于是我做了很多的准备，开始从他的前身——极大极小算法开始学习，有了数据结构学习，我很快理解了博弈树的概念，博弈树就是对每一个可选局面进行评估且搜索，且假设双方都是很聪明的，对于极大极小是相对的，在你的角度和对手的角度选择都是不一样的，你往往选择你对于你最好的局面，而对手往往会选择对于你最差的局面，所以称为极大极小算法。
理解了极大极小算法后，我又再次尝试alphaBeta剪枝算法，它是一个建立在极大极小算法思想之上的算法，它定义了一个上限β和下限α，分别用来表示当前状态一方追求的最大值中的最小值和最小值中的最大值（篇幅有限，这里不做多的描述）。这好比，你已经知道第一种方式你最多收益100块后你，你就不必要对第二种收益10块的路线继续搜索深层结构了。在第一次搜索后，往往能剪枝掉很多不必要的搜索，所以是一个优化算法。在理解了alphaBeta剪枝算法后，我再次重构了我的黑白棋，并起名为v1.0.经过半年的积淀，我已经能让我的计算器计算6步，完胜我自己（这个比起我下赢它更激动）。当晚，我果断找了朋友来测试，在几次尝试之后，朋友也完败下来，终于，在我卧薪尝胆之后初尝胜利的喜悦。（这样也奠定了我日后学习算法的乐趣和信心）

黑白棋算法的总结及展望

在那之后，因为我意识到我的黑白棋只是战胜了我自己，我是一个力争将一件事做到完美的人。于是，我又在谷歌、各大博客、github、百度等搜索自己想要的算法及优化，在alphaBeta剪枝算法的基础上，学习了MTD算法，并行搜索算法、置换表、历史表、启发搜索、遗传算法等优秀的思想，让我对自己的黑白棋再次有了更深层次的理解。
在这里，我发现alphaBeta算法和人类的做事联想起来竟然那么的一致，在你举棋不定时，想想，你自己是真正的做了最大的努力吗(尝试在最短时间内搜索最多的结构)?如果是，在当前的基础上，你能接受对手给你的最差结果(极大极小算法，对手往往给你选择最不利的路)吗?那么就毫不犹豫的去决定吧！这句话总结到一起就是：尽最大的努力，做最坏的打算.现在想想，算法真的教会了我如何去做事，去做人。

算法启发

排序算法

你不可能要所有的东西，所以你只能要你最重要的东西，你要知道什么东西最重要，你就需要对你心内的那些欲望和抱负有清楚的认识，不然，你就会在纠结中度过。
排序算法的核心思想就是，让你帮助你认清自己最需要的是什么，认清自己最想要的是什么，然后根据这个去做选择

贪婪算法

所谓贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择（注意：是当前状态下），从而希望导致结果是最好或最优的算法。
这样的例子有很多。对于选择中，大多数人都会选用贪婪算法，因为这是一个比较简单的算法，未来太复杂了，只能走一步看一步，在当前的状况下做出最利于自己的判断和选择即可。
有的人会贪婪薪水，有的人会贪婪做的项目，有的人会贪婪业务，有的人会贪婪职位，有的人会贪婪自己的兴趣……这些都没什么问题。贪婪算法并没有错，虽然不是全局最优解，但其可以让你找到局部最优解或是次优解。其实，有次优解也不错了。
贪婪算法基本上是一种急功近利的算法，但是并不代表这种算法不好，如果贪婪的是一种长远和持续，又未尝不可呢？

动态规划

对于大部分的问题，贪婪法通常都不能找出最优解，因为他们一般没有测试所有可能的解。因为贪婪算法是一种短视的行为，只会跟据当前的形式做判断，也就是过早做决定，因而没法达到最佳解。
动态规划和贪婪算法的最大不同是，贪婪算法做出选择，不能在过程优化。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，会动态优化功能。
动态规划算法至少告诉我们两个事： 1.承前启后非常重要：当你准备去做遍历的时候，你的上次的经历不但能开启你以后的经历，而且还能为后面的经历所用。你的每一步都没有浪费。
2.是否可以再回到选择:这意思是——如果你面前有两个选择,你选择了A，并不等于放弃了B，而是选择了A出来再去B要比B出来再去A更容易

Dijkstra最短路径

最短路径是一个Greedy + DP的算法。相当经典，总结了上面两种算法吗，也是我参加TW笔试使用到的算法。这个算法的大意如下：
1.在初始化的时候，所有的结点都和我是无穷大，默认是达不到的。
2.从离自己最近的结点开始贪婪。
3.走过去，看看又能到达什么样的结点，计算并更新到所有目标点的距离。
4.再贪婪与原点最短的结点，如此反复。
这个算法给我带来了一些这样的启示：

有朋友和我说过他想成为一个架构师，或是某技术领域的专家，并会踏踏实实的向这个目标前进，永不放弃。我还是鼓励了他，但我也告诉他了这个著名的算法，我说，这个算法告诉你，架构师或某领域的专家对你来说目前的距离是无穷大，他们放在心中，先看看你能够得着的东西。所谓踏实，并不是踏踏实实追求你的目标，而是踏踏实实把你够得着看得见的就在身边的东西干好。 我还记得我刚参加工作，从老家出来的时候，从来没有想过要成为一个技术牛人，也从来没有想过我的博客会那么的有影响力，在做自己力所能及，看得见摸得着的事情，我就看见什么技术就学什么，学着学着就知道怎么学更轻松，怎么学更扎实，这也许就是我的最短路径。
有很多朋友问我要不要学C++，或是问我学Python还是学Ruby，是不是不用学前端，等等。这些朋友告诉我，他们不可能学习多个语言，学了不用也就忘了，而且术业有专攻。这并没有什么不对的，只是我个人觉得，学习一个东西没有必要只有两种状态，一种是不学，另一种是精通。了解一个技术其实花不了多少时间，我学C的目的其实是为了更懂Java，学TCP/IP协议其实是为了更懂Socket编程，很多东西都是连通和相辅相成的，学好了C/C/Unix/TCP等这些基础技术后，我发现到达别的技术路径一下缩短了.这就好像这个算法一样，算法效率不高，也许达到你的目标，你在一开始花了很长时间，遍历了很多地方，但是，这也许这就是你的最短路径

算法就是Trade-Off

你根本没有办法能得到所有你想得到的东西，任何的选择都意味着放弃——当你要去获得一个东西的时候，你总是需要放弃一些东西。人生本来就是一个跷跷板，一头上，另一头必然下。这和我们做软件设计或算法设计一样，用时间换空间，用空间换时间，还有CAP理论，总是有很多的Trade-Off，正如这个短语的原意一样——你总是要用某种东西去交易某种东西。
我们都在用某种东西在交易我们的未来，有的人用自己的努力，有的人用自己的思考，有的人用自己的年轻，有的人用自己的自由，有的人用自己的价值观，有的人用自己的道德…… ……
有的人在交换金钱，有的人在交换眼界，有的人在交换经历，有的人在交换地位，有的人在交换能力，有的人在交换自由，有的人在交换兴趣，有的人在交换虚荣心，在交换安逸享乐…… ……
每个人有每个人的算法，每个算法都有每个算法的purpose，就算大家在用同样的算法，但是每个人算法中的那些变量、开关和条件都不一样，得到的结果也不一样。我们就是生活在Matrix里的一段程序，我们每个人的算法决定着我们每个人的选择，我们的选择决定了我们的人生

算法学习总结

我摘抄上面的一段文字的原因在于在我学习的路上，也发生过这样的共鸣，只是需要一句流畅的语言说出我的心声：
1.排序算法的学习，让我懂得如何去选择，如果去除杂念，你的选择将无比容易
2.黑白棋的算法是一个贪婪算法，也是一个DP思想，让我学会怎么去努力，如何去回退，如果当前是你最优的选择，你能接受最差的情况发生，那么这条路线就是最好的路线
3.TW的面试题Dijkstra算法计算最短路径，让我更加坚定以前学习的算法是有效的，在你不断坚持的路上，我们在扩宽我们的理解内的“最短路径”时，也会找到自我的成功路径，技术没有尽头，只有无尽的搜索。
4.算法和学习一样，是循序渐进的，慢慢从基础做好，静下心来去沉淀，一切都会豁然开朗。
5.你所失去的东西，都在以另外一种方式归来。你总是要用某种东西去交易某种东西。

注:算法启发部分来自耗子叔博客