算法-05-贪心算法

贪心算法 (Greedy Algorithms)
- 贪心技术 (Greedy Technique)
- 贪心策略的应用 (Applications of the Greedy Strategy)
  - 找零问题 (Change-Making Problem)
  - 活动选择问题 (Interval Scheduling Problem)
  - 最小生成树 (Minimum Spanning Tree, MST)
  - 单源最短路径 (Single-Source Shortest Paths)
区间调度 (Interval Scheduling)
- 区间调度问题 (Interval Scheduling Problem)
- 贪心算法 (Greedy Algorithms)
- 证明 (Proof)
区间划分 (Interval Partitioning)
- 问题描述 (Problem Description)
- 贪心算法 (Greedy Algorithm)
- 证明 (Proof)
最小生成树 (Minimum Spanning Tree, MST)
- 定义 (Definition)
- 应用 (Applications)
- 算法 (Algorithms)
  - Prim算法 (Prim's Algorithm)
  - Kruskal算法 (Kruskal's Algorithm)
- 复杂度 (Complexity)
单源最短路径 (Single-Source Shortest Paths)
- 问题描述 (Problem Description)
- 应用 (Applications)
- 算法 (Algorithms)
  - Dijkstra算法 (Dijkstra's Algorithm)
- 复杂度 (Complexity)
参考文献 (References)

1. 贪心算法 (Greedy Algorithms)

贪心技术 (Greedy Technique)

优化问题的算法通常经过一系列步骤，每一步都有一组选择。
贪心算法总是选择当前看起来最好的选项。
即，它在局部做出最优选择，希望这个选择能导致全局最优解。
对于某些问题，每个实例都能获得最优解。
对于大多数优化问题，贪心算法无法保证获得最优解。

贪心策略的应用 (Applications of the Greedy Strategy)

找零问题 (Change-Making Problem)

问题描述：给定无限数量的硬币面值 ( $d_1$ > $d_2$ > $\cdots$ > $d_m$ )，使用最少数量的硬币找零。
示例：给定货币面值为1, 5, 10, 20, 50，使用最少的硬币支付95。
贪心算法：
- 每一步选择当前面值最大的硬币，直到总金额达到目标值。

cpp

#include<iostream>
#include<vector>

using namespace std;

void ChangeMaking(int totalAmount, vector<int> coins){
	vector<int> result(coins.size(), 0);//用0初始化
	sort(coins.begin(), coins.end(), greater<int>());//先将可用面值降序排列
	
	for(int i = 0; i < coins.size(); i++)
	{
		if(totalAmount <= coins[i]){
			result[i] = totalAmount / coins[i];
			totalAmount %= coins[i];
		}
	}
	cout << "最少所需各个硬币的数量为：" <<endl;
	//遍历result数组输出结果
	for(int i = 0; i <= coins.size(); i++)
	{
		if(result[i] > 0)
			cout << "Coin_" << coins[i] << ": " << result[i] <<endl;
	}
}

//一个用于测试的示例main函数
int main(){
	vector<int> coins = {1, 5, 10, 20, 50};
	int totalAmount  = 234;
	ChangeMaking(totalAmount, coins);
	return 0;
}

活动选择问题 (Interval Scheduling Problem)

问题描述：你有一个资源，它可能是一个讲座室，一个超级计算机或一个电子显微镜，很多人请求在一段时间内使用这个资源。
贪心算法：
- 按活动结束时间的升序考虑活动。每次选择下一个与已选择活动不冲突的活动。

最小生成树 (Minimum Spanning Tree, MST)

问题描述：给定一个无向图 (G = (V, E)) 及其边的权重 (we)，找到一个权重总和最小的生成树 ( (V, T) )。
应用：
- 网络设计（通信、电力、计算机等）
- 聚类分析
- 微生物研究
- 图像分割

单源最短路径 (Single-Source Shortest Paths)

问题描述：给定一个加权连通图 (G = (V, E))，找到从源顶点 (s) 到所有其他顶点的最短路径。

2. 区间调度 (Interval Scheduling)

区间调度问题 (Interval Scheduling Problem)

问题描述：资源请求的形式为：我可以从时间 (s) 开始使用资源到时间 (f) 吗？
目标是找到最大数量的相互兼容的活动子集。
活动的定义：活动 (j) 从 (sj) 开始，到 (fj) 结束。
兼容性：如果两个活动不重叠，则它们是兼容的。

贪心算法 (Greedy Algorithms)

按某种顺序考虑活动。只要活动与已选择的活动兼容，就选取该活动。
- 按开始时间升序排序：考虑按开始时间的升序排序活动 (sj)。
- 按结束时间升序排序：考虑按结束时间的升序排序活动 (fj)。
- 按间隔长度升序排序：考虑按间隔长度的升序排序 (fj - sj)。
- 按冲突最少排序：对于每个活动，计算冲突活动的数量 (cj)。按冲突的升序安排活动。

证明 (Proof)

定理：选择最早结束的活动是最优的。
证明思路：
- 假设贪心选择的活动集合为 (i1, i2, \ldots, ik)，最优解的活动集合为 (j1, j2, \ldots, jm)。
- 假设贪心解不是最优的，考虑替换贪心解中的某个活动，证明矛盾。

3. 区间划分 (Interval Partitioning)

问题描述 (Problem Description)

问题描述：许多相同的资源可用，目标是使用最少的资源来安排所有请求。
示例：最小化所需的教室数量以安排所有讲座，使得同一时间的讲座不在同一个教室。

贪心算法 (Greedy Algorithm)

按开始时间升序考虑讲座：将讲座分配到任何兼容的教室。
算法步骤：
1. 将讲座按开始时间排序 (s1 \le s2 \le \cdots \le sn)。
2. 初始化教室数量 (d \leftarrow 0)。
3. 对每个讲座 (j)：
  - 如果讲座 (j) 与某个教室兼容，则安排在该教室。
  - 否则，分配一个新的教室 (d + 1)，并将讲座 (j) 安排在教室 (d + 1)。
  - 更新教室数量 (d \leftarrow d + 1)。

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <tuple>

using namespace std;

// 定义会议时间区间
struct Interval {
    int start;
    int end;
    int index;
    Interval(int s, int e, int i) : start(s), end(e), index(i) {}
};

// 比较函数用于按开始时间排序
bool compareInterval(const Interval &i1, const Interval &i2) {
    return i1.start < i2.start;
}

// 函数用于处理输入数据
vector<Interval> readIntervals() {
    int n;
    cout << "Enter the number of meetings: ";
    cin >> n;

    vector<Interval> intervals;
    cout << "Enter the start and end times of the meetings:" << endl;
    for (int i = 0; i < n; ++i) {
        int s, f;
        cin >> s >> f;
        intervals.push_back(Interval(s, f, i));
    }

    return intervals;
}

// 函数用于计算最少会议室数量并输出具体安排
void minMeetingRooms(const vector<Interval>& intervals) {
    if (intervals.empty()) {
        cout << "0" << endl;
        return;
    }

    // 按开始时间排序
    vector<Interval> sortedIntervals = intervals;
    sort(sortedIntervals.begin(), sortedIntervals.end(), compareInterval);

    // 初始化一个最小堆和一个结果向量
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap;
    vector<vector<tuple<int, int, int>>> rooms;

    // 将第一个会议的结束时间和索引加入堆中
    minHeap.push(make_pair(sortedIntervals[0].end, 0));
    rooms.push_back({make_tuple(sortedIntervals[0].start, sortedIntervals[0].end, sortedIntervals[0].index)});

    // 遍历剩余的会议
    for (size_t i = 1; i < sortedIntervals.size(); ++i) {
        int start = sortedIntervals[i].start;
        int end = sortedIntervals[i].end;
        int index = sortedIntervals[i].index;

        if (start >= minHeap.top().first) {
            int roomIndex = minHeap.top().second;
            minHeap.pop();
            minHeap.push(make_pair(end, roomIndex));
            rooms[roomIndex].push_back(make_tuple(start, end, index));
        } else {
            int newRoomIndex = rooms.size();
            minHeap.push(make_pair(end, newRoomIndex));
            rooms.push_back({make_tuple(start, end, index)});
        }
    }

    // 输出需要的最少会议室数量
    cout << rooms.size() << endl;

    // 输出每个会议室的安排
    for (size_t i = 0; i < rooms.size(); ++i) {
        cout << "Room " << i + 1 << ": ";
        for (const auto& meeting : rooms[i]) {
            cout << "[" << get<0>(meeting) << ", " << get<1>(meeting) << "] ";
        }
        cout << endl;
    }
}

int main() {
    vector<Interval> intervals = readIntervals();
    minMeetingRooms(intervals);
    return 0;
}

证明 (Proof)

观察：贪心算法从不将两个不兼容的讲座安排在同一个教室。
定理：贪心算法是最优的。
- 证明思路：证明教室数量 (d) 等于最大重叠活动的数量（深度）。

4. 最小生成树 (Minimum Spanning Tree, MST)

定义 (Definition)

一个无向图的生成树是一个子图，它是连通的、无环的，并且包含所有顶点。
最小生成树是权重总和最小的生成树。

应用 (Applications)

网络设计：通信、电力、计算机等网络的设计。
聚类分析：例如数据分类。
微生物研究：例如细菌种类的分类。
图像分割：例如将图像分割成不同的区域。

算法 (Algorithms)

Prim算法 (Prim's Algorithm)

基本思想：从一个顶点开始，逐步扩展树，直到所有顶点都被包含。
算法步骤：
1. 从一个任意顶点开始，将其作为初始树 (T1)。
2. 每次从当前树中选择一条最小权重的边，将另一个顶点加入树中。
3. 重复直到所有顶点都被包含。
复杂度：
- 使用权重矩阵/邻接表表示图和数组实现的优先队列：时间复杂度为 $O(|V|^2)$ 。
- 使用邻接表表示图和二进制堆实现的优先队列：时间复杂度为 $O(|E| \log |V|)$ 。

Kruskal算法 (Kruskal's Algorithm)

基本思想：依次添加最小权重的边，前提是不形成环。
算法步骤：
1. 将所有边按权重升序排序。
2. 从最小权重的边开始，依次检查，如果加入该边不形成环，则将其加入生成树。
3. 重复直到生成树包含 $(V-1)$ 条边。
复杂度：
- 使用联合查找数据结构（Union-Find Data Structure）实现：时间复杂度为 $O(|E| \log |E|)$ 。

5. 单源最短路径 (Single-Source Shortest Paths)

问题描述 (Problem Description)

问题描述：给定一个加权连通图

$(G = (V, E))$ ，找到从源顶点 $(s)$ 到所有其他顶点的最短路径。

应用 (Applications)

项目评估与审查技术 (PERT)/关键路径方法 (CPM)：用于项目管理。
地图路由：例如GPS导航系统。
无缝裁剪：例如图像处理中的能量最小化。
城市交通规划：例如最短路径规划。
VLSI芯片的优化管道：用于芯片设计。
网络路由协议：例如Internet中的路由选择。

算法 (Algorithms)

Dijkstra算法 (Dijkstra's Algorithm)

适用条件：适用于无向图和有向图，且权重为非负数。
基本思想：类似于Prim算法，但计算方式不同。每次选择具有最小路径和的顶点，并更新其邻接顶点的最短路径。
算法步骤：
1. 初始化源顶点的距离为0，其他顶点的距离为无穷大。
2. 从未处理顶点中选择距离最小的顶点，标记为已处理。
3. 更新该顶点的所有邻接顶点的距离。
4. 重复步骤2和3，直到所有顶点都被处理。
复杂度：
- 使用权重矩阵/邻接表表示图和数组实现的优先队列：时间复杂度为 $O(|V|^2)$ 。
- 使用邻接表表示图和二进制堆实现的优先队列：时间复杂度为 $O(|E| \log |V|)$ 。

Edge	Weight
(a, e)	1
(a, b)	3
(b, c)	4
(f, d)	6
(e, f)	7

参考文献 (References)

Anany Levitin, Introduction to the Design and Analysis of Algorithms，第9章
Jon Kleinberg, Éva Tardos, Algorithm Design，第5章

目录

1. 贪心算法 (Greedy Algorithms)

贪心技术 (Greedy Technique)

贪心策略的应用 (Applications of the Greedy Strategy)

找零问题 (Change-Making Problem)

活动选择问题 (Interval Scheduling Problem)

最小生成树 (Minimum Spanning Tree, MST)

单源最短路径 (Single-Source Shortest Paths)

2. 区间调度 (Interval Scheduling)

区间调度问题 (Interval Scheduling Problem)

贪心算法 (Greedy Algorithms)

证明 (Proof)

3. 区间划分 (Interval Partitioning)

问题描述 (Problem Description)

贪心算法 (Greedy Algorithm)

证明 (Proof)

4. 最小生成树 (Minimum Spanning Tree, MST)

定义 (Definition)

应用 (Applications)

算法 (Algorithms)

Prim算法 (Prim's Algorithm)

Kruskal算法 (Kruskal's Algorithm)

5. 单源最短路径 (Single-Source Shortest Paths)

问题描述 (Problem Description)

应用 (Applications)

算法 (Algorithms)

Dijkstra算法 (Dijkstra's Algorithm)

参考文献 (References)