基本信息

---

下载

文档摘要

---

第7章贪心法;7.1.1什么是贪心法;例如，求解一个带权无向图G中从顶点i到顶点j（i≠j）的最短路径，可以分析出这样的最短路径一定是简单路径，所以约束条件为：;贪心法从问题的某一个初始解{}出发，采用逐步构造最优解的方法向给定的目标前进，每一步决策产生n-元组解（x0，x1，…，xn-1）的一个分量。

贪心法每一步上用作决策依据的选择准则被称为最优量度标准（或贪心准则），也就是说，在选择解分量的过程中，添加新的解分量xk后，形成的部分解（x0，x1，…，xk)不违反可行解约束条件。

每一次贪心选择都将所求问题简化为规模更小的子问题，并期望通过每次所做的局部最优选择产生出一