资源简介

(共62张PPT)
第7章 经典算法
约瑟夫问题
球钟问题
八皇后问题
背包问题
地图着色问题
旅行商问题
约瑟夫问题
球钟问题
八皇后问题
7.2
7.3
7.1
点击查看本小节知识架构
点击查看本小节知识架构
点击查看本小节知识架构
背包问题
7.4
点击查看本小节知识架构
地图着色问题
7.5
点击查看本小节知识架构
旅行商问题
7.6
点击查看本小节知识架构
学习目标
掌握
熟练
掌握
掌握各种经典算法的设计思想与操作原理
1
2
熟练操作算法中涉及的数据结构
3
掌握具体算法实例的代码编写方法
本章将主要介绍一些经典算法的实例。经典算法涉及到很多解决问题的方法，如回溯法、贪心算法、分治法、动态规划法、分支界限法等。前面的章节中，本书已经介绍了利用贪心算法与分治法解决问题的实例，如赫夫曼树、快速排序等。本章将主要介绍使用回溯法与动态规划法解决问题的实例，其中也涉及一些数据结构的操作，望读者理解算法的设计思想，熟练编写操作代码。
7.1 约瑟夫问题
7.1.1
算法概述
返回目录
7.1.2
算法实现
7.1.1 算法概述
约瑟夫问题又称为约瑟夫斯置换，是一个在计算机科学和数学中出现的问题。在计算机编程中，类似问题又可以称为约瑟夫环。约瑟夫问题有很多版本，其一般的形式如下所示。
假设编号分别为(1,2,…n)的 n 个人围坐成一圈。其中，约定序号为 k(1≤k≤n)的人从 1 开始报数，数到 m的那个人出列，然后下一位继续从 1 开始报数，数到 m的那个人再次出列，以此类推，直到所有人出列为止。
如图所示，设 k 等于 3，n 等于 8，m 等于 4，则出列的序列为 6–2–7–4–3–5–1–8。
7.1.2 算法实现
1．链表实现
由 7.1.1 节中对约瑟夫问题的简单描述可知，每个待出列的人都可以被视为一个数据元素，这些元素形成一个封闭环。因此，可以使用单向循环链表来解决约瑟夫问题。
使用单向循环链表解决约瑟夫问题的代码参考教材7.1.2节。
例中，joseph()函数将数据元素个数设定为 8，然后从第 3 个元素开始计数，每当计数到第 4个元素时，将该元素删除。
Joseph()函数首先采用循环的方式对单向循环链表进行遍历，然后寻找需要删除的元素的上一个元素与下一个元素，最后将这两个元素进行连接，即可实现指定元素的删除。每一次删除元素后，单向循环链表都会重新连接为一个新的环，因此无须考虑环中数据元素减少的问题。程序运行结果如下所示。
由运行结果可以看出，按照约瑟夫问题的规则，输出数据元素的顺序为 6–2–7–4–3–5–1–8。
7.1.2 算法实现
2．循环实现
在单向循环链表中，每删除一个数据元素（结点）后，链表都会重新形成新的循环。因此，无论第几次删除数据元素，其删除过程都与第一次相同，即计数到 k 时，删除对应数据。而如果采用数学的思想处理约瑟夫问题，就需要考虑删除数据产生的空位对后续计数的影响。例如，假设当前环中的数据元素为 10 个，从第 0 个元素开始，每次计数到 4 时，将对应的数据元素删除，如图所示。
7.1.2 算法实现
对环中的数据元素进行操作，第一次删除的是编号为 3 的元素，第二次删除的是编号为 7 的元素（以元素 4 为起始点进行计数）。由此推理，第三次删除的是编号为 1 的元素。当进行第四次删除操作时，编号为 3 的元素已经被删除（环断开），此时需要删除的是编号为 6 的元素，而非编号为 5的元素，可见数据删除产生的空洞对计数产生了影响。
为了解决上述问题，可以将每一次删除数据元素后的环看作成一个新环，这样就不会产生数学运算上的不连续，如图所示。
7.1.2 算法实现
图中，第一次删除的是编号为 3 的元素，元素 3 删除后，元素 2 与元素 4 的连接断开，形成空洞。因此，可以将删除元素后的环重新看作一个新环，即将被删除元素的下一位元素重新编号为 0，以此类推，这样形成的新环在数学运算上就是连续的，不会对后续删除元素产生影响。
由图可知，实际删除的是编号为 3 的元素，而在新环中该元素对应的编号为 9。因此，当前需要解决的问题是新环中被删除元素的编号与旧环中的编号如何一一对应。
从图中可以看出，新环中的元素的编号是由旧环中的元素整体移动 k（k 为计数值，为 4）个单位得来的。由此可以推理出公式 old_num=(new_num+k)%old_sum，其中，old_num 表示旧环中被删除元素的
编号，new_num 表示新环中被删除元素的编号，k 表示计数值，old_sum 表示旧环中元素的总个数。例如，图中需要删除的元素的编号为 3，而在新环中对应的编号为 9，k 为 4，旧环中元素总数为 10（删除元素之前环中元素的总数），即 3=(9+4)%10。
7.1.2 算法实现
按照上述操作方式，在每一次删除元素后，都重新构造新环，如图所示。
7.1.2 算法实现
图中，每一次删除元素后，都需要重新构造新环，即从被删除元素的下一位开始重新编号。每一个环相对于上一个环来说，都是一个新环。
综上所述，根据构造的新环与推理公式，即可推导出原始的环中每一次删除的元素对应的编号。例如，计算图中的原始环第五次删除的元素的编号，只需要找到第五次删除元素后构造的新环，然后根据推理公式进行推导即可，如图所示（截取自图 7.4）。
7.1.2 算法实现
第五次删除元素后构造的新环在数学计算上是连续的，即序列顺序为 0–1–2–3–4，得出第五次删除的元素的编号为 5（在新环中的编号，非原始环中的编号）。结合推理公式可知，(5+4)%6=3，即编号为 5 的元素对应上一个新环（第四次删除元素后构造的新环）中编号为 3 的元素，如图所示（截取自图 7.4）。
将元素 3 加入推理公式可得出，(3+4)%7=0，即编号为 3 的元素对应上一个新环（第三次删除元素后构造的新环）中编号为 0 的元素，如图所示（截取自图 7.4）。
7.1.2 算法实现
将元素 0 加入推理公式可得出，(0+4)%8=4，即编号为 0 的元素对应上一个新环（第二次删除元素后构造的新环）中编号为 4 的元素，如图所示（截取自图 7.4）。
将元素 4 加入推理公式可得出，(4+4)%9=8，即编号为 4 的元素对应上一个新环（第一次删除元素后构造的新环）中编号为 8 的元素，如图所示（截取自图 7.4）。
7.1.2 算法实现
将元素 8 加入推理公式可得出，(8+4)%10=2，即编号为 8 的元素对应上一个新环（原始环）中编号为 2 的元素，如图 所示（截取自图 7.4）。
经过一系列推导可知，原始环中第五次删除的元素的编号为 2。
总结上述过程，可以得到以下结论。
（1）如果需要确定原始环中第 n 次删除的元素，只需要找到第 n 次构造的新环中删除的元素的编号，将其代入推理公式执行 n 次，即可确定原始环中删除的元素。
（2）第 n 次构造的新环中删除的元素的编号等于元素的总个数减去 n，例如，图 7.4 中，第七次删除的元素在新环中的编号为 3(3=10－7)。
7.1.2 算法实现
将上述结论与图 7.4 结合可以得出以下结果（元素总数 sum 为 10，计数值 k 为 4）。
（1）第一次删除的元素的编号为：(sum－1+k)%sum=(10－1+4)%10=3。
（2）第二次删除的元素的编号为：(sum－2+k)%(sum－1)=(8+4)%9=3，(3+k)%sum=(3+4)%10=7。
（3）第三次删除的元素的编号为：(sum－3+k)%(sum－2)=(7+4)%8=3，(3+k)%(sum－1)=(3+4)%9=7，(7+k)%sum=(7+4)%10=1。
（4）其他轮次的删除操作可以此类推。
根据上述求值操作可知，求第 n 次删除元素的编号，需要执行 n 次推理公式，且每一次的计算结果都将代入下一轮次的公式中继续运算。同时可以看出，算式的一般形式为(sum－1+k)%sum。
7.1.2 算法实现
将推导得出的结论转换为程序，如例所示。
7.1.2 算法实现
7.1.2 算法实现
由例可见，通过数学的思想同样可以解决约瑟夫问题。joseph()函数通过获取新环中的元素对应的编号以及循环执行推理公式，确定原始环中删除的元素。程序运行结果如下所示。
由运行结果可知，按顺序删除的元素为 8–24–32–5–14–16–23–23–12–7，其对应的编号（在数组中的下标值）为 3–7–1–6–2–9–8–0–5–4。
7.1.2 算法实现
3．递归实现
采用递归的编程方式同样可以解决约瑟夫问题，递归操作与循环操作类似，都是循环执行推理公式。不同的是，循环实现是直接逐级计算被删除元素在新环中对应的编号，而递归实现是先按轮次向下调用，然后逐级计算被删除元素在新环中对应的编号。采用递归的方式解决约瑟夫问题，如例所示。
7.1.2 算法实现
例采用 joseph()函数嵌套的方式实现递归操作。程序运行结果如下所示。
由运行结果可知，按顺序删除的元素为 3–7–1–6–2–9–8–0–5–4。
7.1.2 算法实现
假设当前原始环中的元素总数为 10，计数值为 4，计算第四次删除的元素的编号，结合例的程序推理该递归操作的过程，可知递归实现的操作原理如图所示。
7.1.2 算法实现
循环实现则是直接将编号代入公式计算，其操作原理如图所示。
对比图可知，循环与递归这两种实现方式本质上没有区别。
7.2 球钟问题
7.2.1
算法概述
返回目录
7.2.2
算法实现
7.2.1 算法概述
球钟问题是一个需要借助于栈和队列来解决的问题。球钟是一种利用球的移动来记录时间的简单装置。它有 3 个可以容纳若干个球的指示器：小时指示器、五分钟指示器、分钟指示器。例如，分钟指示器中有 3 个球，五分钟指示器中有 4 个球，小时指示器中有 8 个球，则表示当前时间为 8点 23 分。
球钟问题的工作原理如下。
（1）每过一分钟，球钟就会从球队列的队首取出一个球放入分钟指示器（分钟指示器中最多可容纳 4 个球）。当放入第 5 个球时，在分钟指示器中的 4 个球就会按照它们被放入时的相反顺序加入球队列的队尾，第 5 个球则会进入五分钟指示器。
（2）五分钟指示器最多可放 11 个球，当放入第 12 个球时，在五分钟指示器中的 11 个球就会按照它们被放入时的相反顺序加入球队列的队尾，第12 个球则会进入小时指示器。
（3）小时指示器最多可放 11 个球，当小时指示器放入第 12 个球时，原来的 11 个球就会按照它们被放入时的相反顺序加入球队列的队尾，然后第 12个球也加入队尾。此时三个指示器均为空，回到初始状态。
7.2.1 算法概述
综上所述，球钟表示的时间范围是 00:00 到11:59。其工作原理如图所示。
7.2.1 算法概述
由图可以看出，球队列中的球遵循先进先出的原则，可以使用数据结构中的队列来实现。而指示器中的球，放入与移出的顺序刚好相反，遵循后进先出的原则，可以使用数据结构中的栈来实现。因此，解决球钟问题需要使用 1 个队列与 3 个栈，且完成一轮计时需要 27（11+11+4+1）个球。
7.2.2 算法实现
由节的分析可知，球钟问题需要借助队列与栈来解决，因此，下面将展示使用链式队列实现球队列和使用顺序栈实现指示器。
自定义头文件实现链式队列的数据定义以及基本操作，示例代码参考教材7.2.2节。
例在头文件中实现了链式队列的创建、入队、出队以及队列的判断。
自定义头文件实现顺序栈的数据定义以及基本操作，示例代码参考教材7.2.2节。
例在头文件中实现了顺序栈的创建、入栈、出栈以及输出栈中的数据。
测试程序需要借助于例 7-4 与例 7-5 中的函数接口，示例代码参考教材7.2.2节。
例中，程序利用球钟的计时规则，计算从球出队开始到球全部回到队列（同时保证球在队列中的顺序与初始出队时一致）的时间。程序运行结果如下。
由运行结果可知，按照球钟的计时规则，从球开始出队到全部入队（入队后球的顺序与初始出
队时一致）的时间为 23 天。
7.3 八皇后问题
7.3.1
算法概述
返回目录
7.3.2
算法实现
7.3.1 算法概述
八皇后问题是一个利用回溯法的典型案例，该问题是由国际西洋棋棋手马克斯·贝瑟尔于 1848 年提出的。其具体形式为：在 8 格×8 格的国际象棋棋盘上摆放八个皇后，使其不能互相攻击（即任意两个皇后都不能处于同一行、同一列或同一斜线上），计算有多少种摆法。
棋盘中的任意两个皇后都不在同一行、同一列或同一斜线上，满足摆放规则，如图所示。
7.3.1 算法概述
由图可知，第二个皇后只能摆放在第二行的 A 位置或 B 位置上，按照顺序，先将其摆放在A 位置，如图 所示。
解决八皇后问题的方法有很多，本节将主要介绍通过回溯法解决这一问题。为了便于理解，可以将皇后数量及棋盘变小进行分析。
假设当前皇后数量为 4，棋盘大小为 4 格×4 格，由于每一个皇后只能占单独的一行与一列，因此第一个皇后可以摆放在第一行的第一列上，如图所示。
7.3.1 算法概述
由图可知，重新将第二个皇后摆放完成后，第三个皇后只能摆放在第三行的 C 位置上，而C 位置与 D 位置在同一斜线上，因此第四个皇后将无法摆放。再次回溯到上一步（第一次摆放皇后时），重新摆放第一个皇后，将其摆放到第一行的第二列上，如图所示。
由图可知，在第二个皇后摆放完成后，第三个皇后只能摆放在第四行的 C 位置上，而棋盘中已经没有位置可以摆放第四个皇后。此时就需要回溯到上一步，重新摆放第二个皇后。将第二个皇后摆放到图 7.15 所示棋盘的 B 位置上，如图所示。
7.3.1 算法概述
由图可知，最后一个皇后可以摆放在最后一行的 C 位置上。摆放结果如图所示。
由图可知，重新将第一个皇后摆放完成后，第二个皇后可以摆放在第二行的 A 位置上，第三个皇后可以摆放在第三行的 B 位置上，如图所示。
由图可知，棋盘中任意两个皇后都不在同一行、同一列或同一斜线上，满足指定的规则。
7.3.2 算法实现
由 7.3.1 节算法分析可知，在棋盘中摆放皇后，需要考虑下一个皇后是否有位置可以摆放，如果没有，则返回到上一步，重新摆放皇后。因此，在设计代码时，需要采用回溯的思想，示例代码参考教材7.3.2节。
例中，Check()函数用来检测皇后是否可以摆放，EightQueen()函数通过嵌套的形式实现递归操作（函数执行一次操作棋盘中的一行），并通过循环与 Check()函数结合，确定皇后在一行中的摆放位置（即某一列上）。如果一行中的所有位置都不适合摆放皇后，则返回到上一步（上一行），重新摆放上一个皇后。程序运行结果如下。
由运行结果可知，八皇后问题的解法共有 92 种。
7.4 背包问题
7.4.1
算法概述
返回目录
7.4.2
算法实现
7.4.1 算法概述
背包问题可以描述为：假设有 n 个物品与一个背包，物品 i 的质量为 W i ，价值为 V i ，背包的最大载重为 c，求如何装载可使背包中物品的总价值最大。本次只讨论“0-1”的情况，即物品不可拆分，只能装入或不装入，且不能将同一个物品装入多次。
解决背包问题的方法有很多，如回溯法、动态规划法、分支界限法等。本节将主要介绍通过回溯法解决背包问题，即采用探测的方式。接下来通过一个具体的示例展示探测的过程。
例如，一个背包只能载重 8kg，已知荔枝 4kg 的价格为 45 元，樱桃 5kg 的价格为 57 元，香蕉1kg 的价格为 11 元，草莓 2kg 的价格为 22.5 元，菠萝 6kg 的价格为 67 元，如表所示。
7.4.1 算法概述
对表中的物品进行试探，具体操作步骤如下（略去单位）。
（1）假设先将荔枝放入背包，此时背包中物品的总价值为 45，总重量为 4（背包的最大载重为 8），当前背包问题的最优解为 45（暂时）。
（2）将樱桃放入背包，此时背包总重量为 9，大于背包的最大载重，不满足规则，因此将樱桃取出并进行判断。判断当前背包中物品总价值加未探测物品的总价值是否大于最优解（荔枝的价值与其他物品的总价值之和大于荔枝的价值），判断结果为需要继续探测。
（3）将香蕉放入背包，此时背包的总重量为 5，背包中物品的总价值为 56，背包总重量小于背包最大载重，可以继续探测。当前背包问题的最优解为 56。
（4）将草莓放入背包，此时背包的总重量为 7，背包中物品的总价值为 78.5（最优解为 78.5），背包总重量小于背包最大载重，可以继续探测。
（5）将菠萝放入背包，此时背包的总重量为 13，大于背包的最大载重，不满足规则，因此将菠萝取出。至此一轮探测结束，保存当前最优解（最优解为 78.5）。
7.4.1 算法概述
（6）回溯到上一步，将草莓取出，当前背包的总重量为 5，背包中物品的总价值为 56，判断当前背包中物品总价值加未探测物品的总价值是否大于最优解（当前背包中物品的总价值为 56，未探测物品为菠萝，二者之和为 123，大于最优解 78.5），判断结果为需要继续探测。
（7）将菠萝放入背包，此时背包的总重量为 11，大于背包的最大载重，不满足规则，因此再次将菠萝取出。
（8）回溯到上一步，将香蕉取出，再放入草莓……
7.4.1 算法概述
上述操作类似于穷举法，即列出所有情况，再进行比较。不同的是，背包问题不需要探测所有结果，如果探测到某一物品时，发现当前重量已经超过最大载重，则无须再探测后续物品；如果当前背包中物品的总价值加上未探测物品的总价值小于目前的最优解，同样也无须再探测后续物品。这种探测方式采用了解空间树的思想，并按照深度优先搜索的方式进行探测，如图 所示。
7.4.1 算法概述
假设当前有 3 个物品 x[1]、x[2]、x[3]，树中结点的左孩子表示选取，右孩子表示不选取，则选取物品的方案有2 3 =8 种（n 个物品的选取方案有 2 n 种）。具体分析如下。
（1）如果第一个物品不选取，第二个物品不选取，第三个物品也不选取，则为方案 0，此时得到一个暂时的最优解。
（2）回溯到上一步，选取第三个物品，则为方案 1。比较当前值与最优解，以较大值作为新的最优解。
（3）回溯到探测第二个物品时，选取第二个物品，不选取第三个物品，则为方案 2。同样，比较当前值与最优解，以较大值作为新的最优解。
（3）回溯到上一步，选取第三个物品，则为方案 3。再次比较当前值与最优解，以较大值作为新的最优解。
（4）以此类推，通过不断递归和回溯，最终确定最优解。
采用回溯法处理背包问题时，处理的数据量不宜过大，如果有 n 个数据对象，则对应的解决方案有 2 n 种。随着 n 的增长，其解的数量将以 2 n 级增长。
7.4.2 算法实现
采用回溯法解决背包问题，示例代码参考教材7.4.2节。
例中，Optimal_Solution()函数用来求背包问题的最优解，函数通过嵌套的方式实现递归探测下一个物品，如果当前探测的物品加入背包后，背包总重量超过最大载重，则直接跳过当前探测的物品。程序运行结果如下所示。
7.4.2 算法实现
由运行结果可知，最优解的物品组合为物品 1、物品 2、物品 5，对应的重量分别为 2kg、2kg、5kg，价值分别为 6 元、3 元、6 元，最终得到的最优解为 15 元。
7.5 地图着色问题
7.5.1
算法概述
返回目录
7.5.2
算法实现
7.5.1 算法概述
地图着色问题是著名的 NP 完全问题（多项式复杂程度的非确定性问题）之一。该问题可以详细
分为以下 3 种模式。
（1）图的着色问题，即给定无向连通图 G 与 n 种不同的颜色，计算所有不同的着色方法，使得任意相邻的 2 个顶点具有不同的颜色。
（2）图的着色判定问题，即给定无向连通图 G 与 n 种不同的颜色，使用这些颜色为图 G 中的各顶点着色，判断是否存在一着色法使图 G 中任意相邻顶点具有不同的颜色。
（3）图的着色优化问题，即计算无向联通图 G 中，至少需要多少种颜色使得任意相邻的 2 个顶点具有不同的颜色。
7.5.1 算法概述
如图所示，创建一个虚拟的地图，并将其转换为一个无向连通图（不共享一条边的块不记为相邻）。
7.5.1 算法概述
由图可知，要解决地图着色问题，可以将复杂的地图转换为数据结构中的无向连通图，然后设置顶点之间的关系来表示地图中的区域是否相邻。例如，设置顶点 A 与顶点 B 之间的权值为 1，顶点 A 与顶点 E 之间的权值为 0，表示区域 A 与区域 B 相邻，区域 A 与区域 E 不相邻。
7.5.2 算法实现
下面通过代码展示地图着色问题以及地图着色优化问题。
1．地图着色问题
地图着色问题的解决方法与八皇后问题、背包问题类似，都是利用深度优先搜索的方式进行递归并回溯，找到所有问题的子集。具体代码参考教材7.5.2节。
例中，程序使用邻接矩阵的方式（二维数组）实现无向连通图中顶点的存储，函数 dfs()通过遍历二维数组来计算着色的方案数量，并通过函数嵌套的方式递归调用，递归的目的是探测每一个顶点与其他顶点的关系。程序通过回溯的方式对已着色的顶点重新分配颜色，以便探测出所有可行的配色方案。dfs()函数通过判断顶点是否相邻以及颜色是否被使用决定是否分配新的颜色。
7.5.2 算法实现
程序运行结果如下所示（以图 7.22 中的无向连通图作为测试对象，二维数组的起始下标为 1）。
由运行结果可知，图中的虚拟地图在只有 3 种颜色的情况下，有 18 种配色方案。
7.5.2 算法实现
2．地图着色优化问题
地图着色优化问题即计算地图的最小色数，该问题只需要求出可行着色方案中的一种，要求使用的颜色数量最少，不需要考虑顶点之间的颜色调换。具体代码参考教材7.5.2节。
例中，graph_input()函数用来读取终端输入的顶点与边以及二者之间的关系；map_overlay()函数用来实现着色，并通过函数嵌套完成递归调用，每一次调用的目的是对下一个顶点进行着色；colorsame()函数用来判断顶点之间是否相邻以及颜色是否被使用；output()函数输出着色方案，并通过编号表示颜色种类。
7.5.2 算法实现
程序运行结果如下所示（以图 7.22 作为测试对象）。
7.5.2 算法实现
由运行结果可以看出，图中的虚拟地图只需要 3 种颜色即可完成着色，其中顶点 A、顶点 E、顶点 G 使用相同的颜色，顶点 B、顶点 D、顶点 F 使用相同的颜色，顶点 C 单独使用一种颜色，如图所示。
图所示的着色方案只是可行方案中的一种。
7.6 旅行商问题
7.6.1
算法概述
返回目录
7.6.2
算法实现
7.6.1 算法概述
旅行商问题是一个经典的组合优化问题。具体的问题描述为：一个推销员必须访问 n 个城市，且所有城市只访问一次，然后回到起始的城市（城市与城市之间有旅行费用，且推销员希望旅行费用之和最小）。也可以换一种描述：给定一系列城市和每对城市之间的距离，求访问每一座城市一次并回到起始城市的最短回路。
解决旅行商问题的方法有很多，如贪心算法、动态规划法、分支界限法、遗传算法、蚁群算法等。本节将主要介绍采用动态规划法实现旅行商问题，并通过具体的示例展示动态规划法的分析过程。
创建一个有向图，表示城市及城市之间的连通关系，如图所示。
7.6.1 算法概述
根据图创建一个邻接矩阵，表示顶点与顶点之间的关系，如图所示。
（1）从城市 0 出发，经过城市 1，再从城市 1 出发，经过[2,3]这两个城市，然后回到城市 0。
（2）从城市 0 出发，经过城市 2，再从城市 2 出发，经过[1,3]这两个城市，然后回到城市 0。
（3）从城市 0 出发，经过城市 3，再从城市 3 出发，经过[1,2]这两个城市，然后回到城市 0。
由上述描述可知，一个大的需求可以分为三个小问题，并且需要求得这三个小问题的最优解。因此，这个需求具有最优子集，可以用动态规划来实现。
7.6.1 算法概述
设置一个二维的动态规划表 dp，定义符号{1,2,3}表示经过[1,2,3]这三个城市，然后回到城市 0。因此上述需求可以用动态规划表表示为 dp[0][{1,2,3}]，如果用 C 表示两个城市之间的旅行费用，则dp[0][{1,2,3}]=min{C 01 +dp[1][{2,3}]，C 02 +dp[2][{1,3}]，C 03 +dp[3][{1,2}]}。其中，min 表示求最小值，C 01 表示从城市 0 到城市 1 的旅行费用，dp[1][{2,3}]表示从城市 1 出发，经过城市[2,3]，然后回到城市 0，其他以此类推。按照上述表示方法，继续推导可以得出，dp[1][{2,3}]=min{C 12 +dp[2][{3}]，C 13 +dp[3][{2}]}，dp[2][{3}]表示从城市 2 出发，经过城市 3，然后回到城市 0。再次进行推导，dp[2][{3}]=C 23 +dp[3][{}]，dp[3][{}]指的是从城市 3 出发，不经过任何城市，回到城市 0，即 C 30 。
将城市编号设置为二进制数，城市 1 为 001，城市 2 为 010，城市 3 为 100（假设城市编号为 m，则其二进制数对应的 m 位为 1，计算的方式为 1 (m－1)），以此类推，则上述动态规划表达式中，{1,2,3}可以表示为 111，转换成十进制数为 7，{2,3}可以表示 110，转换成十进制数为 6。
7.6.1 算法概述
例如，dp[0][{1,2,3}]=dp[0][7]，dp[1][{2,3}]=dp[1][6]。由此得出整个需求对应的动态规划表，如表所示。（假设城市有 n 个，则 dp 表的列数为 2 n ，也可以表示为 1 (n－1)。）
7.6.1 算法概述
表中，第一列表示从哪一个城市出发，其余列表示经过某些城市并回到城市 0 所产生的费用。例如，表中的第 4 行第 4 列，表示从城市 1 出发经过城市 2，然后回到城市 0 的费用为 45；表中的第 5 行第 7 列，表示从城市 2 出发经过城市[1,3]，然后回到城市 0 的费用为 55。
由上述分析可以看出，整个问题的需求为计算 dp[0][7]的值，而 dp[0][7]=min{C 01 +dp[1][6]，C 02 +dp[2][5]，C 03 +dp[3][3]}，因此计算 dp[0][7]的最优解就是计算 dp[1][6]、dp[2][5]、dp[3][3]三者中的最小值，其中，dp[1][6]=min{C 12 +dp[2][4]，C 13 +dp[3][2]}。同理，计算 dp[1][6]的最优解就是计算dp[2][4]、dp[3][2]二者中的较小值。以此类推，经过层层选取即可得到最终的最优解。
需要注意的是，计算 dp[2][3]即从城市 2 出发，经过城市{1,2}，这显然不合理，因{1,2}中已经包含了城市 2，这种情况需要忽略掉（即判断数字 3 的二进制数的第 2 位是不是 1，如果为 1 表示不合理）。同样，计算 dp[2][5]时，从城市 2 出发，经过城市{1,3}，如果选择先经过城市 1，再经过城市 3（城市 3 与城市 0 不直接相连，即 dp[3][{}]的值无法计算），则最终无法回到城市 0。
7.6.2 算法实现
采用动态规划法解决旅行商问题，如例所示。
例中，TSP()函数主要用来构建动态规划表 dp[N][M]，通过已知的记录顶点间距离的矩阵，推算出 dp[N][M]中每一个元素的值。其中，dp[N][M]表示从顶点 N 出发经过状态 M，最后到达起始点的总距离。根据 7.6.1 节的分析可知，从起始点出发再回到起始点的最短路径为 dp[N][（1 N－1 ）－1]（N 表示顶点的个数）。getPath()函数则通过动态规划表 dp[N][M]计算出从顶点 0 出发再回到顶点 0 的最短路径，即计算动态规划表 dp[N][M]中的最小子集（最优解）。printPath()函数用来输出最优的路径。程序运行结果如下所示。
7.6.2 算法实现
由运行结果可知，最短路径的长度为 23，经过顶点的顺序为0 1 4 2 3 0。为了测试上述输出是否正确，可以根据例中列出的矩阵画出对应的无向图，如图所示。
7.6.2 算法实现
根据顶点之间的权值可以看出，从顶点 0 出发，可以直接到达顶点 1、顶点 3、顶点 4，其权值分别为 3、8、9，因此下一个到达的顶点为顶点 1。再从顶点 1 出发，可以直接到达顶点 2、顶点 3、顶点 4，其权值分别为 3、10、5，如果选择先经过顶点 2，则接下来必须经过顶点 3、顶点 4，由于顶点 3 与顶点 4 之间的权值为 20（最大值），因此这里不能选择经过顶点 2。选择经过顶点 4，从顶点4 出发，可以直接到达顶点 2、顶点 3，其权值分别为 3、20，这里选择经过顶点 2。再从顶点 2 出发，经过最后一个未经过的顶点 3，最后回到顶点 0。从图 7.26 中可以计算得出，此路径为最优路径，其权值最小，为 23，与程序输出结果一致。
本章小结
本章主要展示了一些经典算法的操作实例。其中，约瑟夫问题与球钟问题都涉及了对数据结构的操作，包括单向循环链表的插入与删除、队列与栈的插入与删除等。本章通过回溯法解决了八皇后问题、背包问题以及地图着色问题，通过动态规划法解决了旅行商问题。望读者通过对具体实例的学习熟悉数据结构的基本操作，在理解算法设计思想的基础上，掌握代码操作方法，从而提高实际开发中的代码设计能力。

展开更多......

收起↑