广度优先搜索c++算法（广度优先搜索实现）

大家好，我是讯享网，很高兴认识大家。

公众号：编程驿站

贪心算法是一种常见算法。是以人性之念的算法，面对众多选择时，总是趋利而行。

因贪心算法以眼前利益为先，故总能保证当前的选择是最好的，但无法时时保证最终的选择是最好的。当然，在局部利益最大化的同时，也可能会带来最终利益的最大化。

假如在你面前有个盘子，分别放了很多苹果、橙子、梨子。

现以贪心之名，从个盘子里分别拿出其中最重的那个，则能求解出不同品种间最重水果的最大重量之和。这时，个盘子可认为是个子问题（局部问题）。

贪心算法会有一个排序过程。当看到盘子里的水果时，潜意识中你就在给它们排序。有时，因可排序的属性较多，必然导致使用求解问题时，贪心策略可能会有多种。

比如说选择水果，你可以选择每盘里最大的、最重的、最成熟的……具体应用那个策略，要根据求解的问题要求而定。贪心策略不同，导致的结论也会不一样。

本文将通过几个案例深入探讨贪心算法的贪心策略。

问题描述：

分析问题：

教室同一时间点只能安排一个活动，如果活动与活动之间存在时间交集（重叠），则这两个活动肯定是不能在同一天安排。

使用表示活动的开始时间，表示活动的结束时间。则可使用表示活动一，表示活动二。

如果存在：，则称这个活动不相容，不相容的活动不能在一天内同时出现。如下图所示。

只有当活动二的开始时间等于或晚于上活动一的结束时间时方可以在同一天出现。如下图所示。也即。此时，称这个活动是相容。

此问题中，活动的属性有：

那么，在使用贪心算法时，贪心的策略应该如何定夺？

最直接的想法是：每次安排活动时长最短的活动，必然可保证一天内容纳的活动数最多。

逻辑层面上讲，先以活动时长递增排序，然后依次选择。

但是忽视了一个问题，每一个活动都有固定的开始时间和结束时间。

如下图所示，因活动一所需时长最短，先选择。又因活动二所需时长次短，选择活动二。因两个活动时间间隔较长，采用此策略，会导致教室出现空闲时间。

针对此问题，贪心算法的出发点应该是保证每一时刻教室的最大利用率，才有可能容纳最多活动。

显然，受限于活动固定时间限制，此策略不可行。

能否每次选择活动时长最长的活动。提出这个策略时，就不是很自信的。分析问题吗？就不论正确，只论角度。

此策略和策略一相悖论。题目要求尽可能安排活动的数量，如果某活动的时长很长，一个活动就占据了大部分时间，显然，此种策略是无法实现题目要求的。

如下图，选择活动一，后再选择活动三。一天仅能安排次活动。根据图示，根据每个活动的开始、结束时间，一天之内至少可以安排个活动。

每次选择最早开始的活动。

先选择最早开始，等活动结束后，再选择相容且次开始的。这个策略和策略二会有同样的问题。如果最早开始的活动时长较长，必然会导致，大部分活动插入不进去。

还是回到策略一上面来，以时长最短的活动为优先，理论上是没有错的，但是不能简单的仅以时长作为排序依据。

可以以活动结束时间为依据。活动结束的越早，活动时长相对而言是较短的。因同时安排的活动需要有相容性，所以，再选择时，可选择开始时间等于或晚于前一个活动结束时间的活动，这也是与策略一不同之处，并不是简单的选择相容且绝对时长短的活动。

在活动时长较短情况，又能保证教室的使用时间一直连续的，则必然可以安排的活动最多。如下图所示：

输出结果：

问题描述：

分析问题：

此问题是可以使用贪心算法的，可以把每一个作业当成一个子问题看待。

本问题和上题差异之处：不在意作业什么时候完成，所以作业不存在开始时间和结束时间，每个作业仅有一个作业时长属性。所以，贪心策略也就只有个选择：

讯享网

如果是求解在规定的时间之内，能完成的作业数量最多，则可以使用此策略。

而本题是求解最终最短时间，此策略就不行。在几个作业同时工作时，最终完成的的时长是由最长时长的作业决定的。这是显然易见的道理。一行人行走，总是被行动被慢的人拖累。

如果把最长时长的作业排在最后，则其等待时间加上自己的作业时长，必然会导致最终总时长不是最优解。

先安排时长较长的作业，最理想状态可以保证在它工作时，其它时长较小的作业在它的周期内完成。

背包问题是类型问题，不是所有的背包问题都能使用贪心算法。

问题描述：

现有一可容纳重量为的背包，且有不同重量的物品，且每一个物品都有自己的价值，请问，怎么选择物品，才能保证背包里的价值最大化。

如果物品不可分，则称为问题，不能使用贪心算法，因为贪心算法无法保证背包装满。一般采用动态规划和递归方案。

如果物品可分，则可以使用贪心算法，本文讨论是可分的情况。

分析问题：

既然可以使用贪心算法，则现在要考虑贪心策略。

物品的有个属性：

直观的策略有个：

显然，以纯价值优先，是不行。

为什么以纯价值优先不行？

因为没有把价值和重量放在一起考虑。表面上一个物品的价值是较大的，这是宏观上的感觉。但是，这个物品是不是有较高的价值，应该从重量和价值比考虑，也就是价值密度。

Tips： 一块铁重克，价值为。一块金子重克，价值为。不能仅凭这么一个参数就说明铁比金子值钱。

所以，应该以重量、价值比高的物品作为贪心策略。

输出结果：

问题描述：

有一艘小船，每次只能载两个人过河。其中只能一人划船，渡河的时间等于其中划船慢的那个人的时间。现给定一群人和他们的划船时间，请求解最小全部渡河的时间。

分析问题：

可根据人数分情况讨论。如下表示人数：

当总人数时：

否则，按划船的时间由快到慢排序。

基本原则，回来时，选择最快的。

编码实现：

输出结果：

贪心算法在很多地方就可看其身影。如最短路径查找、最小生成树算法里都用到贪心算法。

贪心算法的关键在于以什么属性优先（贪心策略），这个选对了，后续实现都很简单。

广度优先搜索c++算法（广度优先搜索实现）

相关推荐