Жадные алгоритмы — важная тема для изучения каждым программистом. Жадный алгоритм — это алгоритмический подход, который всегда делает локально оптимальный выбор на каждом шаге в надежде найти глобальный оптимум. Это простой и эффективный способ решения задач оптимизации, требующих принятия наилучшего решения на каждом этапе. В этом уроке мы обсудим 4 лучших жадных алгоритма, которые должен знать каждый программист.
1. Алгоритм Крускала для минимального остовного дерева
Алгоритм Крускала используется для нахождения минимального остовного дерева связного взвешенного графа. Он начинается с пустого графа и постепенно добавляет ребра, выбирая ребро с наименьшим весом, не создающее цикл. Алгоритм Крускала очень эффективен, его временная сложность составляет O(E log E), где E — количество ребер в графе.
Давайте посмотрим на пример алгоритма Крускала с использованием Python:
# Kruskal's algorithm for minimum spanning tree
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = []
def add_edge(self, u, v, w):
self.graph.append([u, v, w])
def find_parent(self, parent, i):
if parent[i] == i:
return i
return self.find_parent(parent, parent[i])
def union(self, parent, rank, x, y):
x_root = self.find_parent(parent, x)
y_root = self.find_parent(parent, y)
if rank[x_root] < rank[y_root]:
parent[x_root] = y_root
elif rank[x_root] > rank[y_root]:
parent[y_root] = x_root
else:
parent[y_root] = x_root
rank[x_root] += 1
def kruskal(self):
result = []
i = 0
e = 0
self.graph = sorted(self.graph, key=lambda item: item[2])
parent = []
rank = []
for node in range(self.V):
parent.append(node)
rank.append(0)
while e < self.V - 1:
u, v, w = self.graph[i]
i += 1
x = self.find_parent(parent, u)
y = self.find_parent(parent, v)
if x != y:
e += 1
result.append([u, v, w])
self.union(parent, rank, x, y)
return result
# example usage
g = Graph(4)
g.add_edge(0, 1, 10)
g.add_edge(0, 2, 6)
g.add_edge(0, 3, 5)
g.add_edge(1, 3, 15)
g.add_edge(2, 3, 4)
print(g.kruskal())
2. Алгоритм Дейкстры для поиска кратчайшего пути
Алгоритм Дейкстры используется для поиска кратчайшего пути между двумя узлами во взвешенном графе. Он начинается с одного узла и постепенно исследует его соседей, выбирая соседа с наименьшим расстоянием для добавления в посещаемый набор. Это продолжается до тех пор, пока не будет достигнут узел назначения. Алгоритм Дейкстры имеет временную сложность O(V log V), где V — количество вершин в графе.
Вот пример алгоритма Дейкстры с использованием Python:
# Dijkstra's algorithm for shortest path
import heapq
def dijkstra(graph, start, end):
pq = [(0, start)]
visited = set()
distances = {start: 0}
while pq:
(dist, node) = heapq.heappop(pq)
if node in visited:
continue
visited.add(node)
if node == end:
return distances[node]
for neighbor, weight in graph[node]:
if neighbor in visited:
continue
new_distance = dist + weight
if neighbor not in distances or new_distance < distances[neighbor]:
distances[neighbor] = new_distance
heapq.heappush(pq, (new_distance, neighbor))
return float('inf')
# example usage
graph = {
'A': [('B', 2), ('C', 1)],
'B': [('A', 2), ('D', 5)],
'C': [('A', 1), ('D', 1)],
'D': [('B', 5), ('C', 1), ('E', 2)],
'E': [('D', 2)]
}
print(dijkstra(graph, 'A', 'E'))
3. Алгоритм кодирования Хаффмана для сжатия данных
Кодирование Хаффмана — это алгоритм сжатия данных без потерь, который работает путем присвоения кодов переменной длины разным символам в зависимости от частоты их появления в тексте. Часто встречающимся символам назначаются более короткие коды, а редко встречающимся — более длинные коды. Алгоритм кодирования Хаффмана имеет временную сложность O(n log n), где n — количество символов в тексте.
Вот пример кода Хаффмана с использованием Python:
# Huffman coding algorithm for data compression
from queue import PriorityQueue
class Node:
def __init__(self, freq, char=None, left=None, right=None):
self.freq = freq
self.char = char
self.left = left
self.right = right
def __lt__(self, other):
return self.freq < other.freq
def __eq__(self, other):
return self.freq == other.freq
def build_huffman_tree(data):
freq_map = {}
for char in data:
if char not in freq_map:
freq_map[char] = 0
freq_map[char] += 1
pq = PriorityQueue()
for char, freq in freq_map.items():
pq.put(Node(freq, char))
while pq.qsize() > 1:
node1 = pq.get()
node2 = pq.get()
merged_node = Node(node1.freq + node2.freq, left=node1, right=node2)
pq.put(merged_node)
return pq.get()
def build_huffman_codebook(node, codebook, code=''):
if node is None:
return
if node.char is not None:
codebook[node.char] = code
build_huffman_codebook(node.left, codebook, code + '0')
build_huffman_codebook(node.right, codebook, code + '1')
def huffman_encode(data):
root = build_huffman_tree(data)
codebook = {}
build_huffman_codebook(root, codebook)
encoded = ''
for char in data:
encoded += codebook[char]
return encoded, codebook
def huffman_decode(encoded, codebook):
inv_codebook = {v: k for k, v in codebook.items()}
decoded = ''
code = ''
for bit in encoded:
code += bit
if code in inv_codebook:
decoded += inv_codebook[code]
code = ''
return decoded
# example usage
data = 'hello world'
encoded, codebook = huffman_encode(data)
print('Encoded:', encoded)
print('Codebook:', codebook)
decoded = huffman_decode(encoded, codebook)
print('Decoded:', decoded)
4. Алгоритм интервального планирования
Алгоритм планирования интервалов используется для нахождения максимального количества непересекающихся интервалов в заданном наборе интервалов. Он начинается с сортировки интервалов по времени их окончания, а затем выбора непересекающихся интервалов с самым ранним временем окончания. Алгоритм интервального планирования имеет временную сложность O(n log n), где n — количество интервалов.
Вот пример алгоритма интервального планирования с использованием Python:
# Interval Scheduling Algorithm
def interval_scheduling(intervals):
intervals.sort(key=lambda x: x[1]) # sort by finishing time
selected = []
end_time = 0
for interval in intervals:
if interval[0] >= end_time:
selected.append(interval)
end_time = interval[1]
return selected
# example usage
intervals = [(0, 6), (1, 4), (3, 5), (3, 8), (4, 7), (5, 9), (6, 10), (8, 11)]
selected = interval_scheduling(intervals)
print(selected)
Заключение
Жадные алгоритмы могут быть отличным инструментом для программистов, позволяющим быстро и эффективно решать проблемы. Лучшая часть? Их легко понять и реализовать. Мы рассмотрели 4 лучших жадных алгоритма, которые должен знать каждый программист. Но там еще столько всего!
Освоив эти алгоритмы, программисты могут улучшить свои навыки решения проблем и стать более эффективными в своей работе. Они могут даже оценить элегантность этих алгоритмов и то, как они решают проблемы, принимая оптимальные решения на каждом этапе.
Итак, в следующий раз, когда вы столкнетесь с проблемой, требующей оптимизации, не забудьте рассмотреть жадный алгоритм как потенциальное решение. Кто знает, может быть, это самый эффективный и действенный подход к вашей проблеме.
Повышение уровня кодирования
Спасибо, что являетесь частью нашего сообщества! Перед тем, как ты уйдешь:
- 👏 Хлопайте за историю и подписывайтесь на автора 👉
- 📰 Смотрите больше контента в публикации Level Up Coding
- 💰 Бесплатный курс собеседования по программированию ⇒ Просмотреть курс
- 🔔 Подписывайтесь на нас: Twitter | ЛинкедИн | "Новостная рассылка"
🚀👉 Присоединяйтесь к коллективу талантов Level Up и найдите прекрасную работу
