贪心算法

来自计算思维百科
跳转至: 导航搜索
贪心算法.png

贪心算法是求解问题的一种方法,它的基本思想是把求解问题的任务分解为若干个步骤,而算法在每一步骤的决定是“短视的”,即该步骤所采取的行动或者选择是当前情况下最好的,当然这不能保证最后是最好的。贪心算法不是对所有问题都能得到整体最优解。

基本概念

通过一系列步骤来构造问题的解,每一步都是对已构造的部分解的一个扩展,直到获得问题的完整解。

贪婪算法中,每一步“贪婪地” 选择最好的部分解,但不顾及这样选择对整体的影响(局部最优),因此得到的全局解不一定最好的解,但对许多问题它能产生整体最优解

应用范围

贪心算法不是对所有问题都能得到整体最优解,但对范围相当广泛的许多问题都能产生整体最优解或整体最优解的近似解。

使用方法及步骤

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

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

3.对每一子问题求解,得到子问题的局部最优解。

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

应用1- 找零钱

在找零钱的时候,如果要找补36元,我们会先找一个距离36最近的零钱20元,在剩下的16元中,再找一个最近的零钱就是10元,在剩下的6元中,再找一个零钱5元,最后剩下1元。这样得到的零钱的个数往往是最少的。

应用2- 过十字路口

案例:我们在过十字路口的时候,要从到对角线的那个街区时,我们也会使用贪婪算法——哪边的绿灯先亮了我们就先过到那边去,然后再转身90度等红灯再过街。这个策略最突出的优点是效率高,方案容易实施。

可以体现的计算思维

贪心算法是一种简单的解决问题的方法,虽然不能保证得到全局最优的解,但往往得到的解都是比较令人满意的,体现了计算思维的优化特点。