Skip to content

算法图解 贪婪算法

教室调度问题

假设有如下课程表,你希望将尽可能多的课程安排在某间教室上。

课程开始时间结束时间
美术09:00 AM10:00 AM
英语09:30 AM10:30 AM
数学10:00 AM11:00 AM
计算机10:30 AM11:30 AM
音乐11:00 AM12:00 AM

算法:

  1. 选出结束最早的课,它就是在这间教室上的第一堂课。

  2. 接下来,必须选在在上一堂课结束后才开始的课。同样,选择结束最早的课。

  3. 重复上面的步骤

背包问题

假设你是个贪婪的小偷,背着可装 35 磅重东西的背包,在商场伺机盗窃各种可装入背包的商品。

贪婪策略:

  1. 盗窃可装入背包的最贵商品。

  2. 再盗窃可装入背包的最贵商品,以此类推。

但有可能不是最优解

旅行商问题的近似求解

  1. 随机选择出发城市。

  2. 选择还没有去的最近城市。

总结

  • 贪婪算法寻找局部最优解,企图以这种方式获得全局最优解

  • 对于 NP 完全问题,还没有找到快速解决方案

  • 面临 NP 完全问题时,最佳的做法是找出近似算法

  • 贪婪算法易于实现、运行速度快,是不错的近似算法

Page Layout Max Width

Adjust the exact value of the page width of VitePress layout to adapt to different reading needs and screens.

Adjust the maximum width of the page layout
A ranged slider for user to choose and customize their desired width of the maximum width of the page layout can go.

Content Layout Max Width

Adjust the exact value of the document content width of VitePress layout to adapt to different reading needs and screens.

Adjust the maximum width of the content layout
A ranged slider for user to choose and customize their desired width of the maximum width of the content layout can go.