贪心算法
如何理解贪心算法
-
例子: 假设我们有一个可以容纳 100kg 物品的背包，可以装各种物品。我们有以下 5 种豆子，每种豆子的总量和总价- 值都各不相同。为了让背包中所装物品的总价值最大，我们如何选择在背包中装哪些豆子？每种豆子又该装多少呢？
- 单价排序 + 由高到低来装
贪心算法
- 当我们看到这类问题时,首先要联想到贪心算法
- 针对一组数据,我们给定限制条件和期望值,希望从中选出几个数据,在满足限制条件后,选最大的期望值。
- 在对限制值等贡献量情况下,对期望值贡献最大的数据
- 从实践的角度来说，大部分能用贪心算法解决的问题，贪心算法的正确性都是显而易见的，也不需要严格的数学推导证明。
实际上,用贪心算法解决问题的思路,不能总给出最优解。
- 有权图找最短路径
- Greedy不工作的原因就是 前面的选择会影响后面的选择 所以会很糟糕
贪心算法实战分析
- 分糖果 m个糖果和n个小孩.（m < n ）
- 分析是 限制条件:m<n, 期望值:更多的小孩子能吃到糖果
- 先从需求小的孩子满足,然后再是需要大的孩子
- 钱币找零
- 限制条件:支付k元 期望值:用最少的纸币
- 定是先用面值最大的来支付，如果不够，就继续用更小一点面值的，以此类推，最后剩下的用 1 元来补齐。
- 区间覆盖
- 限制条件: 最小左区间值和最大右区间值 期望值: 容纳的区间数最多
- 霍夫曼编码 (数据压缩)
-
1000个字符的文件,每个字符占1个byte(1bye=8bits) 存储1000个字符就一共需要8000个bits
-
假设我们通过统计分析发现，这 1000 个字符中只包含 6 种不同字符，假设它们分别是 a、b、c、d、e、f。而 3 个二进制位（bit）就可以表示 8 个不同的字符，所以，为了尽量减少存储空间，每个字符我们用 3 个二进制位来表示。那存储这 1000 个字符只需要 3000bits 就可以了，比原来的存储方式节省了很多空间。不过，还有没有更加节省空间的存储方式呢？
-
霍夫曼编码不仅会考察文本中有多少个不同的字符,还会考察每个字符出现的频率
-
选择不同长度的编码,视图用不等长的编码方法,进一步增加压缩效率
-
每个字符看作一个节点，并且附带着把频率放到优先级队列中。我们从队列中取出频率最小的两个节点 A、B，然后新建一个节点 C，把频率设置为两个节点的频率之和，并把这个新节点 C 作为节点 A、B 的父节点。最后再把 C 节点放入到优先级队列中。重复这个过程，直到队列中没有数据。
a(000).....f(101)
Spanning-Tree
-
连通性: 原始图中的每个顶点都包含在跨度树中,且跨度树中任意的两个顶点之间存在路径。
-
无环性: 跨度树不包含任何环。如果它包含环，就不再是一棵树，因为树是一种特殊的图，不包含环。
-
最小边数: n个顶点的树,有n-1条边。
-
简单跨度树的唯一性：对于简单图（没有多重边或自环的图），只存在一棵简单的跨度树，它包含所有顶点。
-
加权跨度树：如果图是加权的，即每条边都有一个相关的成本或权重，那么可以找到一棵最小生成树（MST）。MST是一棵总边权重最小的跨度树。寻找MST的常见算法包括Kruskal算法和Prim算法。
Prim's Selection rule
-
选择树节点和非树节点之间的最小权重边,并将其添加到树中。
-
主要关键步骤:
-
选择一个顶点作为树节点
-
当没有树顶点: 如果没有边连接树节点和非树节点: 返回"没有跨度树" 选择一个最小权重边在树节点和非树节点之间 将添加选择的边和它的顶点到树里
-
返回树
-
-
Prim's算法的实现步骤:
- 初始化:
- 选择图中的任意一个顶点作为起始点,将其加入到树的几何中
- 创建一个最小堆,用于存储所有连接树集合和非树集合顶点的边。
- 构建最小生成树:
- 从优先队列中取出权重最小的边（即堆顶元素），这条边连接了一个已经在树集合中的顶点和一个尚未在树集合中的顶点。
- 如果这条边的权重为0（表示没有权重，即已经是一个顶点），则算法结束，最小生成树构建完成。
- 将这条边以及它的非树顶点从优先队列中移除，并将其加入到最小生成树的集合中。
- 更新优先队列，将新加入的顶点与树集合中所有其他顶点之间的边加入队列（如果这些边的权重不为0。
- 重复过程2,直到所有顶点都被加入到最小生成树的集合中
- 输出结果: 所有顶点都包含在最小生成树中时,算法结束
type Graph struct {
Verxs int
Data []rune
Weight [][]int
}
func main() {
inf := math.MaxInt32
// 构建一张图
vertices := []rune{'A', 'B', 'C', 'D', 'E', 'F'}
v_len := len(vertices)
weight := [][]int{
{inf, 5, 6, 4, inf, inf}, //A
{5, inf, 1, 2, inf, inf}, //B
{6, 1, inf, 2, 5, 3}, //C
{4, 2, 2, inf, inf, 4}, //D
{inf, inf, 5, inf, inf, 4}, //E
{inf, inf, 3, 4, 4, inf}, // F
}
graph := NewGraph(v_len)
// 创建图
CreateGraph(graph, v_len, vertices, weight)
fmt.Println("图的邻接矩阵:")
ShowGraph(graph)
fmt.Println("最小生成树的顶点以及权值:")
Prim(graph, 0)
}
func NewGraph(v_len int) *Graph {
return &Graph{
Verxs: v_len,
Data: make([]rune, v_len),
Weight: make([][]int, v_len),
}
}
func CreateGraph(graph *Graph, v_len int, vetices []rune, weight [][]int) {
for i := 0; i < v_len; i++ {
graph.Data[i] = vetices[i]
graph.Weight[i] = make([]int, v_len)
copy(graph.Weight[i], weight[i])
}
fmt.Println(graph)
}
func ShowGraph(graph *Graph) {
for _, link := range graph.Weight {
fmt.Println(link)
}
}
// 循环 graph.verxs-1 次，每次迭代添加一个顶点到最小生成树中。
func Prim(graph *Graph, v int) {
// 用于标记顶点是否被访问
visited := make([]int, graph.Verxs)
visited[v] = 1
//
var h1, h2 int
minWeight := math.MaxInt32
// 控制边数 n个顶点 n-1条边
for k := 0; k < graph.Verxs-1; k++ {
// 开始迭代 访问过的顶点
for i := 0; i < graph.Verxs; i++ {
// 访问未访问过的顶点
for j := 0; j < graph.Verxs; j++ {
if visited[i] == 1 && visited[j] == 0 && graph.Weight[i][j] < minWeight {
minWeight = graph.Weight[i][j]
// 记录目前权值最小的两个顶点
h1 = i
h2 = j
}
}
}
fmt.Printf("<%c, %c> 权值：%d\n", graph.Data[h1], graph.Data[h2], minWeight)
visited[h2] = 1
minWeight = math.MaxInt32
}
}
实际应用
-
通信网络设计：在通信网络中，如何以最小的成本连通所有的节点是一个关键问题。最小生成树可以帮助设计者优化网络结构，降低建设和维护成本。
-
线路规划：在城市道路、铁路或管道的规划中，最小生成树可以帮助确定最佳的连接方式，以降低资源和成本的使用。
-
集成电路设计：在芯片设计中，最小生成树可以用于布线，以最小化电路的总长度和延迟，从而提高电路的性能和效率。