本章结束时，您将能够:
- 描述算法设计的贪婪方法
- 识别问题的最优子结构和贪婪选择性质
- 实现贪婪算法，如分数背包和贪婪图着色
- 使用不相交集数据结构实现克鲁斯卡尔最小生成树算法
在这一章中，我们将看看各种“贪婪”的算法设计方法，看看它们如何应用于解决现实世界的问题。
在前一章中，我们讨论了分治算法设计技术，该技术通过将输入分成较小的子问题，求解每个子问题，然后合并结果来解决给定的问题。继续我们算法设计范例的主题，我们现在将看看我们的下一个主题:贪婪方法。
在每次迭代中，贪婪算法会选择“看似最好”的选项。换句话说，问题的贪婪解由一系列局部最优解组成给定问题的全局最优解。例如，下面的截图显示了汽车从华盛顿州 DC 的杜勒斯国际机场到东河谷镇办公楼的最短路径。自然，对于路径上不是起点和终点的任意两点，所示路径也是最短的:
因此，我们可以推断，整个最短路径 P 实际上是沿着 P 的道路网络的顶点之间的几条最短路径的串联。因此，如果要求我们设计一个最短路径算法，一种可能的策略如下:从原点顶点开始，绘制一条到尚未探索的最近顶点的路径，然后重复，直到我们到达目的顶点。恭喜您–您刚刚使用迪克斯特拉算法解决了最短路径问题，该算法与为谷歌地图和必应地图等商业软件提供动力的算法相同！
令人期待的是，贪婪算法所采取的简单方法使得它们只适用于算法问题的一小部分。然而，贪婪方法的简单性通常使其成为“第一次攻击”的优秀工具，通过它我们可以了解潜在问题的属性和行为，然后可以使用其他更复杂的方法来解决这些问题。
在这一章中，我们将研究给定问题适合贪婪解的条件——最优子结构和贪婪选择性质。我们将会看到，当一个问题可以被证明具有这两个性质时，一个贪婪的解决方案肯定会产生正确的结果。我们还将看到一些在实践中使用贪婪解决方案的现实问题的例子，我们将在这一章的最后讨论最小生成树问题，它通常出现在电信和供水网络、电网和电路设计的情况下。但是首先，让我们先来看一些更简单的问题，这些问题可以使用贪婪算法来解决。
在本节中，我们将研究两个标准问题，可以使用贪婪方法解决:最短作业优先调度和分数背包问题。
假设你在银行排队。今天很忙，排队的人有 N 人，但是银行只有一个柜台开着(也是真的倒霉的一天！).假设一个人，pT4IaT8】I 的时间量在柜台得到服务。由于排队的人都很理性，所以大家都同意重新排序自己在队列中的位置，这样排队的每个人的平均等待时间就最小化了。你的任务是找到一种方法来重新排序队列中的人。你会如何解决这个问题？
为了进一步讨论这个问题，我们来看一个例子。上图为原始队列示例，其中 A i 显示服务时间， W i 显示第 i 个人的等待时间。离柜台最近的人可以立即开始接受服务，所以他们的等待时间是 0。排在第二的人必须等到第一个人完成，所以他们必须等待a1= 8个时间单位才能得到服务。以类似的方式继续，第 i 个人的等待时间等于队列中排在他们前面的所有I–1人的服务时间总和。
解决这个问题的一个线索是这样的:既然我们在寻求最小化平均等待时间，我们就必须想办法尽可能减少最大可能人群的等待时间。减少所有人等待时间的一个方法是以最快的速度完成工作。通过对队列中的所有人重复这个想法，我们的解决方案得到了以下重新排序的队列:
请注意，我们的重新排序队列的平均等待时间为 8.87 个单位，而原始排序的平均等待时间为 15.25 个单位，这大约是原来的 2 倍。
在本练习中，我们将通过采用上图所示的类似示例来实现最短作业优先调度解决方案。我们将考虑 10 个人排队，并尽量减少所有人的平均等待时间。让我们开始吧:
-
首先添加所需的标题，并创建计算等待时间和输入/输出的函数:
#include <iostream> #include <algorithm> #include <vector> #include <random> #include <numeric> // Given a set of service times, computes the service times for all users template<typename T> auto compute_waiting_times(std::vector<T>& service_times) { std::vector<T> W(service_times.size()); W[0] = 0; for (auto i = 1; i < service_times.size(); i++) W[i] = W[i - 1] + service_times[i - 1]; return W; } // Generic function to print a vector template<typename T> void print_vector(std::vector<T>& V) { for (auto& i : V) std::cout << i << " "; std::cout << std::endl; } template<typename T> void compute_and_print_waiting_times(std::vector<T>& service_times) { auto waiting_times = compute_waiting_times<int>(service_times); std::cout << "Service times: " << std::endl; print_vector<T>(service_times); std::cout << "Waiting times: " << std::endl; print_vector<T>(waiting_times); std::cout << "Average waiting time = " << std::accumulate(waiting_times.begin(), waiting_times.end(), 0.0) / waiting_times.size(); std::cout<< std::endl; }
-
添加主解算器和驱动代码，如下图:
void shortest_job_first(size_t size) { std::vector<int> service_times; std::random_device rd; std::mt19937 rand(rd()); std::uniform_int_distribution<std::mt19937::result_type> uniform_dist(1, size); // Insert random elements as service times service_times.reserve(size); for (auto i = 0; i < size; i++) service_times.push_back(uniform_dist(rand)); compute_and_print_waiting_times<int>(service_times); // Reorder the elements in the queue std::sort(service_times.begin(), service_times.end()); compute_and_print_waiting_times<int>(service_times); } int main(int argc, char* argv[]) { shortest_job_first(10); }
-
编译并运行代码！您的输出应该如下所示:
在本节中，我们将讨论标准的背包问题，也称为 0-1 背包问题，已知它是 NP 完全的，因此不允许我们有任何多项式时间的解。然后，我们将把我们的讨论转向背包问题的一个版本，称为分数背包问题，它可以使用贪婪的方法来解决。我们在这一部分的重点是演示如何即使是问题定义之间的细微差异也能导致解决方案策略的巨大变化。
假设给你一组对象， O = {O 1 ，O 2 ，…，O n } ，每一个都有一定的权重， W i ，值为 V i *。*还会给你一个只能装总重量 T 单位的包(或背包)。现在，假设你的任务是找出一套放在包里的东西，这样总重量就小于或等于 T，这些东西的总价值就是它可能的最大值。
这个问题的一个真实例子可以理解，如果你想象一个旅行交易者在所有交易中赚取固定的百分比利润。他们希望携带最大价值的货物，以使他们的利润最大化，但他们的车辆(或背包)最多只能容纳 T 个重量单位。交易者知道每件物品的确切重量和价值。他们应该携带哪一组物品，以使交易中携带的物品的总价值最大化？
上图中出现的问题是众所周知的背包问题，并且已经被证明是 NP 完全的。换句话说，这个问题没有已知的多项式时间解决方案。因此，我们必须查看对象的所有可能组合，以找到在总重量仅为 T 单位的情况下具有最大值的组合。上图显示了容量为 8 个单位的背包的两种填充方式。灰色的物体是那些被选择放入背包的物体。我们可以看到第一组对象的总值为 40，第二组对象的总值为 37，两种情况下的总重量都是 8 个单位。因此，第二组对象是比第一组对象更好的选择。为了找到最佳可能的对象集，我们必须列出所有可能的组合，并选择具有最大值的组合。
现在，我们将对上一小节中给出的背包问题进行一个小的修改:假设我们现在被允许将每个对象分成我们需要的多个部分，然后我们可以选择每个对象中我们想要保留在背包中的部分。
就现实世界的类比而言，假设我们前面类比中的交易者正在交易石油、谷物和面粉等物品。交易者可以选择任何较小的重量单位。
与标准背包的 NP 完全性相反，分数背包问题有一个简单的解决方案:根据元素的单位重量比的值来排序，并“贪婪地”选择尽可能多的具有最大比例的对象。下图显示了当背包容量设置为 8 个单位时，给定对象集的最佳选择。请注意，所选对象是单位重量比值最高的对象:
我们将在下面的练习中实现这个解决方案。
在本练习中，我们将考虑 10 个项目，并尝试最大化我们背包中的价值，该背包最大可容纳 25 个单位的重量。让我们开始吧:
-
First, we will begin by adding the required headers and defining an
Objectstruct that will represent one object in our solution:#include <iostream> #include <algorithm> #include <vector> #include <random> #include <numeric> template <typename weight_type, typename value_type, typename fractional_type> struct Object { using Wtype = weight_type; using Vtype = value_type; using Ftype = fractional_type; Wtype weight; Vtype value; Ftype value_per_unit_weight; // NOTE: The following overloads are to be used for std::sort() and I/O inline bool operator< (const Object<Wtype,Vtype,Ftype>& obj) const { // An object is better or worse than another object only on the // basis of its value per unit weight return this->value_per_unit_weight < obj.value_per_unit_weight; } inline bool operator== (const Object<Wtype, Vtype, Ftype>& obj) const { // An object is equivalent to another object only if // its value per unit weight is equal return this->value_per_unit_weight == obj.value_per_unit_weight; } // Overloads the << operator so an object can be written directly to a stream // e.g. Can be used as std::cout << obj << std::endl; template <typename Wtype, typename Vtype, typename Ftype> friend std::ostream& operator<<(std::ostream& os, const Object<Wtype,Vtype,Ftype>& obj); }; template <typename Wtype, typename Vtype, typename Ftype> std::ostream& operator<<(std::ostream& os, const Object<Wtype,Vtype,Ftype>& obj) { os << "Value: "<<obj.value << "\t Weight: " << obj.weight <<"\t Value/Unit Weight: " << obj.value_per_unit_weight; return os; }
请注意，我们已经重载了
<和==运算符，因为我们将在objects向量上使用std::sort()。 -
The code for the fractional knapsack solver is as follows:
template<typename weight_type, typename value_type, typename fractional_type> auto fill_knapsack(std::vector<Object<weight_type, value_type,fractional_type>>& objects, weight_type knapsack_capacity) { std::vector<Object<weight_type, value_type, fractional_type>> knapsack_contents; knapsack_contents.reserve(objects.size()); // Sort objects in the decreasing order std::sort(objects.begin(), objects.end()); std::reverse(objects.begin(), objects.end()); // Add the 'best' objects to the knapsack auto current_object = objects.begin(); weight_type current_total_weight = 0; while (current_total_weight <= knapsack_capacity && current_object != objects.end()) { knapsack_contents.push_back(*current_object); current_total_weight += current_object->weight; current_object++ ; } // Since the last object overflows the knapsack, adjust weight auto weight_of_last_obj_to_remove = current_total_weight - knapsack_capacity; knapsack_contents.back().weight -= weight_of_last_obj_to_remove; knapsack_contents.back().value -= knapsack_contents.back().value_per_unit_weight * weight_of_last_obj_to_remove; return knapsack_contents; }
前面的函数按照价值/重量比的降序对对象进行排序，然后挑选能够放入背包的对象的所有部分，直到背包满为止。
-
Finally, to test our implementation, add the following test and driver code:
void test_fractional_knapsack(unsigned num_objects, unsigned knapsack_capacity) { using weight_type = unsigned; using value_type = double; using fractional_type = double; // Initialize the Random Number Generator std::random_device rd; std::mt19937 rand(rd()); std::uniform_int_distribution<std::mt19937::result_type> uniform_dist(1, num_objects); // Create a vector of objects std::vector<Object<weight_type, value_type, fractional_type>> objects; objects.reserve(num_objects); for (auto i = 0; i < num_objects; i++) { // Every object is initialized with a random weight and value auto weight = uniform_dist(rand); auto value = uniform_dist(rand); auto obj = Object<weight_type, value_type, fractional_type> { static_cast<weight_type>(weight), static_cast<value_type>(value), static_cast<fractional_type>(value) / weight }; objects.push_back(obj); } // Display the set of objects std::cout << "Objects available: " << std::endl; for (auto& o : objects) std::cout << o << std::endl; std::cout << std::endl; // Arbitrarily assuming that the total knapsack capacity is 25 units auto solution = fill_knapsack(objects, knapsack_capacity); // Display items selected to be in the knapsack std::cout << "Objects selected to be in the knapsack (max capacity = " << knapsack_capacity<< "):" << std::endl; for (auto& o : solution) std::cout << o << std::endl; std::cout << std::endl; } int main(int argc, char* argv[]) { test_fractional_knapsack(10, 25); }
前面的函数创建对象，并用 STL 随机数生成器中的随机数据初始化它们。接下来，它调用我们的分数背包求解器的实现，然后显示结果。
-
编译并运行这段代码！您的输出应该如下所示:
请注意解算器是如何获取分数的，也就是说，按重量计算，最后一个对象的 5 个单位中只有 4 个。这是一个如何在选择对象保存在背包中之前对其进行分区的示例，这将分数背包与 0-1(标准)背包问题区分开来。
想象一下，你的待办事项清单上有一组任务(洗碗、去超市买杂货、为统治世界的秘密项目工作，以及其他类似的杂务)。每个任务由一个标识来标识，并且只能在特定的开始和结束时间之间完成。假设您希望完成最大数量的任务。在什么子集上，以什么顺序，你应该完成你的任务来实现你的目标？假设在任何时间点，您只能处理一项任务。
例如，考虑下图所示的问题实例。我们被赋予了四个不同的任务，我们可以花时间去完成它们(矩形框代表任务可以完成的时间间隔):
下图显示了任务的最佳计划，它最大化了已完成的任务总数:
请注意，不完成任务 3 如何让我们完成任务 1 和 2，从而增加已完成任务的总数。在本练习中，您将需要实现这个贪婪的间隔调度解决方案。
解决此活动的高级步骤如下:
-
假设每个任务都有一个开始时间、一个结束时间和一个标识。创建描述任务的结构。我们将用这个结构的不同实例来表示不同的任务。
-
实现一个创建 N 个任务的
std::list的函数，从 1 到 N 顺序设置它们的标识，并使用随机数生成器的值作为开始和结束时间。 -
Implement the scheduling function as follows:
a.按照任务结束时间的递增顺序对任务列表进行排序。
b.贪婪地选择以最早的结束时间完成任务。
c.删除与当前所选任务重叠的所有任务(当前任务结束前开始的所有任务)。
d.如果任务仍在列表中，转到步骤 b 。否则，返回选择的任务向量。
您的最终输出应该如下所示:
这个活动的解决方案可以在第 516 页找到。
在前一节中，我们看了贪婪方法给出最优解的问题的例子。然而，当且仅当一个问题具有两个性质时，可以使用贪婪方法最优地解决该问题:最优子结构性质和贪婪选择性质。在本节中，我们将尝试理解这些属性，并向您展示如何识别问题是否表现出这些属性。
最优子结构:当一个给定问题的最优解 P 由它的子问题的最优解组成时，那么 P 被称为具有最优子结构。
贪婪选择:当一个给定问题的最优解 P 可以通过在每次迭代中选择局部最优解来达到时，P 被称为具有贪婪选择性质。
为了理解最优子结构和贪婪选择性质，我们将实现 Kruskal 的最小生成树算法。
最小生成树问题可以表述如下:
“给定一个图，G = < V，E >，其中 V 是顶点集，E 是边集，每个边都与一个边权重相关联，找到一棵树 T，它跨越 V 中的所有顶点，并且具有最小的总权重。”
MST 问题的一个实际应用是供水和运输网络的设计，因为设计者通常希望最小化所使用的管道或所创建的道路的总长度，并且仍然确保服务到达所有指定的用户。让我们试着用下面的例子把这个问题分开。
假设给你一张地图上 12 个村庄的位置，并要求你找出需要修建的道路的最小总长度，以便所有的村庄都可以相互到达，并且道路不会形成一个循环。假设每条路都可以沿任一方向穿越。这个问题中村庄的一种自然表示是使用图数据结构。让我们假设下图的顶点 G 代表 12 个给定村庄的位置， G 的边代表顶点之间的距离:
构造最小生成树 T 的简单贪婪算法如下:
- 将 G 的所有边加入一个最小堆， H 。
- 从 H 开始，弹出一个边， e 。自然， e 在 H 中所有边中成本最小。
- 如果 e 的两个顶点都已经在 T 中，这意味着添加 e 将在 T 中创建一个循环。因此，丢弃 e ，转到步骤 2。否则，继续下一步。
- 将 e 插入最小生成树， T 。
让我们花点时间来思考一下为什么这个策略有效。在第 2 步和第 3 步循环的每次迭代中，我们取成本最低的边，检查它是否给我们的解增加了顶点。这存储在最小生成树 T 中。如果有，我们给 T 加边；否则，我们丢弃该边并选择另一条具有最小值的边。我们的算法是贪婪的，因为在每次迭代中，它选择最小的边权重添加到解中。前面的算法发明于 1956 年，被称为克鲁斯卡尔最小生成树算法。将该算法应用到图 5.11所示的图中，得到以下结果:
最小生成树中边的总权重 T 为 (2 × 1) + (3 × 2) + (2 × 3) = 14 个单位。因此，我们的问题的答案是，至少需要建造 12 个单位的道路。
我们如何知道我们的算法确实是正确的？我们需要回到最优子结构和贪婪选择的定义，并证明 MST 问题表现出这两个性质。虽然这些性质的严格数学证明超出了本书的范围，但这些证明背后的直观思想如下:
最优子结构:我们将用矛盾来证明这一点。让我们假设 MST 问题没有表现出最优子结构；也就是说，最小生成树不是由一组较小的最小生成树组成的:
- 假设给我们一个最小生成树 T ，在图的顶点 G 上，让我们从 T 移除任何边 e 。去除 e 将 T 分解成更小的树，T1T**2。
- 由于我们假设 MST 问题不表现出最优子结构，因此在 T 1 的顶点上一定存在总权重较小的生成树。取此生成树，加上边eT2。这棵新树将是 T' 。
- 现在，由于 T' 的总重量小于 T 的总重量，这与我们最初的假设 T 是一个 MST 相矛盾。因此，最小二乘问题必须表现出最优子结构性质。
贪婪选择:如果 MST 问题表现出贪婪选择属性，那么对于一个顶点， v ，连接 v 到图的其余部分的最小权边， G ，应该始终是最小生成树的一部分， T 。我们可以通过矛盾来证明这个假设，如下:
-
假设一条边 (u，v) 是连接 v 到 G 中任何其他顶点的最小权重边。假设 (u，v) 不是 T 的一部分。
-
如果 (u，v) 不是 T 的一部分，那么 T 必须由将 v 连接到其余 G 的一些其他边组成。设此边为 (x，v) 。由于 (u，v) 是最小重量边，根据定义， (x，v) 的重量大于 (u，v) 的重量。
-
A tree with a lesser total weight than T can be obtained if (x, v) is replaced with (u, v) in T. This contradicts our assumption that T is the minimum spanning tree. Therefore, the MST problem must exhibit the greedy choice property.
正如我们前面提到的，我们也可以采取严格的数学方法来证明 MST 问题表现出最优子结构性质，并且适用于贪婪选择性质。你可以在这里找到:https://OCW . MIT . edu/courses/electric-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2015/讲义/MIT6_046JS15_lec12.pdf 。
让我们思考一下如何实现 Kruskal 算法。我们在第 2 章、树、堆和图中介绍了图和堆数据结构，因此我们知道如何实现步骤 1 和 2。第三步有点复杂。我们需要一个数据结构来存储图的边，并告诉我们添加新的边是否会创建一个循环，其中已经存储了边的任何可能组合。这个问题可以通过使用不相交集数据结构来解决。
一个不相交集数据结构由一个元素森林(一组树)组成，其中每个元素由一个数字标识表示，有一个“等级”，并包含一个指向其父元素的指针。当数据结构初始化时，它以等级为 0 的 N 个独立元素开始，每个元素都是只包含元素本身的树的一部分。数据结构支持另外两种操作:
- 对树的
find操作返回该树的根元素 - 应用于两棵树的
union操作将较小的树合并成较大的树，其中树的大小存储为其根的等级。
更准确地说，分离集数据结构支持以下操作:
Make-Set:这用 N 个元素初始化数据结构，将每个元素的秩设置为 0，父指针指向自身。下图显示了用五个元素初始化的不相交集 DS 的示例。圆圈内的数字表示元素标识，括号内的数字表示等级，箭头表示指向根元素的指针:
在这个阶段，数据结构由五棵树组成，每棵树由一个元素组成。
Find:从给定元素 x 开始，find操作跟随元素的父指针，直到到达树的根。根元素的父元素是根本身。在上一个例子中，每个元素都是树的根，因此这个操作将返回树中唯一的元素。Union:给定两个元素 x 和 y ，union运算找到 x 和 y 的根。如果两个根相同，这意味着 x 和 y 属于同一棵树。因此，它什么也不做。否则，它将具有较高等级的根设置为具有较低等级的根的父级。下图显示了在 DS 上执行Union(1, 2)和Union(4, 5)操作的结果:
随着后续联合操作的应用，更多的树合并成更少(但更大)的树。下图为应用Union(2, 3)后 DS 中的树木:
下图为应用Union(2, 4)后 DS 中的树木:
现在，让我们理解不相交集数据结构如何帮助我们实现 Kruskal 算法。在算法开始时，在步骤 1 之前，我们初始化一个不相交集数据结构，其中 N 等于图中的顶点数， G 。然后，步骤 2 从最小堆中取出一条边，步骤 3 检查所考虑的边是否形成一个循环。请注意，循环检查可以使用 DS 上的union操作来实现，该操作应用于边的两个顶点。如果union操作成功合并了两棵树，则边缘被添加到 MST 中；否则，可以安全地丢弃该边缘，因为它会在 MST 中引入一个周期。以下说明的步骤解释了这一逻辑:
-
First, we begin by initializing a disjoint-set data structure, DS, containing all of the given vertices in the graph:
-
Let's proceed to add the edge with the lowest weight to our MST. As you can see from the following figure, as we add edge (2,4), we also apply
Union(2,4)to the elements in DS:
-
As we proceed with adding edges as per the algorithm, we reach edge (1,5). As you can see, in DS, the corresponding elements are in the same tree. Hence, we cannot add that edge. As you can see from the following graph, adding that would have created a cycle:
在下面的练习中，我们将使用不相交集数据结构实现 Kruskal 的最小生成树算法。
在本练习中，我们将实现不相交集数据结构和 Kruskal 算法，以在图中找到一个 MST。让我们开始吧:
-
首先添加以下标题并声明
Graph数据结构:#include<iostream> #include<vector> #include<algorithm> #include<queue> #include<map> template <typename T> class Graph;
-
首先，我们将实现不相交集:
template<typename T> class SimpleDisjointSet { private: struct Node { T data; Node(T _data) : data(_data) {} bool operator!=(const Node& n) const { return this->data != n.data; } }; // Store the forest std::vector<Node> nodes; std::vector<size_t> parent; std::vector<size_t> rank;
-
添加类的构造函数，实现
Make-set和Find操作，如下图:public: SimpleDisjointSet(size_t N) { nodes.reserve(N); parent.reserve(N); rank.reserve(N); } void add_set(const T& x) { nodes.emplace_back(x); parent.emplace_back(nodes.size() - 1); // the parent is the node itself rank.emplace_back(0); // the initial rank for all nodes is 0 } auto find(T x) { // Find the node that contains element 'x' auto node_it = std::find_if(nodes.begin(), nodes.end(), [x](auto n) {return n.data == x; }); auto node_idx = std::distance(nodes.begin(), node_it); auto parent_idx = parent[node_idx]; // Traverse the tree till we reach the root while (parent_idx != node_idx) { node_idx = parent_idx; parent_idx = parent[node_idx]; } return parent_idx; }
-
接下来，我们将在不相交集合中的两棵树之间执行
Union操作，如下所示:// Union the sets X and Y belong to void union_sets(T x, T y) { auto root_x = find(x); auto root_y = find(y); // If both X and Y are in the same set, do nothing and return if (root_x == root_y) { return; } // If X and Y are in different sets, merge the set with lower rank // into the set with higher rank else if (rank[root_x] > rank[root_y]) { parent[root_y] = parent[root_x]; rank[root_x]++ ; } else { parent[root_x] = parent[root_y]; rank[root_y]++ ; } } };
-
Now that our implementation of the disjoint set is complete, let's start implementing the graph. We will use an edge-list representation. The
edgestruct is defined as follows:template<typename T> struct Edge { size_t src; size_t dest; T weight; // To compare edges, only compare their weights, // and not the source/destination vertices inline bool operator< (const Edge<T>& e) const { return this->weight < e.weight; } inline bool operator> (const Edge<T>& e) const { return this->weight > e.weight; } };
因为我们的边的实现是模板化的，所以边权重可以是实现
<和>运算的任何数据类型。 -
以下函数允许图被序列化并输出到流:
template <typename T> std::ostream& operator<<(std::ostream& os, const Graph<T>& G) { for (auto i = 1; i < G.vertices(); i++) { os << i <<":\t"; auto edges = G.edges(i); for (auto& e : edges) os << "{" << e.dest << ": " << e.weight << "}, "; os << std::endl; } return os; }
-
The graph data structure can now be implemented with the following code:
template<typename T> class Graph { public: // Initialize the graph with N vertices Graph(size_t N): V(N) {} // Return number of vertices in the graph auto vertices() const { return V; } // Return all edges in the graph auto& edges() const { return edge_list; } void add_edge(Edge<T>&& e) { // Check if the source and destination vertices are within range if (e.src >= 1 && e.src <= V && e.dest >= 1 && e.dest <= V) edge_list.emplace_back(e); else std::cerr << "Vertex out of bounds" << std::endl; } // Returns all outgoing edges from vertex v auto edges(size_t v) const { std::vector<Edge<T>> edges_from_v; for(auto& e:edge_list) { if (e.src == v) edges_from_v.emplace_back(e); } return edges_from_v; } // Overloads the << operator so a graph be written directly to a stream // Can be used as std::cout << obj << std::endl; template <typename T> friend std::ostream& operator<< <>(std::ostream& os, const Graph<T>& G); private: size_t V; // Stores number of vertices in graph std::vector<Edge<T>> edge_list; };
我们的图实现不允许在创建图后更改图中的顶点数量。此外，尽管我们可以根据需要添加任意多的边，但由于在本练习中不需要删除边，因此没有实现删除边。
-
现在，我们可以这样实现克鲁斯卡尔算法:
// Since a tree is also a graph, we can reuse the Graph class // However, the result graph should have no cycles template<typename T> Graph<T> minimum_spanning_tree(const Graph<T>& G) { // Create a min-heap for the edges std::priority_queue<Edge<T>, std::vector<Edge<T>>, std::greater<Edge<T>>> edge_min_heap; // Add all edges in the min-heap for (auto& e : G.edges()) edge_min_heap.push(e); // First step: add all elements to their own sets auto N = G.vertices(); SimpleDisjointSet<size_t> dset(N); for (auto i = 0; i < N; i++) dset.add_set(i); // Second step: start merging sets Graph<T> MST(N); while (!edge_min_heap.empty()) { auto e = edge_min_heap.top(); edge_min_heap.pop(); // Merge the two trees and add edge to the MST only if the two vertices of the edge belong to different trees in the MST if (dset.find(e.src) != dset.find(e.dest)) { MST.add_edge(Edge <T>{e.src, e.dest, e.weight}); dset.union_sets(e.src, e.dest); } } return MST; }
-
最后，添加此处显示的驱动程序代码:
int main() { using T = unsigned; Graph<T> G(9); std::map<unsigned, std::vector<std::pair<size_t, T>>> edges; edges[1] = { {2, 2}, {5, 3} }; edges[2] = { {1, 2}, {5, 5}, {4, 1} }; edges[3] = { {4, 2}, {7, 3} }; edges[4] = { {2, 1}, {3, 2}, {5, 2}, {6, 4}, {8, 5} }; edges[5] = { {1, 3}, {2, 5}, {4, 2}, {8, 3} }; edges[6] = { {4, 4}, {7, 4}, {8, 1} }; edges[7] = { {3, 3}, {6, 4} }; edges[8] = { {4, 5}, {5, 3}, {6, 1} }; for (auto& i : edges) for(auto& j: i.second) G.add_edge(Edge<T>{ i.first, j.first, j.second }); std::cout << "Original Graph" << std::endl; std::cout << G; auto MST = minimum_spanning_tree(G); std::cout << std::endl << "Minimum Spanning Tree" << std::endl; std::cout << MST; return 0; }
-
最后，运行程序！您的输出应该如下所示:
验证我们算法的输出确实是图 5.12 所示的 MST。
不使用不相交集的 Kruskal 算法的复杂度为 O(E log E) ，其中 E 为图中的边数。然而，对于不相交的集合，总复杂性归结为O(Eα(V)，其中 α (v) 是阿克曼函数的逆函数。由于逆阿克曼函数的增长速度比对数函数慢得多，所以对于具有几个顶点的图来说，这两种实现的性能差异很小，但是对于更大的图实例来说，差异可能特别大。
顶点着色问题可以表述如下:
“给定一个图 G，给图的每个顶点分配一种颜色，这样就不会有两个相邻的顶点具有相同的颜色。”
例如，下图显示了在图 5.11 中显示的图的有效着色:
图着色在解决现实世界中的各种各样的问题方面都有应用——为出租车制定时间表、解决数独难题和为考试制定时间表，这些都可以映射到找到问题的有效着色，建模为图。然而，找到产生有效顶点着色所需的最小颜色数(也称为色数)是一个 NP 完全问题。因此，问题本质上的一个微小变化就能对它的复杂性产生巨大的影响。
作为图着色问题应用的一个例子，让我们考虑数独解算器的情况。数独是一个数字布局难题，目标是用 1 到 9 的数字填充一个 9 × 9 的盒子，每行不重复数字。每列是一个 3 × 3 的块。这里显示了一个数独谜题的例子:
我们可以将这个难题的一个实例建模为图着色问题，如下所示:
- 用图 G 中的一个顶点表示拼图中的每个单元格。
- 在同一列、行或同一 3 × 3 块中的顶点之间添加边。
- 然后 G 的一个有效着色给了我们一个原始数独难题的解决方案。
我们将在下面的练习中研究图着色的实现。
在本练习中，我们将实现一个贪婪算法，当可以使用的最大颜色数为 6 时，该算法为图 5.21中所示的图生成图着色。让我们开始吧:
-
首先包含所需的头文件并声明
Graph数据结构，我们将在本练习的后面部分实现:#include <unordered_map> #include <set> #include <map> #include <string> #include <vector> #include <iostream> template <typename T> class Graph;
-
下面的结构在我们的图中实现了一条边:
template<typename T> struct Edge { size_t src; size_t dest; T weight; // To compare edges, only compare their weights, // and not the source/destination vertices inline bool operator< (const Edge<T>& e) const { return this->weight < e.weight; } inline bool operator> (const Edge<T>& e) const { return this->weight > e.weight; } };
-
以下函数允许我们将图直接写入输出流:
template <typename T> std::ostream& operator<<(std::ostream& os, const Graph<T>& G) { for (auto i = 1; i < G.vertices(); i++) { os << i << ":\t"; auto edges = G.outgoing_edges(i); for (auto& e : edges) os << "{" << e.dest << ": " << e.weight << "}, "; os << std::endl; } return os; }
-
将图实现为边列表，如下图所示:
template<typename T> class Graph { public: // Initialize the graph with N vertices Graph(size_t N) : V(N) {} // Return number of vertices in the graph auto vertices() const { return V; } // Return all edges in the graph auto& edges() const { return edge_list; } void add_edge(Edge<T>&& e) { // Check if the source and destination vertices are within range if (e.src >= 1 && e.src <= V && e.dest >= 1 && e.dest <= V) edge_list.emplace_back(e); else std::cerr << "Vertex out of bounds" << std::endl; } // Returns all outgoing edges from vertex v auto outgoing_edges(size_t v) const { std::vector<Edge<T>> edges_from_v; for (auto& e : edge_list) { if (e.src == v) edges_from_v.emplace_back(e); } return edges_from_v; } // Overloads the << operator so a graph be written directly to a stream // Can be used as std::cout << obj << std::endl; template <typename T> friend std::ostream& operator<< <>(std::ostream& os, const Graph<T>& G); private: size_t V; // Stores number of vertices in graph std::vector<Edge<T>> edge_list; };
-
下面的散列图存储了我们的着色算法将使用的颜色列表:
// Initialize the colors that will be used to color the vertices std::unordered_map<size_t, std::string> color_map = { {1, "Red"}, {2, "Blue"}, {3, "Green"}, {4, "Yellow"}, {5, "Black"}, {6, "White"} };
-
接下来，让我们实现一个助手函数，打印分配给每个顶点的颜色:
void print_colors(std::vector<size_t>& colors) { for (auto i=1; i<colors.size(); i++) { std::cout << i << ": " << color_map[colors[i]] << std::endl; } }
-
以下函数实现了我们的着色算法:
template<typename T> auto greedy_coloring(const Graph<T>& G) { auto size = G.vertices(); std::vector<size_t> assigned_colors(size); // Let us start coloring with vertex number 1\. // Note that this choice is arbirary. for (auto i = 1; i < size; i++) { auto outgoing_edges = G.outgoing_edges(i); std::set<size_t> neighbour_colors; for (auto e : outgoing_edges) { auto dest_color = assigned_colors[e.dest]; neighbour_colors.insert(dest_color); } // Find the smallest unassigned color // that is not currently used by any neighbor auto smallest_unassigned_color = 1; for (; smallest_unassigned_color <= color_map.size(); smallest_unassigned_color++) { if (neighbour_colors.find(smallest_unassigned_color) == neighbour_colors.end()) break; } assigned_colors[i] = smallest_unassigned_color; } return assigned_colors; }
-
最后添加驱动代码，如下图:
int main() { using T = size_t; Graph<T> G(9); std::map<unsigned, std::vector<std::pair<size_t, T>>> edges; edges[1] = { {2, 2}, {5, 3} }; edges[2] = { {1, 2}, {5, 5}, {4, 1} }; edges[3] = { {4, 2}, {7, 3} }; edges[4] = { {2, 1}, {3, 2}, {5, 2}, {6, 4}, {8, 5} }; edges[5] = { {1, 3}, {2, 5}, {4, 2}, {8, 3} }; edges[6] = { {4, 4}, {7, 4}, {8, 1} }; edges[7] = { {3, 3}, {6, 4} }; edges[8] = { {4, 5}, {5, 3}, {6, 1} }; for (auto& i : edges) for (auto& j : i.second) G.add_edge(Edge<T>{ i.first, j.first, j.second }); std::cout << "Original Graph: " << std::endl; std::cout << G << std::endl; auto colors = greedy_coloring<T>(G); std::cout << "Vertex Colors: " << std::endl; print_colors(colors); return 0; }
-
运行实现！您的输出应该如下所示:
我们的实现总是从顶点标识 1 开始给顶点着色。但是，这种选择是任意的，即使在同一个图上用不同的顶点启动贪婪着色算法，也很可能导致需要不同颜色数的不同图着色。
图着色的质量通常通过它用来给图着色的颜色数量来衡量。虽然找到使用最少可能颜色数的最佳图着色是 NP 完全的，但是贪婪图着色通常用作有用的近似。例如，当设计一个编译器时，图着色被用来将中央处理器寄存器分配给正在编译的程序的变量。贪婪着色算法与一组试探法一起使用，以获得问题的“足够好”的解决方案，这在实践中是可取的，因为我们需要编译器快速才能有用。
对用固定顶点标识开始贪婪着色的简单方法的改进是，按照入射到顶点上的边的数量的递减顺序(或按照顶点的度数的递减顺序)对顶点着色。
该算法的工作原理如下:
- 按照度数递减的顺序对所有顶点进行排序，并将它们存储在一个数组中。
- 取排序后的数组中第一个未着色的顶点，给它分配第一个没有分配给它的任何邻居的颜色。让这个颜色为 C 。
- 遍历排序后的数组，将颜色 C 分配给每个没有任何已经分配了 C 的邻居的未着色顶点。
- 如果数组中还有未着色的顶点，请转到步骤 2。否则，结束程序。到目前为止分配给顶点的颜色是最终输出。
以下是算法的四次迭代的示例，需要这四次迭代来找到图的有效着色，如图 5.21所示:
*1. Here is the graph that we start with:
###### 图 5.24:从未着色的图开始
-
Next, we sort by decreasing order of vertices, and start by coloring red:
-
In the next round, we start coloring blue:
-
在最后一轮中，我们将颜色涂成绿色:
完成本活动的高级步骤如下:
- 假设图的每条边都有源顶点标识、目标顶点标识和边权重。实现一个表示图的边的结构。我们将使用这个结构的实例在我们的图表示中创建不同的边。
- 使用边列表表示实现一个图。
- 实现一个函数，该函数实现威尔士-鲍威尔图着色并返回一个颜色向量。矢量中索引 i 处的颜色应该是分配给顶点标识 i 的颜色。
- 根据需要添加驱动程序和输入/输出代码，创建图图 5.24 所示的图。可以假设着色总是从顶点标识 1 开始。
您的输出应该如下所示:
这个活动的解决方案可以在第 518 页找到。
贪婪的方法很简单:在算法的每次迭代中，从所有可能的选择中挑选看似最好的选择。换句话说，当在每次迭代中选择局部“最佳”的替代方案导致问题的全局最优解时，问题的贪婪解是适用的。
在这一章中，我们看了一些问题的例子，其中贪婪方法是最优的，并导致给定问题的正确解决方案；也就是最短作业优先调度。我们还讨论了诸如 0-1 背包和图着色问题等 NP 完全问题的轻微修改版本如何具有简单的贪婪解。这使得贪婪方法成为解决困难问题的重要算法设计工具。对于有贪婪解决方案的问题，很可能是最简单的解决方法；即使对于没有贪婪解决方案的问题，它也可以经常用于解决实际中可能“足够好”的问题的宽松版本(例如，在编程语言编译器中将寄存器分配给变量时使用贪婪图着色)。
接下来，我们讨论了贪婪选择和最优子结构性质，并看了一个证明给定问题表现出这些性质的例子。我们用最小生成树问题的两个解决方案来结束这一章:克鲁斯卡尔算法和威尔士-鲍威尔算法。我们对 Kruskal 算法的讨论也引入了不相交集数据结构。
在下一章中，我们将重点介绍图算法，从广度优先和深度优先搜索开始，然后介绍 Dijkstra 的最短路径算法。我们还将研究最小生成树问题的另一种解决方案:Prim 算法。*