123456789实验四实验目的与要求：掌握动态规划方法的基本思想与设计策略。1．多段图中的最短路径问题【问题描述】建立一个从源点S到终点T的多段图，设计一个动态规划算法求出从S到T的最短路径值，并输出相应的最短路径。2．有向无环图中的最短路径问题【问题描述】建立一个从源点S到终点E的有向无环图， ...

123456789实验十二实验目的与要求：（1） 理解与掌握求解最大流与最小割的基本算法。（2） 学会应用最大流与最小割算法解决实际问题。1．实现Ford-Fulkerson算法，求出给定图中从源点s到汇点t的最大流，并输出最小割。2. 设计与实现二部图匹配（Bipartite Matching） ...

12345678910实验十三实验目的与要求：（1） 理解与掌握求解最大流与最小割的基本算法。（2） 学会应用最大流与最小割算法解决实际问题。1. 设计与实现项目选择（Project Selection）问题的算法。2. 设计与实现调查设计（Survey Design）问题的算法。 1234567 ...

12345678910111213实验十一实验目的与要求：（1） 掌握对无向图的2-连通分量的划分算法。（2） 理解与掌握在含负权值边的图中求最短路径问题的算法。1．无向图的双连通分量问题【问题描述】给定一个无向图，设计一个算法，判断该图中是否存在关节点，并划分双连通分量。2．带负权值边的有向图中 ...

1234567891011实验十实验目的与要求：（1） 掌握使用图的深度优先搜索算法实现对有向图中是否包含环的判断；（2） 掌握使用图的深度优先搜索算法实现对有向图的强连通分量的划分。1．有向图中环的判断问题【问题描述】给定一个有向图，要求使用深度优先搜索策略，判断图中是否存在环。2．有向图的强连 ...

123456789101112实验六实验目的与要求：掌握动态规划方法的基本思想与设计策略。1．最长公共子序列问题【问题描述】⑴ 给定两个字符串X和Y，设计一个动态规划算法，求出这两个字符串的最长公共子序列，并输出该子序列。⑵ 若仅要求求出两个字符串的最长公共子序列的长度值，为节省存储空间，采用“滚 ...

12345678910实验八实验目的与要求：（1） 掌握贪心法的基本思想和设计方法。1．区间调度问题【问题描述】给定n个活动，其中的每个活动ai包含一个起始时间si与结束时间fi。设计与实现算法从n个活动中找出一个最大的相互兼容的活动子集S。要求：分别设计动态规划与贪心算法求解该问题。其中，对贪心 ...

1234567891011实验五实验目的与要求：掌握动态规划方法的基本思想与设计策略。1．最长递增子序列问题【问题描述】给定一个整数数组，设计一个动态规划算法求出该数组中的最长递增子序列。2．矩阵连乘问题【问题描述】给定n个矩阵{A1，A2，…,An},其中AiAi+1是可乘的 ...

1 K路归并1.0 问题描述 将$k$个已经排序的数组归并成一个大的排序的结果数组。 1.1 初步分析 其实这个问题可以说是一个问题的更加普遍形式。回顾一下我们在讨论归并排序的时候。那时候我们是将一个数组分解成两个子序列进行排序，然后再进行归并。这个过程一直递归下去。而其中归并结果的过程 ...

12345678910111213实验九实验目的与要求：（1） 掌握贪心法的基本思想和设计方法。1．区间划分问题【问题描述】给定一组报告，其中的每个报告设置了一个开始时间si和结束时间fi。设计与实现一个算法，对这组报告分配最少数量的教室，使得这些报告能无冲突的举行。2．最小延迟调度问题【问题描述 ...