贪婪算法示例：什么是贪婪算法、方法和途径

由： 陈莎拉 陈莎拉
Hours 更新

什么是贪婪算法？

In 贪心算法 根据执行过程中任意给定阶段资源的最大、即时可用性，对一组资源进行递归划分。

要基于贪婪方法解决问题，有两个阶段

  1. 扫描物品清单
  2. 优化

本贪婪算法教程在数组划分的过程中并行涵盖了这些阶段。

要理解贪婪方法，您需要具备递归和上下文切换的应用知识。这有助于您了解如何跟踪代码。您可以根据自己的必要和充分语句来定义贪婪范式。

两个条件定义了贪婪范式。

  • 每个逐步解决方案都必须构建一个问题以找到最佳解决方案。
  • 如果问题的构造可以在有限数量的贪婪步骤中停止就足够了。

随着理论的继续，让我们描述一下贪婪搜索方法的历史。

贪婪的历史 Algorithms

这是贪婪算法的一个重要里程碑：

  • 贪婪算法在 1950 世纪 XNUMX 年代被概念化为许多图游走算法。
  • Esdger Djikstra 构思了生成最小生成树的算法。他的目标是缩短荷兰首都阿姆斯特丹内的路线跨度。
  • 在同一时期，Prim 和 Kruskal 实现了基于最小化加权路线路径成本的优化策略。
  • 70年代，美国研究者Cormen、Rivest和Stein在他们所著的经典算法导论著作中提出了贪婪解的递归子结构。
  • 贪婪搜索范式于 2005 年在 NIST 记录中注册为一种不同类型的优化策略。
  • 迄今为止，运行网络的协议，例如开放最短路径优先 (OSPF) 和许多其他网络数据包交换协议都使用贪婪策略来最大限度地减少在网络上花费的时间。

贪婪策略和决策

逻辑最简单的形式可以归结为“贪婪”或“不贪婪”。这些语句由每个算法阶段所采用的推进方法定义。

例如，Djikstra 算法采用逐步贪婪策略，通过计算成本函数来识别互联网上的主机。成本函数返回的值决定了下一条路径是“贪婪”还是“非贪婪”。

简而言之，如果算法在任何阶段采取的步骤不是局部贪婪的，那么它就不再是贪婪的。贪婪问题停止，不再有贪婪的范围。

贪婪算法的特点

贪婪算法的重要特征是：

  • 有一个有序的资源列表，其中包含成本或价值属性。这些量化了系统的限制。
  • 您将在限制时间内获取最大数量的资源。
  • 例如，在活动调度问题中，资源成本以小时为单位，并且活动需要按顺序执行。

贪婪算法的特点

为什么要使用贪婪方法？

以下是使用贪婪方法的原因：

  • 贪婪方法有一些权衡，这可能使其适合优化。
  • 一个突出的原因是立即获得最可行的解决方案。在活动选择问题中（下面解释），如果在完成当前活动之前可以进行更多活动，则可以在相同的时间内完成这些活动。
  • 另一个原因是根据条件递归地划分问题，而不需要组合所有的解决方案。
  • 在活动选择问题中，“递归划分”步骤是通过仅扫描一次项目列表并考虑某些活动来实现的。

如何解决活动选择问题

在活动安排示例中，每个活动都有“开始”和“结束”时间。每个活动都用数字索引以供参考。活动分为两类。

  1. 深思熟虑的活动：是Activity，是分析能否完成多个剩余Activity的参考。
  2. 其余活动： 在所考虑的活动之前一个或多个索引处进行的活动。

总持续时间给出了执行活动的成本。也就是说（完成 - 开始）给出了活动成本的持续时间。

您将了解到贪婪程度是在考虑活动时间内可以执行的剩余活动的数量。

相关文章

Archi贪婪方法的结构

步骤1） 扫描活动成本列表，以索引 0 开始作为考虑的索引。

步骤2） 当所考虑的活动完成时，可以完成更多活动，开始搜索一个或多个剩余活动。

步骤3） 如果没有剩余活动，则当前剩余活动将成为下一个考虑的活动。使用新考虑的活动重复步骤 1 和步骤 2。如果没有剩余活动，则转到步骤 4。

第4步 ） 返回考虑的指标的并集。这些是将用于最大化吞吐量的活动指标。

Archi贪婪方法的结构
Archi贪婪方法的结构

代码说明

#include<iostream>
#include<stdio.h>
#include<stdlib.h>

#define MAX_ACTIVITIES 12

Archi贪婪方法的结构

代码说明：

  1. 包含的头文件/类
  2. 用户提供的最大活动数量。
using namespace std;

class TIME
{
    public:
    int hours;

    public: TIME()
    {
   	 hours = 0;
    }
};

Archi贪婪方法的结构

代码说明：

  1. 流操作的命名空间。
  2. TIME 类定义
  3. 一小时时间戳。
  4. TIME 默认构造函数
  5. 小时变量。
class Activity
{
    public:
    int index;
    TIME start;
    TIME finish;

    public: Activity()
    {
   	 start = finish = TIME();
    }
};

Archi贪婪方法的结构

代码说明：

  1. 来自活动的类定义
  2. 定义持续时间的时间戳
  3. 在默认构造函数中所有时间戳都初始化为 0
class Scheduler
{
    public:
    int considered_index,init_index;
    Activity *current_activities = new    Activity[MAX_ACTIVITIES];
    Activity *scheduled;

Archi贪婪方法的结构

代码说明：

  1. 调度程序类定义的第一部分。
  2. 考虑索引是扫描的起点 排列.
  3. 初始化索引用于分配随机时间戳。
  4. 使用 new 运算符动态分配活动对象数组。
  5. 调度指针定义了贪婪的当前基本位置。
Scheduler()
{
   	 considered_index = 0;
   	 scheduled = NULL;
...
...

Archi贪婪方法的结构

代码说明：

  1. 调度程序构造函数——调度程序类定义的第 2 部分。
  2. 考虑的索引定义了当前扫描的当前开始。
  3. 当前贪婪范围在开始时未定义。
for(init_index = 0; init_index < MAX_ACTIVITIES; init_index++)
 {
   		 current_activities[init_index].start.hours =
   			 rand() % 12;

   		 current_activities[init_index].finish.hours =
   			 current_activities[init_index].start.hours +
   				 (rand() % 2);

   		 printf("\nSTART:%d END %d\n",
   		 current_activities[init_index].start.hours
   		 ,current_activities[init_index].finish.hours);
 }
…
…

Archi贪婪方法的结构

代码说明：

  1. for 循环用于初始化当前安排的每个活动的开始时间和结束时间。
  2. 开始时间初始化。
  3. 结束时间初始化总是在开始时间之后或者正好在开始时间。
  4. 用于打印出分配的持续时间的调试语句。
	public:
   		 Activity * activity_select(int);
};

Archi贪婪方法的结构

代码说明：

  1. 第 4 部分——调度程序类定义的最后一部分。
  2. 活动选择函数以起点索引为基础，将贪婪任务划分为贪婪子问题。
Activity * Scheduler :: activity_select(int considered_index)
{
    this->considered_index = considered_index;
    int greedy_extent = this->considered_index + 1;
…
…

Archi贪婪方法的结构

  1. 使用范围解析运算符（::）提供函数定义。
  2. 所考虑的索引是通过值调用的索引。greedy_extent 是在所考虑的索引之后初始化的索引。
Activity * Scheduler :: activity_select(int considered_index)
{
    	while( (greedy_extent < MAX_ACTIVITIES ) &&
   	 ((this->current_activities[greedy_extent]).start.hours <
   		 (this->current_activities[considered_index]).finish.hours ))
    	{
   	 printf("\nSchedule start:%d \nfinish%d\n activity:%d\n",
   	 (this->current_activities[greedy_extent]).start.hours,
   	 (this->current_activities[greedy_extent]).finish.hours,
   	 greedy_extent + 1);
   	 greedy_extent++;
    	}
…
...

Archi贪婪方法的结构

代码说明：

  1. 核心逻辑——贪婪程度受限于活动数量。
  2. 在考虑的活动（由考虑的索引给出）完成之前，检查当前活动的开始时间是否可安排。
  3. 只要可能，就会打印可选的调试语句。
  4. 前进到活动数组的下一个索引
...
if ( greedy_extent <= MAX_ACTIVITIES )
    {

   	 return activity_select(greedy_extent);
    }
    else
    {
   	 return NULL;
    }
}

Archi贪婪方法的结构

代码说明：

  1. 条件检查是否已覆盖所有活动。
  2. 如果不是，你可以以考虑的索引作为当前点重新启动贪婪算法。这是一个贪婪地划分问题陈述的递归步骤。
  3. 如果是，它会返回给调用者，并且没有扩展贪婪的范围。
int main()
{
    Scheduler *activity_sched = new Scheduler();
    activity_sched->scheduled = activity_sched->activity_select(
   				activity_sched->considered_index);
    return 0;
}

Archi贪婪方法的结构

代码说明：

  1. 用于调用调度程序的主要函数。
  2. 实例化了新的 Scheduler。
  3. 活动选择函数返回一个活动类型的指针，贪婪任务结束后返回给调用者。

输出：

START:7 END 7

START:9 END 10

START:5 END 6

START:10 END 10

START:9 END 10

Schedule start:5 
finish6
 activity:3

Schedule start:9 
finish10
 activity:5

贪婪技术的局限性

它不适用于贪婪问题，因为像排序这样的每个子问题都需要一个解决方案。

在贪婪算法这类实践问题中，贪婪方法可能会出错；在最坏的情况下甚至会导致得不到最优解。

因此贪婪算法的缺点是不知道当前贪婪状态之前会发生什么。

下面描述了贪婪方法的缺点：

贪婪技术的局限性

在这里以树的形式显示的贪婪扫描中（值越高，贪婪程度越高），值 40 处的算法状态很可能将 29 作为下一个值。此外，其任务在 12 处结束。这相当于值 41。

但是，如果算法采取次优路径或采用征服策略，那么 25 之后将是 40，总体成本改善将达到 65，作为次优决策，其价值高出 24 分。

贪婪的例子 Algorithms

大多数网络算法都使用贪婪方法。下面列出了一些贪婪算法示例：

  • Prim 最小生成树算法
  • 旅行商问题
  • 图表 – 地图着色
  • Kruskal 最小生成树算法
  • Dijkstra 最小生成树算法
  • 图 – 顶点覆盖
  • 背包问题
  • 作业调度问题

总结

总而言之，本文定义了贪婪范式，展示了贪婪优化和递归如何帮助您获得最佳解决方案。贪婪算法被广泛应用于许多语言中的问题解决应用中，称为贪婪算法 Python、C、C#、PHP、 Java等，将贪婪算法实例中的活动选择描述为利用贪婪方法实现最大吞吐量的策略问题，最后说明了使用贪婪方法的缺点。

你可能会喜欢：