c语言背包问题_c语言背包问题几种解法_背包问题贪心算法(3)

(4).搜索(包括DFS, BFS, A*)

搜索也是ACM中相当重要的一个组成部分，涉及范围也是相当之广，首先是最为基础的深度优先搜索DFS，所谓的DFS，其实就是通过递归的方式枚举所有的可能从而得到我们想要的结果，而搜索中相当重要的一个技巧就是剪枝，即人为地删去一些没有必要搜索的可能，从而提高我们程序的效率，DFS的经典题有最为著名的八皇后为题，Sticks等等。其实DFS的题实在是太多了，PKU上有很多的题可以供我们练手。另外一个就是广度优先搜索(BFS)了，广度优先搜索是基本思想就是建立一个队列(队列是一种基本的数据结构，我会在下一部分中说明)，然后每一次都拿出队列出的一个点扩展出所有的可能，再把我们需要的解放入队列等着下次再扩展，一直扩展到找到答案或者不能扩展为止，BFS的经典题有跳马问题，八数码等。BFS有一个非常常用的技巧或者说是优化，就是双向BFS，思想是一样的，就是同时从起点和终点开始扩展，等到出现交点的时候就意味着找到了答案，这样比起普通的BFS可以节省大量的空间和时间。BFS还有另外一个常见的扩展，就是优先队列BFS，所谓的优先队列(优先队列是队列的一种实现，我同样会在下一部分中给出解释)，就是始终都保持队列的队首元素是最小的，这样每次扩展的就是当前最小的元素了，这里所谓的最小，其实指的是当前看来最优的解，利用这么一种贪心的方法，来加快我们搜到答案的速度，当然了，具体的效率还要看题目的数据。说了这么多的优先队BFS，其实就是A*的一种特殊情况，A*的中文名是启发式搜索，是人工智能中常用的一种搜索技术，A*最基础的应用就是求最短路，通过某个估价函数对当前的点做出一个价值评估，然后将这些扩展出来的点按照其价值放入一个优先队列中，那么我们每次拿出的队首元素不就是我们当前最优希望的一个点吗？如果用STL(C++的标准模板库，同样会在下一部分中给出解释)来实现优先队列的话，A*比起BFS的代码量几乎没增加，无非多了一个估价函数，但是问题就在于如何更好地设计出一个估价函数，A*的经典题有贪吃蛇，八数码。

(5).C++应用之STL

STL是C++的标准模板库，为我们提供了相当多的现成的库函数和数据结构，STL即可以极大地缩短我们的代码长度，有可以极大地降低我们出错的概率。那么你可能就奇怪了，为什么我还会恨STL呢？理由很简单，我们必须要付出相当大代价，那就是效率。下面我简要地介绍一下STL在ACM中的简单应用。c语言背包问题首先就是STL中的库函数了，其中我们有我们最为常用的sort排序函数，有find，lower_bound和upper_bound等一些查找函数用来简化我们的代码，另外最常用的就是顺序容器和关联容器了，其实顺序容器可以相当相当程度上代替一些常用的基础数据结构如vector可以代替长度可变的数组(可以简单地实现邻接表)，list可以代替链表，stack可以代替栈，deque可以代替双端队列，priority_queue可以代替我们前面提到的优先队列，而关联容器中的map可以实现任意两种类型的数据之间的索引，而set可以查找某个集合中是否存在某个元素。

(6).数据结构之基础篇

数据结构在ACM中应用非常广泛，但单独考查某个数据结构基础的题目较少，一般都是起一些辅助的作用，比如我们前面提到的优先队列，还有一个非常常用的就是哈希，前面我们提到过，在BFS的过程中，我们需要从每次扩展出来的点中筛选出来我们需要的点放入队列中，哪些是不需要的点，一般来说，指的是和以前某个搜索过的点具有相同的状态的点，而判别状态是否相同的方法经常是利用哈希来保存以前搜索过的状态，并且判断每次扩展出来的点的状态是否已经存在，如果不存在，我们再把它放入队列中。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/tongxinshuyu/article-24376-3.html