求最短路径的Dijkstra算法： Dijkstra算法是一种解决最短路径问题的非常有效的算法，时间复杂度为 O(│V│2)，下面是一段精确的描述（本段引自MIT的课程主页，不翻译了，保持原作）中文描述一般的书上都会有：
1. Set i=0, S0= {u0=s}, L(u0)=0, and L(v)=infinity for v <> u0. If │V│ = 1 then stop, otherwise go to step 2.
2. For each v in V\Si, replace L(v) by min{L(v), L(ui)+dvui}. If L(v) is replaced, put a label (L(v), ui) on v.
3. Find a vertex v which minimizes {L(v): v in V\Si}, say ui+1.
4. Let Si+1 = Si cup {ui+1}.
5. Replace i by i+1. If i=│V?1 then stop, otherwise go to step 2.
6. Set i=0, S0= {u0=s}, L(u0)=0, and L(v)=infinity for v <> u0. If │V│ = 1 then stop, otherwise go to step 2.
7. For each v in V\Si, replace L(v) by min{L(v), L(ui)+dvui}. If L(v) is replaced, put a label (L(v), ui) on v.
8. Find a vertex v which minimizes {L(v): v in V\Si}, say ui+1.
9. Let Si+1 = Si cup {ui+1}.
10. Replace i by i+1. If i=│V│-1 then stop, otherwise go to step 2.
求二部图最大匹配（指派问题）的匈牙利算法： 谈匈牙利算法自然避不开Hall定理，即是：对于二部图G，存在一个匹配M，使得X的所有顶点关于M饱和的充要条件是：对于X的任意一个子集A，和A邻接的点集为T(A)，恒有： │T(A)│ >= │A│
匈牙利算法是基于Hall定理中充分性证明的思想，其基本步骤为：
1．任给初始匹配M；
2．若X已饱和则结束，否则进行第3步；
3．在X中找到一个非饱和顶点x0，作V1 ← {x0}, V2 ← Φ；
4．若T(V1) = V2则因为无法匹配而停止，否则任选一点y ∈T(V1)\V2；
5．若y已饱和则转6，否则做一条从x0 →y的可增广道路P，M←M⊕E(P)，转2；
6．由于y已饱和，所以M中有一条边(y,z)，作 V1 ← V1 ∪{z}, V2 ← V2 ∪ {y}， 转4；
关于求网络最大流和最小割的标号算法： 给定一个有向图G=(V,E)，把图中的边看作管道，每条边上有一个权值，表示该管道的流量上限。给定源点s和汇点t，现在假设在s处有一个水源，t处有一个蓄水池，问从s到t的最大水流量是多少。这就叫做网络流问题。用数学语言描述就是：
设G=(V,E)是一个流网络，设c(u, v)>＝0 表示从u到v的管道的流量上限。设s为源，t为汇。G的流是一个函数f: V×V →R，且满足下面三个特征：
1. 容量限制：对于所有的 u,v ∈ V, 要求f(u, v) <= c(u, v)
2. 斜对称性：对于所有的 u,v ∈ V, 要求f(u, v) = - f(v, u)
3. 流的会话：对于所有的 u ∈ V - {s, t}，要求∑ f(u, v) = 0；v∈V
f(u,v)称为从结点u到v的网络流，它可以为正也可以为负。流 f 的值定义为：
│f│ = ∑ f(s, v)
v∈V
即从源出发的所有流的总和。
最大流问题就是找出给定流网络的最大流。网络流问题可以归结为一类特殊的线性规划问题。
寻找最大流的基本方法是Ford-Fulkerson方法，该方法有多种实现，其基本思想是从某个可行流F出发，找到关于这个流的一个可改进路经P，然后沿着P调整F，对新的可行流试图寻找关于他的可改进路经，如此反复直至求得最大流。现在要找最小费用的最大流，可以证明，若F是流量为V(F)的流中费用最小者，而P是关于F的所有可改进路中费用最小的可改进路，则沿着P去调整F,得到的可行流F'一定是流量为V(F')的所有可行流中的最小费用流。这样，当F是最大流时候，他就是所要求的最小费用最大流。
注意到每条边的单位流量费用B(i,j)≥0，所以F=0必是流量为0的最小费用流，这样总可以
从F=0出发求出最小费用最大流。一般的，设已知F是流量V(F)的最小费用流，余下的问题就是如何去寻找关于F的最小费用可改进路。为此我们将原网络中的每条弧变成两条方向相反的弧：
1。前向弧，容量C和费用B不变，流量F为0；
2。后向弧，容量C为0，费用为-B，流量F为0；
每一个顶点上设置一个参数CT，表示源点至该顶点的通路上的费用和。如果我们得出一条关于F的最小费用可改进路时，则该路上的每一个顶点的CT值相对于其它可改进路来说是最小的。每一次寻找最小费用可改进路时前，源点的CT为0，其它顶点的CT为+∞。
设cost为流的运输费用，初始时由于F=0,则cost=0,我们每求出一条关于F的最小费用可改进路，则通过cost ← cost + ∑B(e)*d, （其中e∈P,d为P的可改进量）来累积流的运输费用
的增加量。显然，当求出最小费用最大流时，cost便成为最大流的运输费用了。
另外设置布尔变量break为最小费用可改进路的延伸标志，在搜索了网络中的每一个顶点后
，若break=true表示可改进路还可以延伸，还需要重新搜索网络中的顶点；否则说明最小费
用的可改进路已经找到或者最大流已经求出。
下面是算法的伪代码：
cost ← 0;
repeat
可改进路撤空；
设源点的CT值为0并进入可改进路；
repeat
break ← false;
for u ←1 to N do
begin
分析U出发的所有弧;
if (的流量可改进）and(源点至U有通路)and(U的CT值+的费用 < V的CT值) then
begin
break ← true;
V的CT值 ← U的CT值+的费用；
V进入可改进路经并为之标号；
end if
end for
until break=false
if 汇点已标号 then
begin
从汇点出发倒向修正可改进路的流量；
cost ← cost + ∑B(e)*d（其中e∈P,d为P的可改进量）；
end if
until 汇点未标号；
可见，上述的算法和求最大流的Edmonds-Karp标号算法几乎一样，因为这两种算法都使用宽度优先搜索来来寻找增广路径，所以复杂度也相同，都是O(VE)，其中V是节点数目，E是边数目。
其他的就不详述了，大家感兴趣的可以查阅TAOCP或者是算法导论的相关内容。
贪心法与拟阵： 贪心法是求解关于独立系统组合优化问题的一种简单算法，求最小生成树的Kruskal算法就是一种贪心算法。但是贪心法并不总能找到最优独立集。贪心法能求得最优独立集的充分必要条件是L为一个拟阵。事实上，求最大生成树是关于拟阵的组合优化问题，而二部图的所有匹配构成的独立系统U不是拟阵。
贪心法的基本思路是：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。
该算法存在问题：
1. 不能保证求得的最后解是最佳的；
2. 不能用来求最大或最小解问题；
3. 只能求满足某些约束条件的可行解的范围。
实现该算法的过程：
从问题的某一初始解出发；
while 能朝给定总目标前进一步 do
求出可行解的一个解元素；
由所有解元素组合成问题的一个可行解；
穷举搜索：
组合算法要解决的问题只有有限种可能，在没有跟好算法时总可以用穷举搜索的办法解决，即逐个的检查所有可能的情况。可以想象，情况较多时这种方法极为费时。实际上并不需要机械的检查每一种情况，常常是可以提前判断出某些情况不可能取到最优解，从而可以提前舍弃这些情况。这样也是隐含的检查了所有可能的情况，既减少了搜索量，又保证了不漏掉最优解。这方面怒火之炮写过文章，我认为没必要敖述了。
分支限界法：
这是一种用于求解组合优化问题的排除非解的搜索算法。类似于回溯法，分枝定界法在搜索解空间时，也经常使用树形结构来组织解空间。然而与回溯法不同的是，回溯算法使用深度优先方法搜索树结构，而分枝定界一般用宽度优先或最小耗费方法来搜索这些树。因此，可以很容易比较回溯法与分枝定界法的异同。相对而言，分枝定界算法的解空间比回溯法大得多，因此当内存容量有限时，回溯法成功的可能性更大。
算法思想：分枝定界（branch and bound）是另一种系统地搜索解空间的方法，它与回溯法的主要区别在于对E-节点的扩充方式。每个活节点有且仅有一次机会变成E-节点。当一个节点变为E-节点时，则生成从该节点移动一步即可到达的所有新节点。在生成的节点中，抛弃那些不可能导出（最优）可行解的节点，其余节点加入活节点表，然后从表中选择一个节点作为下一个E-节点。从活节点表中取出所选择的节点并进行扩充，直到找到解或活动表为空，扩充过程才结束。
有两种常用的方法可用来选择下一个E-节点（虽然也可能存在其他的方法）：
1) 先进先出（F I F O） 即从活节点表中取出节点的顺序与加入节点的顺序相同，因此活
节点表的性质与队列相同。
2) 最小耗费或最大收益法在这种模式中，每个节点都有一个对应的耗费或收益。如果查找
一个具有最小耗费的解，则活节点表可用最小堆来建立，下一个E-节点就是具有最小耗费
的活节点；如果希望搜索一个具有最大收益的解，则可用最大堆来构造活节点表，下一个
E-节点是具有最大收益的活节点。
动态规划：
动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision
process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究
多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。
一般来说，只要问题可以划分成规模更小的子问题，并且原问题的最优解中包含了
子问题的最优解（即满足最优子化原理），则可以考虑用动态规划解决。动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。
由此可知，动态规划法与分治法和贪心法类似，它们都是将问题实例归纳为更小的、相似的子问题，并通过求解子问题产生一个全局最优解。其中贪心法的当前选择可能要依赖已经作出的所有选择，但不依赖于有待于做出的选择和子问题。因此贪心法自顶向下，一步一步地作出贪心选择；而分治法中的各个子问题是独立的 (即不包含公共的子子问题)，因此一旦递归地求出各子问题的解后，便可自下而上地将子问题的解合并成问题的解。但不足的是，如果当前选择可能要依赖子问题的解时，则难以通过局部的贪心策略达到全局最优解；如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题。解决上述问题的办法是利用动态规划。该方法主要应用于最优化问题，这类问题会有多种可能的解，每个解都有一个值，而动态规划找出其中最优(最大或最小)值的解。若存在若干个取最优值的解的话，它只取其中的一个。在求解过程中，该方法也是通过求解局部子问题的解达到全局最优解，但与分治法和贪心法不同的是，动态规划允许这些子问题不独立，(亦即各子问题可包含公共的子子问题)也允许其通过自身子问题的解作出选择，该方法对每一个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。
因此，动态规划法所针对的问题有一个显著的特征，即它所对应的子问题树中的子问题呈现大量的重复。动态规划法的关键就在于，对于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，让以后再遇到时直接引用，不必重新求解。
设计一个标准的动态规划算法，通常可按以下几个步骤进行：
1．划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意这若干
个阶段一定要是有序的或者是可排序的（即无后向性），否则问题就无法用动态规
划求解。
2．选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示
出来。当然，状态的选择要满足无后效性。
确定决策并写出状态转移方程：之所以把这两步放在一起，是因为决策和状态转移
有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。
所以，如果我们确定了决策，状态转移方程也就写出来了。但事实上，我们常常是
反过来做，根据相邻两段的各状态之间的关系来确定决策。
3．写出规划方程（包括边界条件）：动态规划的基本方程是规划方程的通用形式
化表达式。一般说来，只要阶段、状态、决策和状态转移确定了，这一步还是比较
简单的。 动态规划的主要难点在于理论上的设计，一旦设计完成，实现部分就会非常简单。
分治法：
对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解
决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。 任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算。n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可，…。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
如果原问题可分割成k个子问题，1 < k ≤ n ，且这些子问题都可解，并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。
其基本步骤是：
分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；
合并：将各个子问题的解合并为原问题的解。
它的一般的算法设计模式如下：
Divide-and-Conquer(P)
1．if │P│≤n0
2．then return( ADHOC(P) )
3．将P分解为较小的子问题 P1 ,P2 ,...,Pk
4．for i←1 to k
5．do yi ← Divide-and-Conquer(Pi) △ 递归解决Pi
6．T ← MERGE(y1,y2,...,yk) △ 合并子问题
7．return(T)
其中│P│表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题已
容易直接解出，不必再继续分解。ADHOC(P)是该分治法中的基本子算法，用于直接
解小规模的问题P。因此，当P的规模不超过n0时，直接用算法ADHOC(P)求解。算法
MERGE(y1,y2,...,yk)是该分治法中的合并子算法，用于将P的子问题P1 ,P2 ,...
,Pk的相应的解y1,y2,...,yk合并为P的解。
根据分治法的分割原则，原问题应该分为多少个子问题才较适宜？各个子问题的规
模应该怎样才为适当？这些问题很难予以肯定的回答。但人们从大量实践中发现，
在用分治法设计算法时，最好使子问题的规模大致相同。换句话说，将一个问题分
成大小相等的k个子问题的处理方法是行之有效的。许多问题可以取k=2。这种使子
问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是
比子问题规模不等的做法要好。
分治法的合并步骤是算法的关键所在。有些问题的合并方法比较明显，有些问题合并方法比较复杂，或者是有多种合并方案，或者是合并方案不明显，究竟应该怎样合并，没有统一的模式，需要具体问题具体分析。
其他的一些经典的算法，如快速傅里叶变换，大家都非常熟悉，这里就不再涉及。如果想深入学习不妨参考San Diego 州立大学的相关课程主页
http://www.eli.sdsu.edu/courses/fall95/cs660/notes/
组合算法的设计是一门艺术，需要高度的技巧和灵感。算法分析的任务是分析算法的优劣，算法分析的任务是分析算法的优劣，主要是讨论算法的时间复杂性和空间复杂性。它的理论基础是组合分析，包括计数和枚举。计算复杂性理论，特别是NP完全性理论，与组合算法是紧密相关的。NP完全性概念的提出，正是为了刻画包括旅行商问题、图着色问题、图着色问题、整数规划等一大批组合问题的计算难度。计算复杂性理论研究算法在时间和空间限制下的能力以及问题的难度，使组合算法的研究有了更加清晰的框架，将组合算法的研究提高到一个新的水平。
本文地址：http://com.8s8s.com/it/it34120.htm