广搜可用于求最短路线，如果节点之间的距离都差不多的话。还可以用来整合借钱关系。还可以用来在人际关系网络中寻找某个要找的人，朋友是一度关系，朋友的朋友是二度关系，有个七度空间理论就是值大概这样递归七次就能找到任何想要找到的人。为了防止重复，可以把查看过的结果放入一个set里。而广搜的时候，先将一度关系如队列，检查一度关系是否满足要求，不满足就将该一度关系下的二度关系入队列。
狄克斯特拉算法是广搜的演变结果：广搜中等距离的关系，变成了不等距的权重。可以用来求首尾确定的结点之间的距离。只能用于有向无环图，因为在每个结点处，都要更新从该结点出发走到的下一个结点距离出发点的距离，如果距离有更新还要记录是哪个结点走到这个结点的；因此，不能有环，否则会有无限多个岔路。也不能把走过的结点加入set，因为就是有可能有多条通往一个结点的路，就是有可能刷新这个结点距离出发点的距离。也就是说，终点之前的结点不能往之前的结点走。原因在于，无法判断是否有环，而一旦有环就陷入死循环了。
但书中说狄克斯特拉算法不能判断负向边存在的情况，我觉得作者是没有好好想过实现方式，只要是有向无环图，就有办法把所有能通往终点的边都走一遍，有的是办法：除了出发点和终点，所有路过的分支结点都依次入队列，更新结点权重和父指针一如既往，但每个结点都要在出队列的时候，判断其子节点是否在队列里，不在就加入队列，这样是为了避免重复，这样走一遍，直到队列为空就好了。
快排，可能很多人不知道它在某些情况下是线性时间复杂度的，《算法》（人邮第四版）里有相关证明：在有大量重复元素的情况下，对重复元素有特别处理的快排可以达到线性时间复杂度。通常情况下，没有那么多重复元素，可以在每次选择pivot的时候，做随机选择，交换到待定序列的第一个位置。
NP完全问题，N是Not，P是Polynomial，多项式时间复杂度内不能解决的问题。贪婪算法的想法：既然找不到多项式复杂度的解法，那每一步就都不要纠结、直接选最优解吧。
动态规划：先解决子问题，问题可以离散地拆分。动态规划的网格，有一个很基本的原理：左边的值小于右边的，上边的值小于下边的；这样，在动态扩展中，可以从子问题推到原问题。最长字串必然要求字串连续，因此最优解的路径是一条对角线，只需利用右下大于左上的值这一思想即可。最长子序列则需要利用两个方向都进行值的传递。
至此，算是告一段落。这本书的优秀之处，以动态规划为例，在于它首先通过一个真实有用的案例引入问题，赋予了问题以意义，给我想学习解决问题之思路的动力；另外，它将公式图示，公式往往不能独立传达完整可信的信息，数学最喜欢的就是掐头去尾地简化不必要的细节，这也许就是编程语言的动人之处，想想微积分课程里，数学前辈们用一个变量可以同时表示变量、常量、微分，只要你心里清楚，但计算机语言可能得分开去存不同的值，编程者习惯了严谨、诚恳，因为他们面对的计算机也是如此。
网友评论