树的搜索策略

许多实际问题的解空间可以组织成一棵树,那么问题的优化解变成了搜索解空间对应的搜索树。这里介绍五种典型搜索策略。 1. 广度优先搜索1.1 算法思想广度优先搜索从树根开始,逐层访问树中的结点。在第k层处理完之后,再处理第k+1层的节点。由此,广度优先搜索使用队列来扩展节点,在处理完该结点之后就将该节点的孩子节点添加到队列中,使得第k+1层节点按序分布; 1.2 算法步骤 构造由根组成的队列Q......

算法分析之贪心算法

1. 算法思想求解优化问题通常可以一步一步来选择求解,贪心算法处理优化问题时,在每一步都选择当前最佳策略,希望通过局部优化来达到全局优化的效果。一般情况下,贪心算法仅会得到一个可行解,并非最优解。如 0-1背包问题 (这里不包括分数背包问题)。 2. 前提条件任何问题只要其具备了贪心选择性和优化子结构就可通过贪心算法获得该问题的最优解。 贪心选择性 : 如果一个优化问题的贪心选择必然出......

算法分析之动态规划

1. 算法思想动态规划建立在分治思想的基础上,在利用分治算法求解问题时,可能遇到子问题之间互相关联,会造成重复求解,从而影响算法效率。那么对于这类具有优化子结构和子问题重叠性的优化问题时,可以根据优化子问题设计数据结构和i问题的求解次序,从规模最小的子问题开始自底向上地计算每个子问题的解,保证每个子问题被求解一次;将求得的子问题的解和构造最优解所需要的信息存储在数据结构中;再根据最优解的构造......

算法分析之分治算法

1. 基本原理经验告诉我们,小规模问题的解通常比大规模问题的解更容易得到,所以,在面对一个大规模问题时,可以考虑转换为几个具有相同形式的子问题来求解。实践证明,这种分而治之的策略简单而实用。 2. 适用前提 问题的规模缩小到一定程度可以轻易解决 问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质 利用该问题分解出的子问题的解可以合并为该问题的解 该问题所分解出的各个子问题是......

高级数据结构之Patricia Tree

1. Patricia Tree的提出PATRICIA (Practical Algorithm to Retrieve Information Coded In Alphanumeric)由D.Morrisonrz 于1968年首次提出,Gonnet 在90年代将PATRICIA 应用到全文检索领域,发展成为PAT tree 并获得巨大成功。它也是TRIE树的一种, 2. 题外由于在课程......

使用 LATEX排版 数学公式

1. 常见数学符号的实现1.1 指数及下标的实现$x_{1}$ $x_{1}$ x_{1}$$x_{1}$$双$$为居中 $x^{2}\qquad a_{ij}^{-\alpha t}$ $x^{2}\qquad a_{ij}^{-\alpha t}$ 1.2 平方根的实现$\sqrt{ x^{2}+\sqrt{y} }$ $\sqrt{ x^{2}+\sqrt{y} }$ 1.3 在表达式......

KNN实战之改进约会网站的配对效果

1. 说明此文案例来自于《机器学习实战》,适合初学机器学习的入门者,要运行本文的实例代码需要安装 numpy、 scikit-learn、matplotlib 以及jupyter,博主使用的是 python2, 所有代码建议在jupyter 下按序运行。 2. 案列背景有一个舍友A在约会网站上寻找对象,约会网站会推荐不同的人选,但并不是很准确。通过总结,可以发现A他曾经交往过三种类型的人:......

深入理解C++指针、引用及指针的指针

C++ 用了这么久,发现身边还是有同学不能理解 C++ 的指针、引用的本质,对指针的指针、指针的引用更是十分迷糊。现在让我们来理解一下它们吧! 1. 指针与引用指针与引用都可以对对象进行直接的操作,通常作函数的参数传递或是函数返回的对象。 1.1 理解本质指针,本质上是一个变量,指向一块内存空间,只不过该内存存放的是某个变量的地址。这就不难理解,指针可以改变指向,也就是存放别的变量的地址;也......

[转载]:从头到尾彻底理解KMP

非常详尽、易懂的关于KMP算法的博文

从头到尾彻底理解KMP算法本文转自 July (七月在线创始人) 的博文,KMP算法已经是第二次准备吃透了,书和博文看了不少,感觉还是理解的不是十分透彻,直到看了 July 关于 KMP 算法的详解。 原文在此 1. 引言    本KMP原文最初写于2年多前的2011年12月,因当时初次接触KMP,思路混乱导致写也写得混乱。所以一直想找机会重新写下KMP,但苦于一直以来......

Python进阶之生成器

较详细地介绍了生成器的两种生成方式、特性以及方法

1. 生成器(generator)什么是生成器呢,要理解生成器你就必须先理解什么是迭代器,因为生成器也是一种迭代器,是一种更高级、更优雅的迭代器。关于迭代器,如果你不明白的话,本博文的 前一篇有讲解,这里不再赘述。首先,明白下面两点: 任意生成器都是迭代器 (反之不成立)。 任意生成器,都是一个延迟产生值的工厂。 2. yieldPython 有两种不同的方式提供生成器:现在介绍第一种:......