Жадібні алгоритми

4.1 Визначення жадібних алгоритмів.

Жадібні алгоритми (Greedy Algorithms) — це клас алгоритмів, які будують рішення шляхом прийняття локально оптимальних рішень на кожному кроці. Ці рішення приймаються на основі поточного стану і не переглядаються в майбутньому.

Жадібні алгоритми часто використовуються для розв'язання задач оптимізації, де мета — максимізувати або мінімізувати певну величину.

Основні принципи жадібних алгоритмів

• Жадібний вибір: На кожному кроці алгоритм обирає найкращий локальний варіант, який, на його думку, приведе до глобально оптимального рішення.
• Оптимальна підструктура: Проблема повинна мати властивість, що локально оптимальні рішення можуть бути об'єднані для отримання глобально оптимального рішення.
• Монотонність: Після вибору чергового локально оптимального кроку рішення не повинно бути погіршено подальшими виборами.

Переваги та недоліки жадібних алгоритмів

Переваги:

• Простота реалізації: Жадібні алгоритми часто прості для розуміння та реалізації.
• Ефективність: Зазвичай вони працюють швидше, ніж більш складні алгоритми, такі як динамічне програмування.

Недоліки:

• Відсутність глобальної оптимальності: Жадібні алгоритми не завжди приводять до глобально оптимального рішення.
• Не всі задачі підходять: Тільки певні задачі можуть бути розв'язані жадібними алгоритмами.

Є цілий клас задач, у яких найкраще рішення досягається жадібним алгоритмом. Вам буде корисно дізнатися про такі.

4.2 Задача про розмін монет.

Задача:

У нас є монети різного номіналу. Потрібно знайти мінімальну кількість монет для здачі заданої суми.

Рішення:

Завжди береться монета з найбільшим номіналом, що не перевищує залишок суми.

Часова складність: O(n), де n — кількість типів монет.

Приклад коду на Python:

def min_coins(coins, amount):
    coins.sort(reverse=True)
    count = 0
    for coin in coins:
        while amount >= coin:
            amount -= coin
            count += 1
    return count
        

4.3 Задача про рюкзак

Задача:

У нас є предмети з відомою вартістю і вагою. Ми хочемо покласти в рюкзак фіксованого розміру речей на якомога більшу суму.

В цьому варіанті задачі предмети можна ділити на частини. Наприклад ми хочемо купити різні крупи і можна хоч 1000 грамів, хоч 512.

Рішення:

Сортування предметів за питомою вартістю (вартість/вага) і вибір найбільших питомих вартостей до заповнення рюкзака.

Часова складність: O(n log n), де n — кількість предметів.

Приклад коду на Python:

class Item:
    def __init__(self, value, weight):
        self.value = value
        self.weight = weight
        self.ratio = value / weight
        
def fractional_knapsack(items, capacity):
    items.sort(key=lambda x: x.ratio, reverse=True)
    total_value = 0.0
    for item in items:
        if capacity >= item.weight:
            total_value += item.value
            capacity -= item.weight
        else:
            total_value += item.ratio * capacity
            break
    return total_value
        
        

4.4 Задача про покриття відрізками

Задача:

Є відрізки на прямій лінії, задані своїми кінцями (x1, x2), і один цільовий відрізок. Потрібно знайти мінімальну кількість відрізків, що покривають всі точки цільового відрізка.

Рішення:

Сортування відрізків за правим кінцем та вибір найменшого відрізка, що покриває поточну точку.

Часова складність: O(n log n), де n — кількість відрізків.

Приклад коду на Python:

def min_segments(segments):
    segments.sort(key=lambda x: x[1])
    count = 0
    end = -float('inf')
    for seg in segments:
        if seg[0] > end:
            end = seg[1]
            count += 1
    return count
        

1

Опитування

Жадні алгоритми, рівень 19, лекція 3

Недоступний

Жадні алгоритми

Жадні алгоритми

Відкрити