队列

特点：先进先出（First In First Out,FIFO）。

(栈是后进先出的数据结构，LastIn First Out,LIFO)

入队和出队操作。

树

树是一种特殊的图，其中没有往后指的边。

狄克斯拉特算法

查找最快的路径，即距离最短的路径。

适用范围：有向无环图(directed acyclic graph,DAG)，且不包含负权边（即边的权重为负值）。

（包含负权边的图，找最短路径用 贝尔曼—福德算法Bellman-Ford algorithm）

每一段都分配了权重(weight)，带权重的图à加权图(weightedgraph)

不带权重的图à非加权图(unweighted graph)

环

4个步骤：

1）找出“最便宜“的节点，即 可在最短时间内到达的节点；

2）更新该节点的邻居的开销；

3）重复这个过程，直到对图中的每一个节点都这么做了；

4）计算最终路径。

举例：

计算起点到终点的最短路径的总权重？

贪婪算法

NP完全问题

NP问题(Non-deterministicPolynomial问题)即多项式复杂程度的非确定性问题。

如果任何一个NP问题都能通过一个多项式时间算法转换为某个NP问题，那么这个NP问题就称为NP完全问题（Non-deterministic Polynomial complete problem）。NP完全问题也叫做NPC问题。

贪婪算法

特点：一般不能获取最优解，但是结果也非常接近最优解。

思路：寻找局部最优解，企图用这种方式获取全局最优解：

每步都选择局部最优解à最终全局最优解

1、教室调度问题

2、背包问题

假设可盗窃以下3种物品：

使用贪婪算法得到的是30，虽然不是35但也非常接近了。

3、集合覆盖问题

实现代码：

NP完全问题

如：旅行商问题(2!) ； 集合覆盖问题

NP完全问题的判别方法：

集合

| 并集 （集合A与集合B合并）

& 交集 （两个集合中都有的元素）

差集（A-B  在集合A中但不在集合B中的元素）
• 1

动态规划

借用网格

工作原理：先解决子问题，再逐步解决大问题。

使用范围：子问题是离散的。（即子问题不依赖于其他子问题）

1、背包问题

假设你是个小偷，背着一个可装4磅东西的背包。

注：1每个单元格都将包含当期能够装入背包的所有商品。

2各行的排列顺序无关紧要。

每个单元格的填充公式：

如果增加1个iphone，2000美元，1磅，则结果如下：

2、旅行行程最优化

3、最长公共字符串问题

假设Alex不小心输入了hish，那么他原本是想输入fish还是vista呢？

公式伪代码：

4、最长公共子序列

假设Alex不小心输入了fosh，那么他原本是想输入fish还是fort呢？

公式伪代码：

K近邻算法

求距离，常用欧式距离。

分类问题与回归问题

后续补充机器学习相关知识。

应用场景举例：

OCR光学字符识别

垃圾邮件过滤 （朴素贝叶斯）

预测股票市场