2023-03-03  阅读(402)
原文作者:gofuncchan 原文地址:https://blog.csdn.net/gofuncchan

贪心算法的思想

即对于目标T,对于达成它的每一局部都选择最优选项,直到满足或最终近似满足为止,最终结果或许不是全局最优解,但应该是近似最优解,因为它足够简单。

每一步都采取局部最优做法!
贪婪算法大多时候都是近似最优算法!

贪心算法的三步走:

第一步:明确到底什么是最优解?
第二步:明确什么是子问题的最优解?
第三步:分别求出子问题的最优解再堆叠出全局最优解?

贪心算法的前提:

  • 原问题复杂度过高;
  • 求全局最优解的数学模型难以建立;
  • 求全局最优解的计算量过大;
  • 没有太大必要一定要求出全局最优解,“比较优”就可以。
    以上情况几乎99.99999999999%就要使用贪心算法的思想来解决问题!

分解子问题的方法:

1.按串行任务分:时间串行的任务,按子任务来分解,即每一步都是在前一步的基础上再选择当前的最优解。
2.按规模递减分:规模较大的复杂问题,可以借助递归思想,分解成一个规模小一点点的问题,循环解决,当最后一步的求解完成后就得到了所谓的“全局最优解”。
3.按并行任务分:这种问题的任务不分先后,可能是并行的,可以分别求解后,再按一定的规则(比如某种配比公式)将其组合后得到最终解。

如何知道贪心算法结果逼近全局最优解?

正因为有些问题很难求到全局最优解,才有贪心算法,它需要考虑成本、速度、价值: 成本:耗费多少资源,花掉多少编程时间。 速度:计算量是否过大,计算速度能否满足要求。 价值:得到了最优解与次优解是否真的有那么大的差别,还是说差别可以忽略。

例题

0-1背包问题 有一个背包,最多能承载150斤的重量,现在有7个物品, 重量分别为[35, 30, 60, 50, 40, 10, 25], 它们的价值分别为[10, 40, 30, 50, 35, 40, 30], 每个物品要么选择要么放弃, 应该如何选择才能使得我们的背包背走最多价值的物品?

解法:
  • 第一步:明确到底什么是最优解? —— 在重量限制内,价值最大的就是最优解;

  • 第二步:明确什么是子问题的最优解?这就是"局部最优解"

    • 方案一:每一次都尽量选择当前价值最高的物品
    • 方案二:每次尽量选择重量最小的物品
    • 方案三:每次尽量选择价值密度高的物品,即单位重量价值高的物品
  • 第三步:分别求出子问题的最优解再堆叠出全局最优解?

解题步骤及Go语言描述:

方案一:按照制订的规则(价值)进行计算,数组索引顺序是:3 1 5 4 ;最终的总重量是:130 ;最终的总价值是:165。
方案二:按照制订的规则(重量)进行计算,数组索引顺序是:5 6 1 0 4 ;最终的总重量是:140;最终的总价值是:155。可以看到,重量优先是没有价值优先的策略更好。
方案三:按照制订的规则(单位密度)进行计算,数组索引顺序是:5 1 6 3 4;最终的总重量是:150;最终的总价值是:170。可以看到,单位密度这个策略比之前的价值策略和重量策略都要好。

    type good struct {
        // name   string
        weight int
        price  int
        status int // 0未选中,1已选中
    }
    
    var maxWeight = 150
    var goods = []good{
        good{35, 10, 0},
        good{30, 40, 0},
        good{60, 30, 0},
        good{50, 50, 0},
        good{40, 35, 0},
        good{10, 40, 0},
        good{25, 30, 0},
    }
    
    // 解法一:每一次都尽量选择当前价值最高的物品
    // 按照制订的规则(价值)进行计算,数组索引顺序是:3 1 5 4 ;最终的总重量是:130 ;最终的总价值是:165。
    func GreedyKnapsack1(goods []good, maxW int) (totalP, totalW int) {
        // 物品总数
        n := len(goods)
        // 选物品
        for totalW <= maxW {
            // 选出余下价格最大的物品
            maxPIndex := -1
            maxPrice := goods[0].price
            for i := 0; i < n; i++ {
                if goods[i].status == 0 && goods[i].price > maxPrice {
                    maxPIndex = i
                    maxPrice = goods[i].price
                }
            }
            // 如计算超出重量则退出
            if totalW+goods[maxPIndex].weight > maxW {
                break
            }
            // 累计
            goods[maxPIndex].status = 1
            totalW += goods[maxPIndex].weight
            totalP += goods[maxPIndex].price
            fmt.Println("select good:", goods[maxPIndex], ",index:", maxPIndex, ",total weight:", totalW)
        }
        fmt.Println("goods:", goods)
    
        return
    
    }
    
    // 解法二:每次尽量选择重量最小的物品
    // 按照制订的规则(重量)进行计算,数组索引顺序是:5 6 1 0 4 ;最终的总重量是:140;最终的总价值是:155。可以看到,重量优先是没有价值优先的策略更好。
    func GreedyKnapsack2(goods []good, maxW int) (totalP, totalW int) {
        // 物品总数
        n := len(goods)
        // 选物品
        for totalW <= maxW {
            minWIndex := -1
            minWeight := math.MaxInt64
            // 选出余下重量最小的
            for i := 0; i < n; i++ {
                if goods[i].status == 0 && goods[i].weight <= minWeight {
                    minWIndex = i
                    minWeight = goods[i].weight
                }
            }
    
            // 如计算超出重量则退出
            if totalW+goods[minWIndex].weight > maxW {
                break
            }
    
            // 累计
            goods[minWIndex].status = 1
            totalW += goods[minWIndex].weight
            totalP += goods[minWIndex].price
            fmt.Println("select good:", goods[minWIndex], ",index:", minWIndex, ",total weight:", totalW)
        }
        fmt.Println("goods:", goods)
    
        return
    }
    
    // 解法三:每次尽量选择价值密度高的物品,即单位重量价值高的物品
    // 按照制订的规则(单位密度)进行计算,数组索引顺序是:5 1 6 3 4;最终的总重量是:115;最终的总价值是:160。可以看到,单位密度这个策略比之前的价值策略和重量策略都要好。
    func GreedyKnapsack3(goods []good, maxW int) (totalP, totalW int) {
    
        // 物品总数
        n := len(goods)
        // 选物品
        for totalW <= maxW {
            maxDIndex := -1
            maxDensity := 0.0
            // 选出余下价格密度最高的
            for i := 0; i < n; i++ {
                if goods[i].status == 0 && float64(goods[i].price) / float64(goods[i].weight) > maxDensity {
                    maxDIndex = i
                    maxDensity = float64(goods[i].price) / float64(goods[i].weight)
                }
            }
            // fmt.Println("maxDIndex:",maxDIndex)
            // fmt.Println("maxDensity:",maxDensity)
    
            // 如计算超出重量则退出
            if totalW+goods[maxDIndex].weight > maxW {
                break
            }
    
            // 累计
            goods[maxDIndex].status = 1
            totalW += goods[maxDIndex].weight
            totalP += goods[maxDIndex].price
            fmt.Println("select good:", goods[maxDIndex], ",index:", maxDIndex, ",total weight:", totalW)
        }
        fmt.Println("goods:", goods)
    
        return
    }

很显然大多数方案不是全局最优解,但只要是近似最优解。优点就是计算简单,对于那些计算精确解需要极大代价的算法来说,贪心算法求解出近似解是不错的选择。

阅读全文
  • 点赞