柚子快報(bào)激活碼778899分享：使用rust學(xué)習(xí)基本算法（二）
柚子快報(bào)激活碼778899分享：使用rust學(xué)習(xí)基本算法（二）
使用rust學(xué)習(xí)基本算法（二）
貪心算法
貪心算法是一種在每一步選擇中都采取當(dāng)前狀態(tài)下最優(yōu)的選擇，以期望通過一系列的局部最優(yōu)解來達(dá)到全局最優(yōu)解的算法策略。它的主要特點(diǎn)是局部最優(yōu)解的選擇，希望通過這種方式來解決某些優(yōu)化問題。但需要注意的是，貪心算法并不保證能夠得到全局最優(yōu)解，它的正確性需要根據(jù)具體問題來分析。
貪心算法的基本思路
建立數(shù)學(xué)模型：將問題抽象成數(shù)學(xué)問題。定義局部最優(yōu)解策略：確定在每一步選擇中應(yīng)該遵循的規(guī)則，以確保每一步都是當(dāng)前狀態(tài)下的最優(yōu)選擇。求解和構(gòu)建全局解：通過不斷地采取局部最優(yōu)解，累積最終求得全局最優(yōu)解或者接近全局最優(yōu)解的答案。
貪心算法的特點(diǎn)
簡(jiǎn)單高效：算法通常較為簡(jiǎn)單，且執(zhí)行效率高。局部最優(yōu)解：每一步都采取當(dāng)前看來最優(yōu)的選擇。不可回溯：一旦選擇，就不會(huì)改變。適用范圍有限：只適用于能夠通過局部最優(yōu)解確保能夠得到全局最優(yōu)解的問題。
適用場(chǎng)景
貪心算法適用于問題的最優(yōu)解可以通過一系列局部最優(yōu)解構(gòu)建的情況。
常見的適用于貪心算法的問題包括：
活動(dòng)選擇問題：如何安排活動(dòng)使得使用同一個(gè)會(huì)議室的活動(dòng)數(shù)目最多。 哈夫曼編碼：用于數(shù)據(jù)壓縮的編碼方法。 最小生成樹：如Kruskal算法和Prim算法。 單源最短路徑：如Dijkstra算法。
[!TIP]
點(diǎn)擊鏈接即可查看博客詳情介紹。
活動(dòng)選擇問題
活動(dòng)選擇問題是貪心算法中的一個(gè)經(jīng)典案例，它描述的是這樣一個(gè)問題：給定一個(gè)活動(dòng)集合，每個(gè)活動(dòng)都有一個(gè)開始時(shí)間和結(jié)束時(shí)間，我們需要選擇盡可能多的活動(dòng)，使得這些活動(dòng)之間不相互沖突。
簡(jiǎn)而言之，目標(biāo)是在給定的時(shí)間內(nèi)安排盡可能多的活動(dòng)。
活動(dòng)選擇問題的貪心選擇策略
貪心算法解決活動(dòng)選擇問題的關(guān)鍵在于如何選擇活動(dòng)。一種有效的策略是總是選擇結(jié)束時(shí)間最早的活動(dòng)，因?yàn)榻Y(jié)束得越早，留給其他活動(dòng)的時(shí)間就越多，從而有可能安排更多的活動(dòng)。當(dāng)然，前提是這個(gè)活動(dòng)與已經(jīng)選擇的活動(dòng)不沖突。
算法步驟
輸入：
活動(dòng)集合
(
S
=
{
a
1
,
a
2
,
.
.
.
,
a
n
}
)
，其中每個(gè)活動(dòng)
(
a
i
)
由一個(gè)開始時(shí)間
(
s
i
)
和結(jié)束時(shí)間
(
e
i
)
組成。
活動(dòng)集合 (S = \{a_1, a_2, ..., a_n\})，其中每個(gè)活動(dòng) (a_i) 由一個(gè)開始時(shí)間 (s_i) 和結(jié)束時(shí)間 (e_i) 組成。
活動(dòng)集合(S={a1?,a2?,...,an?})，其中每個(gè)活動(dòng)(ai?)由一個(gè)開始時(shí)間(si?)和結(jié)束時(shí)間(ei?)組成。 排序：按照活動(dòng)的結(jié)束時(shí)間從小到大對(duì)活動(dòng)進(jìn)行排序。 選擇活動(dòng)： $$ 選擇結(jié)束時(shí)間最早的活動(dòng)（假設(shè)為 a_1將其加入到結(jié)果集合中。 從剩下的活動(dòng)中繼續(xù)選擇結(jié)束時(shí)間最早且與已選擇的活動(dòng)不沖突的活動(dòng)，將其加入到結(jié)果集合中。
重復(fù)上述步驟，直到?jīng)]有更多的活動(dòng)可以被選擇。 $$
算法實(shí)現(xiàn)實(shí)例
activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
# 每個(gè)元組代表一個(gè)活動(dòng)，元組的第一個(gè)元素是開始時(shí)間，第二個(gè)元素是結(jié)束時(shí)間
# 按照結(jié)束時(shí)間對(duì)活動(dòng)進(jìn)行排序
activities.sort(key=lambda x: x[1])
def select_activities(activities):
selected_activities = [activities[0]] # 選擇結(jié)束時(shí)間最早的活動(dòng)
last_finish_time = activities[0][1]
for start_time, finish_time in activities[1:]:
if start_time >= last_finish_time: # 如果當(dāng)前活動(dòng)的開始時(shí)間不早于上一個(gè)選中活動(dòng)的結(jié)束時(shí)間
selected_activities.append((start_time, finish_time))
last_finish_time = finish_time
return selected_activities
# 調(diào)用函數(shù)
selected_activities = select_activities(activities)
print("Selected activities:", selected_activities)
/*
步驟 1: 定義活動(dòng)結(jié)構(gòu)體
首先，我們定義一個(gè) Activity 結(jié)構(gòu)體來表示一個(gè)活動(dòng)，包括它的開始時(shí)間和結(jié)束時(shí)間。
*/
#[derive(Debug, Clone)]
struct Activity {
start: i32,
end: i32,
}
/*
步驟 2: 實(shí)現(xiàn)活動(dòng)選擇函數(shù)
接下來，我們實(shí)現(xiàn)一個(gè)函數(shù)來解決活動(dòng)選擇問題。這個(gè)函數(shù)接收一個(gè)活動(dòng)列表作為輸入，返回一個(gè)選中活動(dòng)的列表。
*/
fn activity_selection(mut activities: Vec
// 按照活動(dòng)的結(jié)束時(shí)間進(jìn)行排序
activities.sort_by(|a, b| a.end.cmp(&b.end));
let mut selected_activities = Vec::new();
// 選擇第一個(gè)活動(dòng)
if let Some(first_activity) = activities.first() {
selected_activities.push(first_activity.clone());
let mut last_end = first_activity.end;
// 遍歷其余的活動(dòng)
for activity in activities.iter().skip(1) {
if activity.start >= last_end {
// 如果當(dāng)前活動(dòng)的開始時(shí)間晚于或等于上一個(gè)選中活動(dòng)的結(jié)束時(shí)間，則選擇這個(gè)活動(dòng)
selected_activities.push(activity.clone());
last_end = activity.end;
}
}
}
selected_activities
}
fn activity_selection(mut activities: Vec
// 按照活動(dòng)的結(jié)束時(shí)間進(jìn)行排序
activities.sort_by(|a, b| a.end.cmp(&b.end));
let mut selected_activities = Vec::new();
// 選擇第一個(gè)活動(dòng)
if let Some(first_activity) = activities.first() {
selected_activities.push(first_activity.clone());
let mut last_end = first_activity.end;
// 遍歷其余的活動(dòng)
for activity in activities.iter().skip(1) {
if activity.start >= last_end {
// 如果當(dāng)前活動(dòng)的開始時(shí)間晚于或等于上一個(gè)選中活動(dòng)的結(jié)束時(shí)間，則選擇這個(gè)活動(dòng)
selected_activities.push(activity.clone());
last_end = activity.end;
}
}
}
selected_activities
}
/*
代碼測(cè)試
*/
fn main() {
let activities = vec![
Activity { start: 1, end: 4 },
Activity { start: 3, end: 5 },
Activity { start: 0, end: 6 },
Activity { start: 5, end: 7 },
Activity { start: 8, end: 9 },
Activity { start: 5, end: 9 },
];
let selected_activities = activity_selection(activities);
for activity in selected_activities {
println!("Activity starts at {}, ends at {}", activity.start, activity.end);
}
}
哈夫曼樹
哈夫曼樹（Huffman Tree），又稱最優(yōu)二叉樹，是一種應(yīng)用廣泛的用于數(shù)據(jù)壓縮的樹形結(jié)構(gòu)。它是基于字符出現(xiàn)頻率來構(gòu)造的二叉樹，其中頻率高的字符離根較近，而頻率低的字符離根較遠(yuǎn)，從而實(shí)現(xiàn)數(shù)據(jù)的有效壓縮。構(gòu)造哈夫曼樹的過程是一種貪心算法。
構(gòu)造過程
初始化：根據(jù)待編碼的字符及其頻率構(gòu)造一個(gè)森林，每個(gè)字符都是一個(gè)單節(jié)點(diǎn)的二叉樹，節(jié)點(diǎn)的權(quán)值為字符出現(xiàn)的頻率。構(gòu)造過程：在森林中選出兩個(gè)根節(jié)點(diǎn)的權(quán)值最小的樹合并，作為一個(gè)新的二叉樹的左、右子樹，新二叉樹的根節(jié)點(diǎn)權(quán)值為兩個(gè)子樹根節(jié)點(diǎn)權(quán)值之和。將選中的兩棵樹從森林中刪除，同時(shí)將新形成的二叉樹加入森林。重復(fù)上述過程，直到森林中只剩下一棵樹，這棵樹就是哈夫曼樹。結(jié)果：得到的哈夫曼樹中，每個(gè)字符都對(duì)應(yīng)一條從根到該字符節(jié)點(diǎn)的路徑，路徑上的左右分支分別代表編碼中的0和1，從而得到每個(gè)字符的哈夫曼編碼。
特點(diǎn)
哈夫曼編碼是一種變長(zhǎng)編碼方法，不同字符的編碼長(zhǎng)度不同，頻率高的字符編碼短，頻率低的字符編碼長(zhǎng)。哈夫曼編碼是前綴編碼，任何字符的編碼都不是其他字符編碼的前綴，這保證了編碼的唯一解碼性。
應(yīng)用
哈夫曼編碼廣泛應(yīng)用于數(shù)據(jù)壓縮領(lǐng)域，如ZIP文件壓縮、JPEG圖像壓縮等。通過哈夫曼編碼，可以有效減少存儲(chǔ)空間或傳輸帶寬的需求，提高數(shù)據(jù)處理效率。
/*
步驟 1: 定義節(jié)點(diǎn)和樹的結(jié)構(gòu)
首先，定義哈夫曼樹的節(jié)點(diǎn)結(jié)構(gòu)，以及一個(gè)枚舉來表示節(jié)點(diǎn)可以是葉子節(jié)點(diǎn)或者有兩個(gè)子節(jié)點(diǎn)的中間節(jié)點(diǎn)。
*/
use std::rc::Rc;
use std::cell::RefCell;
use std::collections::BinaryHeap;
use std::cmp::Ordering;
#[derive(Debug, Clone)]
enum Node {
Leaf { character: char, frequency: usize },
Internal { frequency: usize, left: Rc
}
impl Node {
fn frequency(&self) -> usize {
match *self {
Node::Leaf { frequency, .. } | Node::Internal { frequency, .. } => frequency,
}
}
}
impl PartialEq for Node {
fn eq(&self, other: &Self) -> bool {
self.frequency() == other.frequency()
}
}
impl Eq for Node {}
impl PartialOrd for Node {
fn partial_cmp(&self, other: &Self) -> Option
other.frequency().partial_cmp(&self.frequency())
}
}
impl Ord for Node {
fn cmp(&self, other: &Self) -> Ordering {
other.frequency().cmp(&self.frequency())
}
}
/*
步驟 2: 構(gòu)建哈夫曼樹
接下來，實(shí)現(xiàn)構(gòu)建哈夫曼樹的函數(shù)。這個(gè)函數(shù)將接受一個(gè)字符及其頻率的映射，然后構(gòu)建并返回哈夫曼樹。
*/
fn build_huffman_tree(frequencies: &[(char, usize)]) -> Option
if frequencies.is_empty() {
return None;
}
let mut heap = BinaryHeap::new();
for &(character, frequency) in frequencies {
heap.push(Rc::new(RefCell::new(Node::Leaf { character, frequency })));
}
while heap.len() > 1 {
let left = heap.pop().unwrap();
let right = heap.pop().unwrap();
let new_node = Node::Internal {
frequency: left.borrow().frequency() + right.borrow().frequency(),
left,
right,
};
heap.push(Rc::new(RefCell::new(new_node)));
}
heap.pop()
}
/*
步驟 3: 生成哈夫曼編碼
最后，我們需要從哈夫曼樹中生成每個(gè)字符的編碼。這需要遍歷樹，并在遍歷過程中記錄路徑。
*/
fn generate_codes(node: &Rc
match *node.borrow() {
Node::Leaf { character, .. } => {
codes.push((character, prefix));
},
Node::Internal { ref left, ref right, .. } => {
generate_codes(left, format!("{}0", prefix), codes);
generate_codes(right, format!("{}1", prefix), codes);
},
}
}
fn main() {
let frequencies = [('a', 45), ('b', 13), ('c', 12), ('d', 16), ('e', 9), ('f', 5)];
let tree = build_huffman_tree(&frequencies);
let mut codes = Vec::new();
generate_codes(&tree, "".to_string(), &mut codes);
for (character, code) in codes {
println!("Character: {}, Code: {}", character, code);
}
}
/*
單元測(cè)試
*/
use std::rc::Rc;
use std::cell::RefCell;
use std::collections::BinaryHeap;
use std::cmp::Ordering;
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_empty_input() {
let frequencies = [];
let tree = build_huffman_tree(&frequencies);
assert!(tree.is_none());
}
#[test]
fn test_single_element_input() {
let frequencies = [('a', 1)];
let tree = build_huffman_tree(&frequencies).expect("Tree should be created with single element");
let mut codes = Vec::new();
generate_codes(&tree, "".to_string(), &mut codes);
assert_eq!(codes.len(), 1);
assert_eq!(codes[0], ('a', "".to_string()));
}
}
最小生成樹
最小生成樹（Minimum Spanning Tree，MST）是在一個(gè)加權(quán)無向圖中尋找一個(gè)邊的子集，使得這個(gè)子集構(gòu)成的樹包括圖中的所有頂點(diǎn)，并且樹的所有邊的權(quán)值之和最小。最小生成樹在很多領(lǐng)域都有應(yīng)用，比如網(wǎng)絡(luò)設(shè)計(jì)、電路設(shè)計(jì)、交通網(wǎng)絡(luò)規(guī)劃等。
Prim算法（Prim’s Algorithm）
從圖中的任意一個(gè)頂點(diǎn)開始構(gòu)建最小生成樹。 在每一步中，選擇連接樹與非樹頂點(diǎn)且權(quán)值最小的邊，并將其加入到樹中，直到所有頂點(diǎn)都被包含在樹中。 時(shí)間復(fù)雜度：使用優(yōu)先隊(duì)列時(shí)為O(E+VlogV)，其中 V 是頂點(diǎn)數(shù)，E 是邊數(shù)。
/*
定義圖的數(shù)據(jù)結(jié)構(gòu)：首先，我們需要定義一個(gè)適合表示圖的數(shù)據(jù)結(jié)構(gòu)。這里我們使用Vec
*/
use std::collections::BinaryHeap;
use std::cmp::Ordering;
#[derive(Debug, Clone, Eq)]
struct Edge {
node: usize,
cost: i32,
}
impl PartialEq for Edge {
fn eq(&self, other: &Self) -> bool {
self.cost == other.cost
}
}
impl PartialOrd for Edge {
fn partial_cmp(&self, other: &Self) -> Option
other.cost.partial_cmp(&self.cost)
}
}
impl Ord for Edge {
fn cmp(&self, other: &Self) -> Ordering {
other.cost.cmp(&self.cost)
}
}
struct Graph {
adj_list: Vec
}
impl Graph {
fn new(size: usize) -> Self {
Graph {
adj_list: vec![vec![]; size],
}
}
fn add_edge(&mut self, src: usize, dest: usize, cost: i32) {
self.adj_list[src].push((dest, cost));
self.adj_list[dest].push((src, cost)); // For undirected graph
}
}
/*
步驟2: 實(shí)現(xiàn)普里姆算法
接下來，我們實(shí)現(xiàn)普里姆算法來找到最小生成樹：
*/
impl Graph {
fn prim_mst(&self) -> i32 {
let mut total_cost = 0;
let mut edge_heap = BinaryHeap::new();
let mut visited = vec![false; self.adj_list.len()];
// Start from the first node
visited[0] = true;
for &(node, cost) in &self.adj_list[0] {
edge_heap.push(Edge { node, cost });
}
while let Some(Edge { node, cost }) = edge_heap.pop() {
if visited[node] {
continue;
}
visited[node] = true;
total_cost += cost;
for &(next_node, next_cost) in &self.adj_list[node] {
if !visited[next_node] {
edge_heap.push(Edge { node: next_node, cost: next_cost });
}
}
}
total_cost
}
}
/*
步驟3: 添加單元測(cè)試
最后，我們?yōu)槠绽锬匪惴ㄌ砑訂卧獪y(cè)試：
*/
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_prim_mst() {
let mut graph = Graph::new(4);
graph.add_edge(0, 1, 10);
graph.add_edge(0, 2, 6);
graph.add_edge(0, 3, 5);
graph.add_edge(1, 3, 15);
graph.add_edge(2, 3, 4);
assert_eq!(graph.prim_mst(), 19);
}
}
Kruskal算法（Kruskal’s Algorithm）
? 將圖中的所有邊按權(quán)值從小到大排序。 ? 依次考慮每條邊，如果這條邊不會(huì)與已選擇的邊形成環(huán)，則將其加入到最小生成樹中。 ? 使用并查集（Disjoint Set Union，DSU）可以高效地檢測(cè)環(huán)。 ? 時(shí)間復(fù)雜度：O(ElogE) 或 O(ElogV)（因?yàn)樾枰獙?duì)邊進(jìn)行排序）。
/*
定義邊和并查集的數(shù)據(jù)結(jié)構(gòu)：克魯斯卡爾算法需要對(duì)所有的邊進(jìn)行排序，并使用并查集（Disjoint Set Union，DSU）來檢測(cè)環(huán)。
*/
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
struct Edge {
src: usize,
dest: usize,
weight: i32,
}
struct DisjointSet {
parent: Vec
rank: Vec
}
impl DisjointSet {
fn new(size: usize) -> Self {
DisjointSet {
parent: (0..size).collect(),
rank: vec![0; size],
}
}
fn find(&mut self, node: usize) -> usize {
if self.parent[node] != node {
self.parent[node] = self.find(self.parent[node]);
}
self.parent[node]
}
fn union(&mut self, node1: usize, node2: usize) {
let root1 = self.find(node1);
let root2 = self.find(node2);
if self.rank[root1] < self.rank[root2] {
self.parent[root1] = root2;
} else if self.rank[root1] > self.rank[root2] {
self.parent[root2] = root1;
} else {
self.parent[root2] = root1;
self.rank[root1] += 1;
}
}
}
/*
實(shí)現(xiàn)克魯斯卡爾算法：對(duì)邊進(jìn)行排序，并逐一檢查每條邊以構(gòu)建最小生成樹，同時(shí)使用并查集來避免環(huán)的形成。
*/
fn kruskal(edges: &mut Vec
edges.sort(); // Sort edges based on weight
let mut dsu = DisjointSet::new(num_nodes);
let mut mst = Vec::new();
for edge in edges.iter() {
let root1 = dsu.find(edge.src);
let root2 = dsu.find(edge.dest);
if root1 != root2 {
mst.push(edge.clone());
dsu.union(root1, root2);
}
}
mst
}
/*
添加單元測(cè)試：確保算法的正確性。
*/
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_kruskal() {
let mut edges = vec![
Edge { src: 0, dest: 1, weight: 10 },
Edge { src: 0, dest: 2, weight: 6 },
Edge { src: 0, dest: 3, weight: 5 },
Edge { src: 1, dest: 3, weight: 15 },
Edge { src: 2, dest: 3, weight: 4 }
];
let mst = kruskal(&mut edges, 4);
assert_eq!(mst.len(), 3);
assert_eq!(mst.iter().map(|e| e.weight).sum::
}
}
選擇算法
[!NOTE]
在圖論中，判斷一個(gè)圖是稠密（Dense）還是稀疏（Sparse）通常依賴于圖中邊的數(shù)量與頂點(diǎn)數(shù)量的關(guān)系。
稀疏圖：如果邊的數(shù)量接近頂點(diǎn)的數(shù)量，即 (E ≈V) 或 (E = O(V))，則圖被認(rèn)為是稀疏的。在實(shí)際應(yīng)用中，如果邊的數(shù)量少于頂點(diǎn)數(shù)量的兩倍，即 (E < 2V)，圖通常也被認(rèn)為是稀疏的。 稠密圖：如果邊的數(shù)量接近頂點(diǎn)數(shù)量的平方，即 (E ≈ V^2) 或 (E = O(V^2))，則圖被認(rèn)為是稠密的。在實(shí)際應(yīng)用中，如果邊的數(shù)量大于或等于頂點(diǎn)數(shù)量的對(duì)數(shù)倍，即 (E ≥Vlog V)，圖也可能被認(rèn)為是較為稠密的。
快速判斷方法
計(jì)算邊和頂點(diǎn)的比率：計(jì)算 (E/V) 的值，這個(gè)比率可以提供圖是稠密還是稀疏的直觀感受。如果這個(gè)比率接近1或者更小，圖很可能是稀疏的；如果這個(gè)比率接近頂點(diǎn)數(shù) (V) 或更高，圖很可能是稠密的。 觀察實(shí)際應(yīng)用場(chǎng)景：在某些情況下，圖的應(yīng)用背景也能提供是否稠密或稀疏的線索。例如，在社交網(wǎng)絡(luò)中，用戶（頂點(diǎn)）之間的連接（邊）可能非常豐富，使得這類圖傾向于更稠密。而在某些交通網(wǎng)絡(luò)中，地點(diǎn)（頂點(diǎn)）之間的直接路線（邊）可能相對(duì)較少，使得這類圖可能更傾向于稀疏。
注意事項(xiàng)
如果圖是稠密的，即邊數(shù)接近頂點(diǎn)數(shù)的平方，通常使用普里姆算法更高效。如果圖是稀疏的，即邊數(shù)與頂點(diǎn)數(shù)相近，克魯斯卡爾算法可能更合適。
柚子快報(bào)激活碼778899分享：使用rust學(xué)習(xí)基本算法（二）
參考文章
本文內(nèi)容根據(jù)網(wǎng)絡(luò)資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點(diǎn)和立場(chǎng)。
轉(zhuǎn)載請(qǐng)注明，如有侵權(quán)，聯(lián)系刪除。
Fyndiq優(yōu)選網(wǎng)
