回溯方法 用来设计货箱装船、背包、最大完备子图、旅行商和电路板排列问题的求解算法。

寻找问题的解的一种可靠的方法是首先列出所有候选解，然后依次检查每一个，在检查完所有或部分候选解后，即可找到所需要的解。理论上，当候选解数量有限并且通过检查所有或部分候选解能够得到所需解时，上述方法是可行的。不过，在实际应用中，很少使用这种方法，因为候选解的数量通常都非常大（比如指数级，甚至是大数阶乘），即便采用最快的计算机也只能解决规模很小的问题。对候选解进行系统检查的方法有多种，其中回溯和分枝定界法是比较常用的两种方法。按照这两种方法对候选解进行系统检查通常会使问题的求解时间大大减少（无论对于最坏情形还是对于一般情形）。事实上，这些方法可以使我们避免对很大的候选解集合进行检查，同时能够保证算法运行结束时可以找到所需要的解。因此，这些方法通常能够用来求解规模很大的问题。 本章集中阐述回溯方法，这种方法被用来设计货箱装船、背包、最大完备子图、旅行商和电路板排列问题的求解算法。

分枝定界 使用树形结构来组织解空间（常用的树结构是子集树和排列树）

类似于回溯法，分枝定界法在搜索解空间时，也经常使用树形结构来组织解空间（常用的树结构是第1 6章所介绍的子集树和排列树）。然而与回溯法不同的是，回溯算法使用深度优先方法搜索树结构，而分枝定界一般用宽度优先或最小耗费方法来搜索这些树。本章与第1 6章所考察的应用完全相同，因此，可以很容易比较回溯法与分枝定界法的异同。相对而言，分枝定界算法的解空间比回溯法大得多，因此当内存容量有限时，回溯法成功的可能性更大。

动态规划 解决背包问题、图象压缩、矩阵乘法链、最短路径、无交叉子集和元件折叠等

动态规划是本书介绍的五种算法设计方法中难度最大的一种，它建立在最优原则的基础上。采用动态规划方法，可以优雅而高效地解决许多用贪婪算法或分而治之算法无法解决的问题。在介绍动态规划的原理之后，本章将分别考察动态规划方法在解决背包问题、图象压缩、矩阵乘法链、最短路径、无交叉子集和元件折叠等方面的应用。

分而治之算法 分而治之策略也可以运用到高效率的计算机算法的设计过程中。

君主和殖民者们所成功运用的分而治之策略也可以运用到高效率的计算机算法的设计过程中。本章将首先介绍怎样在算法设计领域应用这一古老的策略，然后将利用这一策略解决如下问题：最小最大问题、矩阵乘法、残缺棋盘、排序、选择和一个计算几何问题——找出二维空间中距离最近的两个点。 本章给出了用来分析分而治之算法复杂性的数学方法，并通过推导最小最大问题和排序问题的复杂性下限来证明分而治之算法对于求解这两种问题是最优的（因为算法的复杂性与下限一致）。

贪婪算法 解决最优化问题的一种基本方法

最优化问题是程序设计中一类非常重要的问题。每一个最优化问题都包含一组约束条件和一个优化函数，满足约束条件的问题求解方案称为问题的可行解，使优化函数取得最优值的可行解称为问题的最优解。贪婪算法是解决最优化问题的一种基本方法。它采用逐步构造最优解的思想，在问题求解的每一个阶段，都作出一个在一定标准下看上去最优的决策；决策一旦作出，就不可再更改。制定决策的依据称为贪婪准则。

PCB廠之生產排程以基因演算法架構

PCB（Printed Circuit Board）廠為電子產業的基礎，一般的電子產品大多數都含有PCB板在內部，如何大量的產出及縮短總完工時間，決定了工廠的利潤來源。一般來說PCB工廠為了要使流程時間縮短，通常都會從機台的平衡（Balance）、技術的改良及機台的更新來著手，往往忽略了排程（Scheduling）在生產規劃的重要性，而且PCB廠的工廠模式，屬於非等效平行機台（Unrelated Parallel Machines）為複雜的求解模式，如果以工廠人員手動的排程方法需要花費較多的時間且其解也不一定較佳，本研究以基因演算法（Genetic Algorithms）建構排程的求解模式，利用基因演算法的優點來解決複雜的排程問題。