四、 贪心策略的理论基础--矩阵胚

　　正如前文所说的那样，贪心策略是最接近人类认知思维的一种解题策略。但是，越是显而易见的方法往往越难以证明。下面我们就来介绍贪心策略的理论--矩阵胚。

　　"矩阵胚"理论是一种能够确定贪心策略何时能够产生最优解的理论，虽然这套理论还很不完善，但在求解最优化问题时发挥着越来越重要的作用。

　　【定义3】 矩阵胚是一个序对M=[S，I] ，其中S是一个有序非空集合，I是S的一个非空子集，成为S的一个独立子集。

　　如果M是一个N×M的矩阵的话，即



　　若M是无向图G的矩阵胚的话，则S为图的边集，I是所有构成森林的一组边的子集。

　　如果对S的每一个元素X（X∈S）赋予一个正的权值W（X），则称矩阵胚M=（S，I）为一个加权矩阵胚。

　　适宜于用贪心策略来求解的许多问题都可以归结为在加权矩阵胚中找一个具有最大权值的独立子集的问题，即给定一个加权矩阵胚，M=（S，I），若能找出一个独立且具有最大可能权值的子集A，且A不被M中比它更大的独立子集所包含，那么A为最优子集，也是一个最大的独立子集。

　　我们认为，针对绝大多数的信息学问题，只要它具备了"矩阵胚"的结构，便可用贪心策略求解。矩阵胚理论对于我们判断贪心策略是否适用于某一复杂问题是十分有效的。

　　五、 几种典型的贪心算法

　　贪心策略在图论中有着极其重要的应用。诸如Kruskal、 Prim、 Dijkstra等体现"贪心"思想的图形算法更是广泛地应用于树与图的处理。下面就分别来介绍Kruskal算法、Prim算法和Dijkstra算法。

　　Ⅰ、库鲁斯卡尔（Kruskal）算法