图灵普及1班A总结（二）：
第四课（经典贪心）：
贪心算法的定义:
1.贪心算法（greedy algorithm，又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。
也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。贪心算法不是对所有问题都能
得到整体最优解，关键是贪心策略的选择。
2.贪心的精髓在于不用穷举所有解空间，就能找到答案。每一步都需要进行选择，选择需要满足贪心选择性质，
问题具有最优子结构性质，子问题之间相互独立。
第五课（朴素贪心）：
1.除了经典的，有模板的贪心题以外，还有很多需要灵活思考和创造性解决的贪心问题。这些问题可能需要考虑
多种因素，或者需要利用特殊的性质来优化贪心策略。
第六课（二分答案）：
2.二分算法 :称为折半法,是一种在有序数组中查找特定元素的搜索算法,主要用于数组的数据比较多的时候
3.二分算法查找的思路如下:
1.首先,从数组的中间元素开始搜索,如果该元素正好是目标元素,则搜索过程结束,否则执行下一步;
2.如果目标元素大于/小于中间元素,则在数组大于/小于中间元素的那一半区域查找,然后重新步骤1的操作;
3.如果某一步数组为空,则表示找不到目标元素。
4.当问题的答案具有单调性时，我们就可以二分答案。单调性可以理解为，随着x的增加，对应y值逐渐增大——单
调递增；或者随着x的减小，对应y值逐渐减小——单调递减。
第七课（搜索）：
1.搜索算法是利用计算机的高性能来有目的地穷举一个问题解空间的部分或所有的可能情况，从而求出问题的解的一种
方法。现阶段一般有枚举算法、深度优先搜索、广度优先搜索、A*算法、回溯算法、蒙特卡洛树搜索、散列函数等算
法。在大规模实验环境中，通常通过在搜索前，根据条件降低搜索规模；根据问题的约束条件进行剪枝；利用搜索过
程中的中间解，避免重复计算这几种方法进行优化。
2.广度优先搜索
广度优先搜索算法（又称宽度优先搜索）是最简便的图的搜索算法之一，其别名又叫BFS，属于一种盲目搜寻法，目的
是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到
找到结果为止。
3.基本概念
广搜是一种图形搜索演算法。简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点，如果发现目标，则演算终止。
所谓宽度优先算法，就是算法自始至终一直通过已找到和未找到顶点之间的边界向外扩展，就是说，算法首先搜索和s距离为
k的所有顶点，然后再去搜索和S距离为k+l的其他顶点。所谓广度，就是一层一层的，向下遍历，层层堵截，我们如果要是广
度优先遍历的话，我们的结果是V1 V2 V3 V4 V5 V6 V7 V8。
1、访问顶点vi ；
2、访问vi 的所有未被访问的邻接点w1 ,w2 , …wk ；
3、依次从这些邻接点（在步骤②中访问的顶点）出发，访问它们的所有未被访问的邻接点; 依此类推，直到图中所有访问过的顶点的邻接点都被访问；
DFS的相关介绍：
DFS：深搜。优先往下(深处)走，当达到目标终点(得到一种方案)之后，再往上(前)回溯[回溯之后要注意"恢复现场"]。 重复往下走&往上回溯的操作，
直到得到根节点对应的某一个大分支的所有的方案数。再重复另一个分支的操作，直到得到所有的方案总数。DFS俗称暴搜，它的流程是一个树的形式，
类似以前学的树状图，但每次只会存当前的一个路径，不需要存整棵树。 其实也不需要真的去写一个栈把这个流程存下来，在写的递归函数里面，会有
一个隐藏的栈帮我们做维护, 不需要开额外的空间。系统会为我们做回溯。DFS最需要考虑的问题：顺序，即考虑要用一个什么样的顺序把某一个题目所
有的方案全部遍历一遍 。