最近这周计划弄一弄搜索...然后教练推荐我们将紫书第七章的内容处理好
虽然搜索联赛前已经涉及许多，但之前一直没有弄紫书，把紫书大概看了一下，写一点东西，算是一个小记录吧
紫书概况
7.1 简单枚举
[例7-3] 1/k=1/x+1/y，输入k求所有的正整数x,y
[答]
∵y<=x
∴1/y>=1/x
∴y<2k，可以枚举，x=k*y/(y-k) (要求 k*y%(y-k)==0)
似乎第一次想的是数学方法，然后错了...解答还是比较巧妙的
7.2 枚举排列
7.2.1 递归求全排列
7.2.2 求元素可重复的排列
7.2.3 解答树
[推出全排列的复杂度是O(n!)的]
每步都有几个可以选择的方向，通过这个来建树
深度优先和广度优先也是从解答树的生成来命名的
7.2.4 下一个排列
使用next_permutation(p,p+n) STL函数
7.3 子集生成
7.3.1 增量构造法
每次加一个元素，然后在剩余集合中递归操作
7.3.2 位向量法
在解答树上增加一个不选选项，所有的叶子节点表示一个不完整解
7.3.3 二进制法
最常用的方法，支持位运算
7.4 回溯法
7.4.1 八皇后
7.4.2 其余例子
枚举量很大时：回溯法>构造判定
回溯时只需比较当前元素和之前元素，不用管再之前元素是否相互冲突
可以想办法在某个结果时预测最好结果[最优性剪枝]
[例7-7]天平难题
在每次枚举的时候求每一种分法的值，然后选出这些分法中最优的一个，作为这一层的最优值返回。每次递归下去两个二进制表示的数就好了。
当然这是一个错误的思想，因为有墙壁的限制，所以不能说最大的就是最优的，因为问的是最长情况，也不能说最小的是最优的。这个方法是错的。
所以正解是每次都要把答案传下去，到最后不能分了为止来更新答案，不能在下面的部分选值。
7.5 路径寻找问题
在隐式图上找最优值的方法。隐式图指只告诉你出发节点和结束节点，其它节点需要你用程序去拓展的图。
每个解到终点都是一条路径，所有这样的路径便形成了解答树。
在隐式图中，常常会有相同节点，需要HASH判重。
双向广搜也是比较好的方法，虽然对于题目的限制较大，但是效率比单向的好。
7.6 迭代加深搜索
这个专题之前涉及较少，记忆比较深的是那道：栅栏的木料
常对于解答树又深又宽的题，且常常这种题的最优解不是很深。
[codevs1288 埃及分数]
迭代加深+最优性剪枝
[UVa11212 编辑书稿]
迭代加深+最优性剪枝
这题的最优性剪枝很巧妙，妙在取了一个h(S)表示S状态下的后接不同的数字的数目，并得出每一步最多让它减三的结论。
7.7 竞赛题目选讲
7.8 参考训练
上面两个部分主要涉及的就是题目了，到时候会再开博客对里面一些不错的题目说说看法。
当然看完紫书之后还有一个想了解的A*算法没有看到多少，于是自己看了看黑书[感觉黑书给我的感受还是比较深的]
黑书概况
1.6.1 概念
搜索是将枚举分阶段，然后在一些阶段进行选择性跳过一些节点代表的子树，从而达到加快找最优(可行)解速度的过程。
状态就是这样的一些节点，状态转移就是这张图上的有向边。智能体就是操作状态转移的人。如果智能体大于1，(一般是2人)就成了博弈搜索了。
1.6.2 盲目搜索算法
纯随机搜索 [普通深搜、广搜]
重复式搜索 [迭代加深、迭代加宽、柱式搜索(固定拓展的节点数)] 后两种因为效果不怎么样，应用不广，所以不常用。
双向广度优先搜索
就是从起始状态和终止状态分别进行搜索。
有一种比较好的情况，是所有询问的目标节点相同，可以采用周界搜索。
周界搜索：反向搜索一次，用HASH或Trie树记录下访问到的所有节点信息的过程。这里的反向搜索也不一定要拓展完所有点[可能点是大于1e8的]，只需要根据题目拓展一定的层数即可。
不是周界搜索的话，就是看哪边节点少拓展哪一边了[不是按层哦]。
1.6.3 启发式搜索算法
概念：状态 S
实际到终点的距离 h*(S)；估计到终点的距离[S的估价函数] h(S)；到状态S之前的代价 g(S)；S的启发函数 f(S)=g(S)+h(S)
构造估价函数是最重要的步骤，估价函数也通常是比正确值少的，表示到终点的下界。
如果估价函数对于任意s1,s2满足h(s1)<=h(s2)+c(s1,s2)，就是h的减少值最多等于状态转移的实际代价(其实就是要求h()不能下降的太快)，就称h()函数的相容的。如果其相容，则会满足f()函数单调。
贪心搜索，每次只拓展可以拓展的节点中h(S)最小的一个，从而到达终点得到的解。但是因为h(x)是不准确的，不能保证最优解。[但是例如求第k短路中的h(x)=h'(x)，所以可以使用贪心搜索]
A*搜索，每次拓展的是f(S)中最小的一个，遇到重复状态时，保留较小的f()值，这个好处在于不仅考虑的h(x)的因素，也考虑了g(x)，g(x)便涉及到转移的方式，最后得到的解一定是最优的。
A*搜索的实现：需要一个保存带拓展节点的表一，因为要判重，也要使用一个表二来存所有节点。表一需要取最小值，添加和替换的操作，表二有查找和插入的操作。表一可以用堆，表二可以用Hash表或者二叉搜索树来判重。
IDA*就是迭代加深A*算法，忽略所有f()大于maxd的节点即可，不需要堆和二叉搜索树，只需要一个可以加可以删的数据结构即可[栈或队列?]，空间也大大减小，但是别忘了，迭代搜索的适用范围。
黑书的后面就是博弈了...目前没有这么多闲心啊...大脑会比较不够用的感觉...留坑在这了...一定有时间回来再看的。