二楼我可没说不能插楼~~

续着昨天的恩……可怜就是要看DP的童鞋们看不到了……第一天讲DP我一路睡过去了……
恩恩，上课铃开响
怎么这个点还有这么多同学没来啊，是不是觉得搜索很简单？其实搜索是个基本，不是掌握了DP就好的。好吧，我们不等了。
其实搜索啊，是我们没有办法的时候才要搜索，所以搜索是万能的，所以任何情况下都不可能没事情做。
我们先看一下一些基本概念：我们遇到的一些问题当中，有些问题不能够确切的建立数学模型，或即使有数学模型但该模型的准确方法也不一定能运用现成算法。再要求枚举方案时，常常会遇到这一类问题。解决这一类问题，我们一般采用搜索的方法。即扩展出所有的可能情况。搜索也有状态和转移，两者可能是题目中给出的，也有可能是自己分析出来的。有时候状态和决策的好坏，决定了你做题的好坏。产生式系统是把状态通过转移得到的一棵状态树，称作产生式系统。产生式有三个要素：综合数据库，扩展规则和搜索的策略。
我们先从广度优先搜索开始，我们平时都是从深搜开始，所以我们先从这个平时很少用的东西入手开始（笑，误？）。在搜索算法中，深度越小的节点得到越先得到扩展，这就是广度优先搜索。


度姐姐吃帖子了~~等姐姐吐出来……

下午重点是深搜的优化，上午那道蛋糕（无人举手，老师很无奈……）的优化，我们只能来看看了……（很无奈，很无奈~~）因为知道余下的蛋糕的面积，所以我们可以估算一下余下的侧面积，从而进行剪枝（怎么剪我懒得打……上网找标程吧……好吧好吧……我是坏人……）。
深搜操作消耗时间约定于每个节点操作系数*节点个数，要顺着这个方向进行优化。


n个点的有向完全图，每条边都有一个实数权值，现在我们要找一条长度为n的路使得路上的边权和最接近的一个数x。注意：每个点都有自环（自环是指对于一个点，存在一条边，从这个点出发，指向这个点本身）。可每次搜索一半，搜索出长度为n/2的路径，并存下来，当作路径的前半段。用f[i,j]数组存下所有以i结尾的长度n/2的路经权值和，并将j这一维按权值和排序。即f[i,1]表示所有路径中权值和最大的，f[i,2]表示权值和第二大的。依此类推。然后搜后半段路径，每搜出来一条，若这条路径以i开头，权值和为y，则在f[i]中二分查找一个离x-y最近的权值和，构成完整的路径。这就是一个二分法剪枝的优化。
深搜得剪枝方面，我们从三个方面进行优化：1.搜索的顺序能不能优化，你的顺序不一样，最后取解得时间就不尽相同。2.可行性剪枝，有些地方搜索超过了条件，是不可能的，所以可以进行剪枝。3.最优性剪枝，即只搜索最逼近最优解的搜索剪枝。
我们的功夫要下在编程之外，我们要学会分析，这才是最重要的

15数码问题：
联系八数码的问题，可以用广搜，但状态量太大，所以不行。所以引入迭代加深算法：从小到大枚举ans，用深搜判断ans是否可行。因为ans越小越容易进行可行性剪枝。因为ans枚举出来了，所以不存在最优性剪枝。其实也可以理解成枚举ans，更好的进行最优性剪枝。搜索顺序的优化要根据题目进行讨论。
将估价函数运用到广搜的算法成为A*算法，需用堆来实现。A*算法是理论上时间最优的算法，但是需要的空间太大。为了解决A*算法的空间问题，IDA*算法被提出，它是将估价函数与迭代算法结合起来的算法。

给你n个字符串，长度为5~11都是小写字母组成，告诉你每个字符串都是数学等式，其中有+*=和0~9，问，能否唯一确定每个字母表示什么。如果能够唯一确定，就输出。
这道题，先搜等于号（老师黯然神伤：这支笔不行了……），然后搜乘号或者加号。这道题在这里就体现出来了搜索顺序的优化。‘=’‘+’‘*’不出现在最右，最左不连续出现。‘+’‘*’不出现在‘=’‘+’‘*’附近。不能出现前导0，1~9搜完了n个等式要同时满足。从而进行搜索。
通过这一次学习，我们可以经过归纳总结出分析搜索问题的一般步骤，与对搜索问题优化的大致方向。
分析搜索问题的一般步骤：根据题意确定出状态，并算出状态量，若状态量不是很大，直接广搜，用hash表优化判重。若状态量很大，用深搜优化。
优化：
广搜：（优化的空间并不大，所以我们主要讨论深搜）：用hash表在判重时优化，与DP优化类似，优化状态量的转移
深搜：搜索顺序的优化，最优性剪枝，可行性剪枝。
所有优化都是以这些为核心的。

神经网络（NOIP2003第一题，不打了……就是那道很长，很长，看上去就觉得纠结的题……啊~~真纠结）
没讲……
虫食算（也很著名NOIP2004第四题）
方法一：狂搜……
方法二：可递推的时候递推，不可递推则就进行枚举，递推如果有矛盾，则用回溯进行再次的枚举，附带上很多剪枝，则可以做到完美解决。
方法三：时间不够算了……利用矩阵和各位之间推导出来的的数字关系，进行求解。
传染病控制（NOIP2003第四题，依旧我很懒……）
我们首先想到的是贪心，贪儿子最多的子节点，然后把它切掉。但是这种方式不一定对，随之而来，可以想到随机化贪心，然后一直贪。
其次这道题依旧是搜索的题，所以我们可以用随机化搜索，和随机化贪心的理由一样。
搜索就到这里结束了。