Жадный алгоритм - это алгоритмическая парадигма, которая следует эвристике решения проблем, заключающейся в выполнении локально оптимального выбора на каждом этапе в надежде найти глобальный оптимум.
Рисунок: Жадные алгоритмы определяют минимальное количество монет, которое нужно отдать при внесении сдачи. Это шаги, которые может предпринять человек, чтобы подражать жадному алгоритму для представления 36 центов, используя только монеты со значениями {1, 5, 10, 20}. Монета с наибольшей стоимостью, меньше оставшейся причитающейся сдачи, является локальным оптимумом.
Ниже приведены часто задаваемые проблемы жадных алгоритмов на технических собеседованиях:
Задача выбора деятельности
Учитывая набор действий, а также время начала и окончания каждого действия, найдите максимальное количество действий, выполняемых одним человеком, предполагая, что человек может работать только над одним действием за раз.
Задача раскраски графа
Раскраска графа (также называемая раскраской вершин) - это способ раскраски вершин графа таким образом, чтобы никакие две соседние вершины не имели одинаковый цвет. В этой статье будет обсуждаться жадный алгоритм раскраски графиков и минимизировать общее количество используемых цветов.
Проблема с очередностью заданий и дедлайнами
Учитывая набор задач с крайними сроками и общей прибылью, полученной при выполнении задачи, найдите максимальную прибыль, полученную при выполнении задач в указанные сроки. Предположим, что на выполнение задачи требуется одна единица времени, и она не может быть выполнена сверх установленного срока. Кроме того, одновременно будет выполняться только одна задача.
Найдите минимум платформ, необходимых, чтобы избежать задержки прибытия поезда
Имея расписание, в котором указано время прибытия и отправления поездов на станцию, найдите минимальное количество платформ, необходимое, чтобы избежать задержки прибытия любого поезда.
Алгоритм сжатия кодирования Хаффмана
Кодирование Хаффмана (также известное как кодирование Хаффмана) - это алгоритм сжатия данных, который составляет основную идею сжатия файлов. В этой публикации рассказывается о кодировании фиксированной и переменной длины, однозначно декодируемых кодах, правилах префиксов и построении дерева Хаффмана.
Кратчайшие пути из одного источника - алгоритм Дейкстры
Для исходной вершины `s` из набора вершин` V` взвешенного графа, у которой все веса ребер `w (u, v)` неотрицательны, найдите веса кратчайшего пути `d (s, v) `из источника` s` для всех вершин `v`, присутствующих в графе.
Алгоритм Краскала для поиска минимального остовного дерева
Для неориентированного, связного и взвешенного графа постройте из него минимальное остовное дерево с помощью алгоритма Крускала.
Задача о кратчайшей суперструне
Учитывая список строк, в котором ни одна строка не является подстрокой другой, найдите самую короткую строку, которая содержит каждую строку в списке в качестве подстроки.
Спасибо за чтение.
