prim算法导论

A. prim算法中，closedge[j].lowcost 是干什么用的。新定点并入U后重新选择最小边。那段代码没看懂。 辅助

在看严蔚敏的这个prim算法之前，我是看的《算法导论》上的prim算法，感觉那个更容易理解prim算法，只是严的有相应的步骤，可以照着实现，网上好多实现prim算法的，貌似也是基于这个。那个closedge[j].lowcost是用来记录V到U-V的权值的（V是已经选择的边，U是所有的边，U-V是剩下的边），在这里可以找到V到U-V的最小权值。你手边应该有书吧，那我就对着严的书说了，对于V1有V2，V3，V4分别是6，1，5，这时可以存入数组（对着那个P174的表），然后选了V3，这个时候就是需要更新closedge.lowcost，因为V2到V1是6而V2到V3是5，所以P175那边的算法倒数第六行的for循环就是用来更新这个的，因为对于新加入的点，可能会出现上面说的情况，其余应该没什么问题的吧

B. 《算法导论》（第三版）目录

1.1 算法

1.2 作为一种技术的算法

2.1 插入排序

2.2 分析算法

2.3 设计算法

2.3.1 分治法

2.3.2 分析分治算法

3.1 渐近记号

3.2 标准记号与常用函数

4.1 最大子数组问题

4.2 矩阵乘法的 Strassen 算法

4.3 用代入法求解递归式

4.4 用递归树方法求解递归式

4.5 用主方法求解递归式

*4.6 证明主定理

4.6.1 对 b 的幂证明主定理

4.6.2 向下取整和向上取整

5.1 雇佣问题

5.2 指示器随机变量

5.3 随机算法

*5.4 概率分析和指示器随机变量的进一步使用

5.4.1 生日悖论

5.4.2 球与箱子

5.4.3 特征序列

5.4.4 在线雇佣问题

6.1 堆

6.2 维护堆的性质

6.3 建堆

6.4 堆排序算法

6.5 优先队列

7.1 快速排序的描述

7.2 快速排序的性能

7.3 快速排序的随机化版本

7.4 快速排序分析

7.4.1 最坏情况分析

7.4.2 期望运行时间

8.1 排序算法的下界

8.2 计数排序

8.3 基数排序

8.4 桶排序

9.1 最小值和最大值

9.2 期望为线性时间的选择算法

9.3 最坏情况为线性时间的选择算法

10.1 栈和队列

10.2 链表

10.3 指针和对象的实现

10.4 有根树的表示

11.1 直接寻址表

11.2 散列表

11.3 散列函数

11.3.1 除法散列法

11.3.2 乘法散列法

*11.3.3 全域散列法

11.4 开放寻址法

11.5 完全散列

12.1 什么是二叉树

12.2 查询二叉搜索树

12.3 插入和删除

12.4 随机构建二叉搜索树

13.1 红黑树的性质

13.2 旋转

13.3 插入

13.4 删除

14.1 动态顺序统计

14.2 如何扩张数据结构

14.3 区间树

15.1 钢条切割

15.2 矩阵链乘法

15.3 动态规划原理

15.4 最长公共子序列

15.5 最优二叉搜索树

16.1 活动选择问题

16.2 贪心算法原理

16.3 赫夫曼编码

*16.4 拟阵和贪心算法

*16.5 用拟阵求解任务调度问题

17.1 聚合分析

17.2 核算法

17.3 势能法

17.4 动态表

17.4.1 表扩张

17.4.2 表扩张和收缩

18.1 B 树的定义

18.2 B 树上的基本操作

18.3 从 B 树上删除关键字

19.1 斐波那契结构

19.2 可合并堆操作

19.3 关键字减值和删除一个结点

19.4 最大度数的界

20.1 基本方法

20.2 递归结构

20.2.1 原型 van Emde Boas 结构

20.2.2 原型 van Emde Boas 结构上的操作

20.3 van Emde Boas 树及其操作

20.3.1 van Emde Boas 树

20.3.2 van Emde Boas 树的操作

21.1 不相交集合的操作

21.2 不相交集合的链表表示

21.3 不相交集合森林

*21.4 带路径压缩的按秩合并的分析

22.1 图的表示

22.2 广度优先搜索

22.3 深度优先搜索

22.4 拓扑排序

22.5 强连通分量

23.1 最小生成树的形成

23.2 Kruskal 算法和 Prim 算法

24.1 Bellman-Ford 算法

24.2 有向无环图中的单源最短路径问题

24.3 Dijkstra 算法

24.4 差分约束和最短路径

24.5 最短路径性质的证明

25.1 最短路径和矩阵乘法

25.2 Floyd-Warshall 算法

25.3 用于稀疏图的 Johnson 算法

26.1 流网络

26.2 Ford-Fulkerson 方法

26.3 最大二分匹配

*26.4 推送-重贴标签算法

*26.5 前置重贴标签算法

27.1 动态多线程基础

27.2 多线程矩阵乘法

27.3 多线程归并排序

28.1 求解线性方程组

28.2 矩阵求逆

28.3 对称正定矩阵和最小二乘逼近

29.1 标准型和松弛型

29.2 将问题表达为线性规划

29.3 单纯形算法

29.4 对偶性

29.5 初始基本可行解

30.1 多项式的表示

30.2 DFT 和 FFT

30.3 高效 FFT 实现

31.1 基础数论概念

31.2 最大公约数

31.3 模运算

31.4 求解模线性方程

31.5 中国余数定理

31.6 元素的幂

31.7 RSA 公钥加密系统

*31.8 素数的测试

*31.9 整数的因子分解

32.1 朴素字符串匹配算法

32.2 Rabin-Karp 算法

32.3 利用有限自动机进行字符串匹配

32.4 Knuth-Morris-Pratt 算法

33.1 线段的性质

33.2 确定任意一对线段是否相交

33.3 寻找凸包

33.4 寻找最近点对

34.1 多项式时间

34.2 多项式时间的验证

34.3 NP 完全性与可归约性

34.4 NP 完全性的证明

34.5 NP 完全问题

34.5.1 团问题

34.5.2 顶点覆盖问题

34.5.3 哈密顿回路问题

34.5.4 旅行商问题

34.5.5 子集和问题

35.1 顶点覆盖问题

35.2 旅行商问题

35.2.1 满足三角不等式的旅行商问题

35.2.2 一般旅行商问题

35.3 集合覆盖问题

35.4 随机化和线性规划

35.5 子集和问题

A.1 求和公式及其性质

A.2 确定求和时间的界

B.1 集合

B.2 关系

B.3 函数

B.4 图

B.5 树

B.5.1 自由树

B.5.2 有根树和有序树

B.5.3 二叉树和位置树

C.1 计数

C.2 概率

C.3 离散随机变量

C.4 几何分布与二项分布

C.5 二项分布的尾部

D.1 矩阵与矩阵运算

D.2 矩阵的基本性质

C. 基础-11：最小生成树（MST）

最小生成树（minimum spanning tree）是图计算中基本的问题，背后的问题非常直接，假设无向连通图G(V, E)，且E中的每条边e有权值（可以表示距离、价值等），找出一颗树，连接G中所有的边，且连接这棵树的所有边的权值之和最小。在电子制造中，如何以最低的成本连接多个针管便是这一问题。

下面以一个图来对此进行说明：

前面两课中介绍了动态规划和贪心算法，都是用来解决最值问题，本文中的最小生成树很显然也属于此类。最小生成树使用贪心算法，文中会对贪心算法的使用进行说明。

假设mst是最终要求的最小生成树，若A是最小生成树mst边集的子集，如果每次选择一条边(u, v)加入A，并且确保A始终是mst边集的子集，则最终得到的A必然是mst最小生成树的边集。这样的边(u, v)称为A的 安全边 。安全边即为可以选择的边。

为了得到安全边，下面介绍一些概念。无向图G=(V,E)的一个切割(S, V-S)是节点集V的一个划分，如图2所示：

显然，一个切割将图划分为两部分。如果一条边(u,v)，u在S中，v在S-V中，则称边(u,v)横跨切割(S, V-S)。如果集合A中不存在横跨该切割的边，则称该切割尊重A；在横跨切割的所有边中，权重最小的边称为轻量级边（注：轻量级边可能不是唯一的）。

下面的定理和推论保证了Kruskal和Prim算法的正确性，感兴趣的童鞋可以自己证明或参考算法导论中的说明。

根据定理1和推论1，构造最小生成树可以有两种方式，一种是切割的角度，一种是森林的角度。切割的角度：先从图中选取一个点n ₁ ，划一个切割({n ₁ }, V-{n ₁ })，然后找这个切割的轻量级边以及这个边在 V-{n ₁ }的节点n ₂ ；然后再划一个切割（{n ₁ , n ₂ }, V-{n ₁ , n ₂ })，再找出对应的轻量级边，...,直到所有的节点，每一步中找到的轻量级边组成的集合为最小生成树中的边。

森林的方式是：首先将每个节点都看成一个连通分量（此时有n个连通分量），寻找连通连接连通分量权值最小的边(u, v)，(u, v)连接的连通分量为C ₁ 和C ₂ ，则(u, v)连接后，合成一个更大的连通分量C ₁₂ （此时有n-1个连通分量）；然后对n-1个连通分量继续实施上述类似的动作，直至最后变成一个连通分量。

切割的角度对应的是Prim算法，森林的方式对应的是Kruskal算法，算法本身都很简单，在此不再赘述，下面两组从算法导论中摘取的图很好地解释了对应的算法。

最小生成树是图计算中的基本算法，理解算法的关键是切割基础上的轻量级边，上文的说明中野间接解释了利用贪心算法的正确性，相对而言，最小生成树是较为简单和基础的算法，是其他算法的基础。

D. 算法怎么学

贪心算法的定义：

贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，只做出在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

解题的一般步骤是：

1.建立数学模型来描述问题；

2.把求解的问题分成若干个子问题；

3.对每一子问题求解，得到子问题的局部最优解；

4.把子问题的局部最优解合成原来问题的一个解。

如果大家比较了解动态规划，就会发现它们之间的相似之处。最优解问题大部分都可以拆分成一个个的子问题，把解空间的遍历视作对子问题树的遍历，则以某种形式对树整个的遍历一遍就可以求出最优解，大部分情况下这是不可行的。贪心算法和动态规划本质上是对子问题树的一种修剪，两种算法要求问题都具有的一个性质就是子问题最优性(组成最优解的每一个子问题的解，对于这个子问题本身肯定也是最优的)。动态规划方法代表了这一类问题的一般解法，我们自底向上构造子问题的解，对每一个子树的根，求出下面每一个叶子的值，并且以其中的最优值作为自身的值，其它的值舍弃。而贪心算法是动态规划方法的一个特例，可以证明每一个子树的根的值不取决于下面叶子的值，而只取决于当前问题的状况。换句话说，不需要知道一个节点所有子树的情况，就可以求出这个节点的值。由于贪心算法的这个特性，它对解空间树的遍历不需要自底向上，而只需要自根开始，选择最优的路，一直走到底就可以了。

话不多说，我们来看几个具体的例子慢慢理解它：

1.活动选择问题

这是《算法导论》上的例子，也是一个非常经典的问题。有n个需要在同一天使用同一个教室的活动a1,a2,…,an，教室同一时刻只能由一个活动使用。每个活动ai都有一个开始时间si和结束时间fi 。一旦被选择后，活动ai就占据半开时间区间[si,fi)。如果[si,fi]和[sj,fj]互不重叠，ai和aj两个活动就可以被安排在这一天。该问题就是要安排这些活动使得尽量多的活动能不冲突的举行。例如下图所示的活动集合S，其中各项活动按照结束时间单调递增排序。

关于贪心算法的基础知识就简要介绍到这里，希望能作为大家继续深入学习的基础。

E. 图的相关算法（二）：最小生成树算法

在含有n个顶点的连通图中选择n-1条边，构成一棵极小连通子图，并使该连通子图中n-1条边上权值之和达到最小，则称其为连通网的最小生成树。

例如，对于上图中的连通网可以有多棵权值总和不相同的生成树。

克鲁斯卡尔（Kruskal）算法，是用来求加权连通图的最小生成树的算法。

基本思想 ：按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路。
具体做法 ：首先构造一个只含n个顶点的森林，然后依照权值从小到大从连通网中选择边加入到森林中，并使得森林不产生回路，直到森林变成一棵树为止。

以图G4为例（更详细的可以参考《算法导论》p367），对Kruskal进行演示（假设，用数组R保存最小生成树结果）。

第1步 ：将边<E,F>加入R中。
边<E,F>的权值最小，因此将它加入到最小生成树结果R中。
第2步 ：将边<C,D>加入R中。
上一步操作之后，边<C,D>的权值最小，因此将它加入到最小生成树结果R中。
第3步 ：将边<D,E>加入R中。
上一步操作之后，边<D,E>的权值最小，因此将它加入到最小生成树结果R中。
第4步 ：将边<B,F>加入R中。
上一步操作之后，边<C,E>的权值最小，但<C,E>会和已有的边构成回路；因此，跳过边<C,E>。同理，跳过边<C,F>。将边<B,F>加入到最小生成树结果R中。
第5步 ：将边<E,G>加入R中。
上一步操作之后，边<E,G>的权值最小，因此将它加入到最小生成树结果R中。
第6步 ：将边<A,B>加入R中。
上一步操作之后，边<F,G>的权值最小，但<F,G>会和已有的边构成回路；因此，跳过边<F,G>。同理，跳过边<B,C>。将边<A,B>加入到最小生成树结果R中。

此时，最小生成树构造完成！它包括的边依次是： <E,F> <C,D> <D,E> <B,F> <E,G> <A,B> 。

根据前面介绍的克鲁斯卡尔算法的基本思想和做法，我们能够了解到，克鲁斯卡尔算法重点需要解决的以下两个问题：
问题一 对图的所有边按照权值大小进行排序。
问题二 将边添加到最小生成树中时，怎么样判断是否形成了回路。

问题一用排序算法排序即可。
问题二，处理方式：记录顶点在“最小生成树”中的终点，顶点的终点是“在最小生成树中与它连通的最大顶点"(关于这一点，后面会通过图片给出说明)。然后每次需要将一条边添加到最小生成树时，判断该边的两个顶点的终点是否重合，重合的话则会构成回路。 以下图来进行说明：

在将<E,F> <C,D> <D,E>加入到最小生成树R中之后，这几条边的顶点就都有了终点：

关于终点，就是将所有顶点按照从小到大的顺序排列好之后；某个顶点的终点就是"与它连通的最大顶点"。 因此，接下来，虽然<C,E>是权值最小的边。但是C和E的重点都是F，即它们的终点相同，因此，将<C,E>加入最小生成树的话，会形成回路。这就是判断回路的方式。

普里姆（Prim）算法，也是求加权连通图的最小生成树的算法。

基本思想
对于图G而言，V是所有顶点的集合；现在，设置两个新的集合U和T，其中U用于存放G的最小生成树中的顶点，T存放G的最小生成树中的边。从所有的 uЄU ，vЄ(V-U)（V-U表示除去U的所有顶点）的边中选取权值最小的边（u，v），将顶点v加入U中，将边（u,v）加入集合T中，如此不断重复，直到U=V为止，最小生成树构造完毕，此时集合T中包含了最小生成树中的所有边。

以上图G4为例，来对普里姆进行演示(从第一个顶点A开始通过普里姆算法生成最小生成树)。

初始状态 ：V是所有顶点的集合，即V={A,B,C,D,E,F,G}；U和T都是空！
第1步 ：将顶点A加入到U中。
此时，U={A}。
第2步 ：将顶点B加入到U中。
上一步操作之后，U={A}, V-U={B,C,D,E,F,G}；因此，边(A,B)的权值最小。将顶点B添加到U中；此时，U={A,B}。
第3步 ：将顶点F加入到U中。
上一步操作之后，U={A,B}, V-U={C,D,E,F,G}；因此，边(B,F)的权值最小。将顶点F添加到U中；此时，U={A,B,F}。
第4步 ：将顶点E加入到U中。
上一步操作之后，U={A,B,F}, V-U={C,D,E,G}；因此，边(F,E)的权值最小。将顶点E添加到U中；此时，U={A,B,F,E}。
第5步 ：将顶点D加入到U中。
上一步操作之后，U={A,B,F,E}, V-U={C,D,G}；因此，边(E,D)的权值最小。将顶点D添加到U中；此时，U={A,B,F,E,D}。
第6步 ：将顶点C加入到U中。
上一步操作之后，U={A,B,F,E,D}, V-U={C,G}；因此，边(D,C)的权值最小。将顶点C添加到U中；此时，U={A,B,F,E,D,C}。
第7步 ：将顶点G加入到U中。
上一步操作之后，U={A,B,F,E,D,C}, V-U={G}；因此，边(F,G)的权值最小。将顶点G添加到U中；此时，U=V。

此时，最小生成树构造完成！它包括的顶点依次是：A B F E D C G。

F. 关于prim算法的时间复杂度

Prim算法的时间复杂度与网中的边数无关，适合于稠密图。

通过邻接矩阵图表示的简易实现中，找到所有最小权边共需O（V）的运行时间。使用简单的二叉堆与邻接表来表示的话，普里姆算法的运行时间则可缩减为O(ElogV)，其中E为连通图的边数，V为顶点数。

如果使用较为复杂的斐波那契堆，则可将运行时间进一步缩短为O(E+VlogV)，这在连通图足够密集时（当E满足Ω（VlogV）条件时），可较显着地提高运行速度。

(6)prim算法导论扩展阅读：

算法描述：

1、输入：一个加权连通图，其中顶点集合为V，边集合为E；

2、初始化：Vnew= {x}，其中x为集合V中的任一节点（起始点），Enew= {},为空；

3、重复下列操作，直到Vnew= V：

在集合E中选取权值最小的边<u, v>，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；

将v加入集合Vnew中，将<u, v>边加入集合Enew中；

4、输出：使用集合Vnew和Enew来描述所得到的最小生成树。

G. 哪些常见算法属于贪婪算法

显然KMP和FLOYD算法不是贪心算法，FLOYD算法是使用了类似于动态规划的思想，而KMP算法则是对串的前缀进行去处理得到所有可能出现匹配的位置从而减少不必要的位移。贪心算法可能还有很多，但是一般能用到的可能只有这些。在确定一个问题是否能用贪心来解决的时候应该线能够证明在这里使用贪心算法的正确性（详见算法导论）

H. 程序员如何学好算法

一.基本算法:

枚举. (poj1753,poj2965)

贪心(poj1328,poj2109,poj2586)

递归和分治法.

递推.

构造法.(poj3295)

模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996)

二.图算法:

图的深度优先遍历和广度优先遍历.

最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra)
(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)
最小生成树算法(prim,kruskal)
(poj1789,poj2485,poj1258,poj3026)
拓扑排序 (poj1094)

二分图的最大匹配 (匈牙利算法) (poj3041,poj3020)

最大流的增广路算法(KM算法). (poj1459,poj3436)

三.数据结构.

串 (poj1035,poj3080,poj1936)

排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299)

简单并查集的应用.

哈希表和二分查找等高效查找法(数的Hash,串的Hash)
(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)
哈夫曼树(poj3253)

堆

trie树(静态建树、动态建树) (poj2513)

四.简单搜索

深度优先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)

广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)

简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)

五.动态规划

背包问题. (poj1837,poj1276)

型如下表的简单DP(可参考lrj的书 page149):
E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533)
E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列) (poj3176,poj1080,poj1159)
C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题)
六.数学

组合数学:
1.加法原理和乘法原理.
2.排列组合.
3.递推关系.
(POJ3252,poj1850,poj1019,poj1942)
数论.
1.素数与整除问题
2.进制位.
3.同余模运算.
(poj2635, poj3292,poj1845,poj2115)
计算方法.
1.二分法求解单调函数相关知识.(poj3273,poj3258,poj1905,poj3122)
七.计算几何学.

几何公式.

叉积和点积的运用(如线段相交的判定,点到线段的距离等). (poj2031,poj1039)

多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交)
(poj1408,poj1584)
凸包. (poj2187,poj1113)

中级（校赛压轴及省赛中等难度）:
一.基本算法:

C++的标准模版库的应用. (poj3096,poj3007)

较为复杂的模拟题的训练(poj3393,poj1472,poj3371,poj1027,poj2706)

二.图算法:

差分约束系统的建立和求解. (poj1201,poj2983)

最小费用最大流(poj2516,poj2516,poj2195)

双连通分量(poj2942)

强连通分支及其缩点.(poj2186)

图的割边和割点(poj3352)

最小割模型、网络流规约(poj3308)

三.数据结构.

线段树. (poj2528,poj2828,poj2777,poj2886,poj2750)

静态二叉检索树. (poj2482,poj2352)

树状树组(poj1195,poj3321)

RMQ. (poj3264,poj3368)

并查集的高级应用. (poj1703,2492)

KMP算法. (poj1961,poj2406)

四.搜索

最优化剪枝和可行性剪枝

搜索的技巧和优化 (poj3411,poj1724)

记忆化搜索(poj3373,poj1691)

五.动态规划

较为复杂的动态规划(如动态规划解特别的旅行商TSP问题等)
(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)
记录状态的动态规划. (POJ3254,poj2411,poj1185)

树型动态规划(poj2057,poj1947,poj2486,poj3140)

六.数学

组合数学:
1.容斥原理.
2.抽屉原理.
3.置换群与Polya定理(poj1286,poj2409,poj3270,poj1026).
4.递推关系和母函数.
数学.
1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)
2.概率问题. (poj3071,poj3440)
3.GCD、扩展的欧几里德(中国剩余定理) (poj3101)
计算方法.
1.0/1分数规划. (poj2976)
2.三分法求解单峰(单谷)的极值.
3.矩阵法(poj3150,poj3422,poj3070)
4.迭代逼近(poj3301)
随机化算法(poj3318,poj2454)
杂题(poj1870,poj3296,poj3286,poj1095)
七.计算几何学.

坐标离散化.

扫描线算法(例如求矩形的面积和周长并,常和线段树或堆一起使用)
(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)
多边形的内核(半平面交)(poj3130,poj3335)

几何工具的综合应用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)

高级（regional中等难度）:
一.基本算法要求:

代码快速写成,精简但不失风格

(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)

保证正确性和高效性. poj3434

二.图算法:

度限制最小生成树和第K最短路. (poj1639)

最短路,最小生成树,二分图,最大流问题的相关理论(主要是模型建立和求解)
(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446
最优比率生成树. (poj2728)

最小树形图(poj3164)

次小生成树.

无向图、有向图的最小环

三.数据结构.

trie图的建立和应用. (poj2778)

LCA和RMQ问题(LCA(最近公共祖先问题) 有离线算法(并查集+dfs) 和 在线算法(RMQ+dfs)).(poj1330)
双端队列和它的应用(维护一个单调的队列,常常在动态规划中起到优化状态转移的目的). (poj2823)
左偏树(可合并堆).

后缀树(非常有用的数据结构,也是赛区考题的热点).(poj3415,poj3294)
四.搜索

较麻烦的搜索题目训练(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)

广搜的状态优化:利用M进制数存储状态、转化为串用hash表判重、按位压缩存储状态、双向广搜、A*算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)

深搜的优化:尽量用位运算、一定要加剪枝、函数参数尽可能少、层数不易过大、可以考虑双向搜索或者是轮换搜索、IDA*算法. (poj3131,poj2870,poj2286)

五.动态规划

需要用数据结构优化的动态规划.(poj2754,poj3378,poj3017)
四边形不等式理论.

较难的状态DP(poj3133)

六.数学

组合数学.
1.MoBius反演(poj2888,poj2154)
2.偏序关系理论.
博奕论.
1.极大极小过程(poj3317,poj1085)
2.Nim问题.
七.计算几何学.

半平面求交(poj3384,poj2540)

可视图的建立(poj2966)

点集最小圆覆盖.

对踵点(poj2079)

I. 什么是科研人员应该具有的能力，什么是工程师应该具有的能力

这几天，由于项目工作需要暂停，所以我就抽空开始学《算法导论》。认为这是一本很不错的书，不仅介绍了各种算法，而且给出了算法的由来（它的发明者是如何想到它的），以及效率的数学计算，当然还包含了算法的数学基础。我觉得这本书应该很耐看。它不向目前的一些国内的算法教材，只是罗列些经典算法，让你应用的时候可以想到去套这些算法。 昨天晚上和大师兄说了我正在学算法导论的事情。本以为大师兄会很支持，结果大师兄说，其实科研人员并不关心算法效率的问题，只有程序员或编程高手才会更关心效率的问题。 比如我曾经用C语言和MATLAB同时实现prim和kruskal算法，由于matlab语言对矩阵的特殊支持，matlab实现的算法显然比C语言高。 我们在本科多是工程上的训练。其目的就是：以后无论那门编程语言，只要学一个星期就能上手。。 可是当我在考研面试的时候，说道不同的编程语言对实现不同的算法有不同的效率时，在场的老师不屑一顾。当我能使用多种编程语言。又有人认为编程只是一种工具罢了，我充其量只不过是一个木匠。当人家问我数据库知识，我答出一小部分时，有人有任务我没有理论素养。。荒谬，真是荒谬。。。 我承认在本科，我们受到的训练都是工程上的训练，其目的是深刻的认识“编程语言只是工具，不是限制人思维的桎梏”。不学几种语言，怎么能深刻认识到这样一点，怎么能在研究生的学习中用一周就能基本入门一种特定的编程语言。当然，我们不是大专，也不是职业培养学校。我们虽然注重工程能力，但是并不要求一个学生在某一门程序语言上成为大牛（这是职业培训的目的。所以即便很多人是职业培训出来的，编程能力也可能比我们强）。我们的优势是在于在注重工程培养的同时，我们还有很多理论学习，报考计算机的各种理论，算法的各种理论。。。这些理论的学习是给在研究生期间做理论研究做初步准备的。 所以，我认为 一个软件领域的科研人员，在本科阶段应该是一个优秀的程序编写员。本科的偏工程背景，不应该认为和做理论研究是不相关的。

J. 求图的最短路径 c语言

prim算法或者kruskal算法啊