文章目录

• 算法思路
• 应用实例
• 仿真
• Ref.

算法思路

贪心算法一般按如下步骤进行：

建立数学模型来描述问题。

把求解的问题分成若干个子问题。

对每个子问题求解，得到子问题的局部最优解。

把子问题的解局部最优解合成原来解问题的一个解。

贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。贪心算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择，就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解。虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪心算法不要回溯。

对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。

要确定一个问题是否适合用贪心算法求解，必须证明每一步所作的贪心选择最终导致问题的整体最优解。证明的大致过程为：首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始，做了贪心选择后，原问题简化为规模更小的类似子问题。然后用数学归纳法证明通过每一步做贪心选择，最终可得到问题的整体最优解。

应用实例

例如，平时购物找零钱时，为使找回的零钱的硬币数最少，不要求找零钱的所有方案，而是从最大面值的币种开始，按递减的顺序考虑各面额，先尽量用大面值的面额，当不足大面值时才去考虑下一个较小面值，这就是贪心算法。

仿真

% PSO % Author: Zhao-Jichao % Date: 2021-10-06 clc clear%% n = 20 ; % 用于记录点数x = zeros(1,n) ; % 产生一个与经过点数相同的行向量 y = zeros(1,n) ;best = 1:1:n; % 生成一个用来存储点顺序的矩阵 handle = 1:1:n;for i = 1 : (n) % 生成n个随机数x(i) = rand * 20 ; y(i) = rand * 20 ; endd = zeros(n) ; for i = 1 : n for j = 1 : nd(i,j) = sqrt( ( x(i) - x(j) ) ^ 2 + ( y(i) - y(j) ) ^ 2) ; % 距离矩阵end endbest(1) = 1; % 默认起点 num = 1; for a = 1:(n-2) % 需要n-2次判断handle(:,1)=[]; % 上一次最优点的数据裁掉dis = zeros(1,(n-a)); % 用来存剩下各个点的距离for b = 1:(n-a) % 用来获取剩下各个点的距离dis(b) = d (num , handle(b)); endnum1 = find( dis == min(dis) ); % 得到最优点所在检索t = handle(1); % 将最优点与最前面的点位置进行交换 handle(1) = handle(num1);handle(num1) = t;num = handle(1); % 获取下次进行操作的数best(a+1) = handle(1); % 将最优点存入best数组 endbest(n) = handle(num1); % 补上最后一个点plot(x(best),y(best),'-+') ; % 用'+'标出点并用实线连接得到最优路径 grid on

Ref.

贪心算法-百度百科

MATLAB实现贪心算法

总结

以上是生活随笔为你收集整理的【控制】贪心算法（GA，Greedy Algorithm）及 Matlab 实现的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。