Жадные алгоритмы

Алгоритм Дейкстры используется для поиска кратчайшего пути между узлами в графе. Алгоритм поддерживает набор не посещенных узлов и рассчитывает предварительное расстояние от данного узла до другого. Если алгоритм находит более короткий способ добраться до данного узла, путь обновляется, чтобы отразить более короткое расстояние. Эта проблема имеет удовлетворительную оптимизацию, так как если А соединена с В , В связана с С, и необходимо пройти через точки А и В, чтобы добраться до места назначения С , то кратчайший путь из А до B и кратчайший путь из B к С должен быть частью кратчайшего пути от А до C . Таким образом, оптимальные ответы из подзадач действительно способствуют оптимальному ответу для всей проблемы. Это связано с тем, что алгоритм отслеживает кратчайший путь, возможный для любого данного узла.
Кодирование Хаффмана — еще один пример алгоритма, в котором жадный подход успешен. Алгоритм Хаффмана анализирует сообщение и в зависимости от частот символов, используемых в сообщении, назначает кодирование переменной длины для каждого символа. Более часто используемый символ будет иметь более короткую кодировку, в то время как редкий символ будет иметь более длинную кодировку.
Алгоритм кодирования Хаффмана принимает информацию о частотах или вероятностях появления конкретного символа. Он начинает строить дерево префиксов снизу вверх, начиная с двух наименее вероятных символов в списке. Он берет эти символы и формирует поддерево, содержащее их, а затем удаляет отдельные символы из списка. Алгоритм суммирует вероятности элементов в поддереве и добавляет поддерево и его вероятность в список. Затем алгоритм ищет список и выбирает два символа или поддерева с наименьшими вероятностями. Он использует их для создания нового поддерева, удаляет исходные поддеревья / символы из списка, а затем добавляет новое поддерево и его объединенную вероятность в список. Это повторяется до тех пор, пока не появится одно дерево и все элементы не будут добавлены.
Демонстрационный пример решения
Задача найти наименьшее число с заданной суммой цифр s и количеством цифр d.
Простое решение заключается в рассмотрении всех цифр числа м, сумма которых равна заданной и определение среди них минимального числа.
Существует жадный подход к решению проблемы. Идея состоит в том, чтобы по одному заполнить все цифры от крайнего правого до крайнего левого (или от наименее значимого разряда до самого значимого)
Программная реализация
Назначение программы
Задача найти наименьшее число с заданной суммой цифр s и количеством цифр d.
Простое решение заключается в рассмотрении всех цифр числа м, сумма которых равна заданной и определение среди них минимального числа.
Существует жадный подход к решению проблемы. Идея состоит в том, чтобы по одному заполнить все цифры от крайнего правого до крайнего левого (или от наименее значимого разряда до самого значимого)
Первоначально мы вычитаем 1 из суммы s, чтобы у нас была самая маленькая цифра в конце. После вычета 1 мы применяем жадный подход. Мы сравниваем оставшуюся сумму с 9, если оставшаяся сумма больше 9, мы помещаем 9 в текущую позицию, иначе мы оставляем оставшуюся сумму. Поскольку мы заполняем цифры справа налево, мы ставим самые высокие цифры справа.
Структура и назначение модулей программы
Программа состоит из основной функции, которая отвечает за вывод на экран результатов и запросов на ввод данных для пользователя, также из этой функции осуществляется вызов второй функции, в которой собственно и реализован жадный алгоритм.
Описание форматов хранения данных
В работе используются целочисленные переменные и массив, для хранения и обработки данных.
Описание алгоритмов решения задачи