Все о жадных алгоритмах| Руководство для начинающих.

Жадные алгоритмы Все, что вам нужно знать для начинающих.

Представьте, что вы отправляетесь в путь в новое место, скорее всего, вы используете GPS-навигацию, чтобы найти самый быстрый маршрут. Точно так же, ища эффективный по времени путь в незнакомом маршруте, жадные алгоритмы всегда выбирают следующий шаг, который предлагает наиболее очевидную и немедленную выгоду. Жадные алгоритмы обычно выбирают лучший вариант на каждом шаге, что постепенно дает нам способ достижения решения в эффективное с точки зрения времени решение.

Теперь давайте рассмотрим пример, чтобы узнать больше о жадных алгоритмах — проблема сдачи монет.

• Для всего мира некоммерческая организация применяет графические процессоры для обучения медицинских работников операциям, спасающим зрение.
• Как установить AutoGen на ваш компьютер в 13 простых шагах.
• Сверхмощные вычисления NVIDIA и AMD предлагают мощные рабочие станции для ускорения искусственного интеллекта, рендеринга и симуляции.

Предположим, нам нужно дать 31 монету в качестве сдачи, и у нас есть номинации 20, 10, 5, 2, 1.

Проблема сдачи монет использует жадный алгоритмический подход:

• Сначала найдите самую большую номинацию, которая меньше общей суммы.
• Добавьте номинал к результату и вычтите его из общей суммы.
• Если общая сумма теперь равна нулю, то напечатайте номинации.
• Иначе повторите шаги 1 и 2.

Определение жадных алгоритмов

Жадные алгоритмы – это набор оптимизационных алгоритмов, используемых в алгоритмическом решении проблем. Основная идея жадного подхода заключается в том, чтобы сделать локально оптимальный выбор на каждом этапе с надеждой найти глобальный оптимум. В отличие от метода динамического программирования, где мы решаем подзадачи и храним решения, чтобы избежать избыточных вычислений, жадные алгоритмы принимают решения, выбирая лучший доступный вариант на текущий момент, не учитывая последующие шаги.

Когда следует выбирать жадные алгоритмы?

Жадные алгоритмы подходят для задач, которые обладают следующими характеристиками:

1. Жадный выбор: жадные алгоритмы всегда принимают лучшее решение на каждом шаге, чтобы достичь оптимального глобального решения. При этом они не рассматривают повторное посещение принятых решений. Если нам не нужно пересматривать или изменять принятые решения, то можно выбрать жадный алгоритмический подход.
2. Оптимальная подструктура: если мы можем подходить к общему решению, разбивая нашу проблему на ряд подзадач, в которых лучшее решение имеет значение, мы можем использовать жадный алгоритм.
3. Эффективность по времени: жадные алгоритмы являются простыми и эффективными по времени. Они достигают глобального оптимума быстрее и могут не учитывать принятые решения в прошлом.

Теперь давайте решим 3 задачи, использующие жадный алгоритмический подход.

Проблема выбора действия – Непересекающиеся интервалы

Учитывая массив интервалов intervals, где intervals[i] = [starti, endi], верните минимальное количество интервалов, которые необходимо удалить, чтобы остальные интервалы не перекрывались.

Пример 1:

Ввод: интервалы = [[1,2],[2,3],[3,4],[1,3]]Вывод: 1Объяснение: [1,3] можно удалить, и остальные интервалы не перекрываются.

Пример 2:

Ввод: интервалы = [[1,2],[1,2],[1,2]]Вывод: 2Объяснение: Вам нужно удалить два [1,2], чтобы остальные интервалы не перекрывались.

Пример 3:

Ввод: интервалы = [[1,2],[2,3]]Вывод: 0Объяснение: Вам не нужно удалять ни один из интервалов, так как они уже не перекрываются.

Код:

class Solution:    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:        intervals.sort(key=lambda x: x[1])        last_end = intervals[0][1]        count = 0        for s, e in intervals[1:]:          if last_end>s:            count += 1          else:            last_end = e        return(count)

Вышеуказанный код следует подходу жадного алгоритма. Мы сортируем входной список, чтобы убедиться, что мы можем следовать оптимальной подструктуре – разделению его на более маленькие проблемы. Затем мы убеждаемся, что каждый список во вложенном списке не перекрывает предыдущий, и на основе этого мы увеличиваем наш ответ.

Кодирование Хаффмана

Кодирование Хаффмана – это алгоритм сжатия данных без потерь. Целью кодирования Хаффмана является представление данных путем назначения более коротких двоичных кодов наиболее часто встречающимся символам и более длинных кодов для реже встречающихся символов.

Подход:

• Рассчитайте частоту каждого символа в переданных данных.
• Строится дерево таким образом, чтобы более часто встречающиеся символы имели более короткие двоичные коды, а менее часто встречающиеся символы – более длинные двоичные коды.
• Для каждого символа назначаются двоичные коды. Путь от корня дерева к определенному символу явно определяет его двоичный код.
• Эти назначенные двоичные коды для каждого символа образуют коды Хаффмана. Исходные данные были заменены кодом Хаффмана.
• То же самое дерево Хаффмана используется для распаковки данных. Начиная с корня, проходятся двоичные коды, и восстанавливаются исходные символы.

Пример – Построение дерева:

Давайте рассмотрим текст – ABRACADABRA, Здесь A встречается 5 раз, B и R дважды, а C и D один раз. Дерево Хаффмана строится на основе этих частот, и дерево может выглядеть так –

В этом примере ‘A’ может быть назначен код ‘0’, ‘B’ – код ‘110’, ‘R’ – код ‘111’, ‘C’ – код ’10’ и ‘D’ – код ‘1110’. Кодирование Хаффмана широко используется в различных приложениях, включая сжатие файлов (файлы ZIP), сжатие изображений (JPEG) и сетевые протоколы. Его эффективность заключается в том, что более частые символы имеют более короткие коды, что приводит к общему сжатию данных.

Код:

import heapqfrom collections import defaultdictclass Node:    def __init__(self, symbol=None, frequency=None):        self.symbol = symbol        self.frequency = frequency        self.left = None        self.right = None    def __lt__(self, other):        return self.frequency < other.frequencydef build_huffman_tree(frequencies):    heap = [Node(symbol=s, frequency=f) for s, f in frequencies.items()]    heapq.heapify(heap)    while len(heap) > 1:        left = heapq.heappop(heap)        right = heapq.heappop(heap)        merged = Node(frequency=left.frequency + right.frequency)        merged.left = left        merged.right = right        heapq.heappush(heap, merged)    return heap[0]def generate_huffman_codes(node, code="", mapping=None):    if mapping is None:        mapping = {}    if node.symbol:        mapping[node.symbol] = code    if node.left:        generate_huffman_codes(node.left, code + "0", mapping)    if node.right:        generate_huffman_codes(node.right, code + "1", mapping)    return mappingdef huffman_encode(text):    frequencies = defaultdict(int)    for symbol in text:        frequencies[symbol] += 1    root = build_huffman_tree(frequencies)    codes = generate_huffman_codes(root)    encoded_text = "".join(codes[symbol] for symbol in text)    return encoded_text, roottext_to_encode = "ABRACADABRA"encoded_text, huffman_tree_root = huffman_encode(text_to_encode)print("Исходный текст:", text_to_encode)print("Закодированный текст:", encoded_text)

Чтобы узнать больше о используемых коллекциях в приведенном выше коде, обратитесь к моей предыдущей статье –

Все о модуле Collections в Python

Как мы все знаем, в Python есть свои обычные типы данных-герои – список, кортеж, словарь и печально известные множества. Но наряду с…

pub.towardsai.net

Алгоритм Дейкстры

Алгоритм Дейкстры используется в теории графов для нахождения кратчайшего пути между узлами графа, в основном для графов с положительными весами ребер.

Подход:

• Инициализируйте очередь с приоритетом для отслеживания расстояний от начальной точки до узлов. Установите расстояние до начальной точки равным 0, а остальных узлов равным бесконечности.
• Из узла с наименьшим расстоянием обновите расстояние до других соседей, вычислив сумму текущего расстояния от выбранных узлов до остальных узлов.
• После обработки расстояний отметьте его как посещенный, чтобы не повторно посещать уже исследованные узлы. Повторите процесс, пока все узлы не будут посещены.

Пример:

Узлы: A, B, C, DРебра: (A, B, 4), (A, C, 5), (A, D, 2), (B, C, 1), (B, D, 3), (C, D, 5)

Давайте найдем кратчайшие пути от узла A до всех остальных узлов с помощью алгоритма Дейкстры:

• Начните с узла A. Установите расстояние до A равным 0 и до остальных узлов равным бесконечности: (A, 0), (B, ∞), (C, ∞), (D, ∞).
• Инициализируйте очередь с приоритетом с этими расстояниями.
• Выберите A с расстоянием 0. Изучите его соседей: B (вес 4), C (вес 5), D (вес 2).
• Обновите расстояния: (A, 0), (B, 4), (C, 5), (D, 2).
• Отметьте A как посещенный. Повторите, пока все узлы не будут исследованы.
• Выберите D с расстоянием 2. Изучите его соседей: B (вес 3) и C (вес 5).
• Обновите расстояния: (A, 0), (B, 4), (C, 5), (D, 2) (без изменений для D). Отметьте D как посещенный.
• Повторите процесс для всех остальных узлов.
• Кратчайшие пути от A до других узлов:
• A до B: [A, D, B] (Общее расстояние: 4 + 3 = 7)
• A до C: [A, D, C] (Общее расстояние: 2 + 5 = 7)
• A до D: [A, D] (Общее расстояние: 2)

Код:

import heapqfrom collections import defaultdictdef dijkstra(graph, start):    distances = {node: float('infinity') for node in graph}    distances[start] = 0    priority_queue = [(0, start)]    while priority_queue:        current_distance, current_node = heapq.heappop(priority_queue)        if current_distance > distances[current_node]:            continue        for neighbor, weight in graph[current_node].items():            distance = current_distance + weight            if distance < distances[neighbor]:                distances[neighbor] = distance                heapq.heappush(priority_queue, (distance, neighbor))    return distancesgraph = {    'A': {'B': 4, 'C': 5, 'D': 2},    'B': {'A': 4, 'C': 1, 'D': 3},    'C': {'A': 5, 'B': 1, 'D': 5},    'D': {'A': 2, 'B': 3, 'C': 5}}start_node = 'A'shortest_distances = dijkstra(graph, start_node)print(f"Кратчайшие расстояния от {start_node}:")for node, distance in shortest_distances.items():    print(f"К {node}: {distance}")

Вы можете изучить проблемы, связанные с жадными алгоритмами, по этой ссылке.

Примечание: Важно выбирать наилучший подход к решению проблемы. Жадный алгоритм не всегда дает оптимальное решение. Например, в проблеме сдачи монет, что если номиналы равны [3,5], а сумма равна 9. Жадный алгоритм не сможет решить эту задачу. Но существует множество других решений, где он работает. Поэтому выбирайте свой подход мудро.

Вы можете узнать больше о структурах данных и динамическом программировании, используя следующие статьи:

Понимание метода возврата при использовании Python: руководство для начинающих

Метод возврата – это алгоритм, используемый для поиска всех возможных решений проблемы. При использовании этой техники мы находим…

pub.towardsai.net

Улучшение кода на Python: мемоизация против табуляции

Мемоизация – это конкретная оптимизационная техника, используемая в программировании и проектировании алгоритмов для улучшения…

blog.devgenius.io

Надеюсь, этот материал будет полезен… Удачного обучения….