Acgöz (Greedy) algoritmlər

4.1 Acgöz alqoritmlərin tərifi.

Acgöz alqoritmlər (Greedy Algorithms) — bu sinif alqoritmlərdir, hansı ki qərarı hər addımda lokal optimal həlləri qəbul etməklə qurur. Bu həllər mövcud vəziyyətə əsasən qəbul edilir və gələcəkdə yenidən nəzərdən keçirilməz.

Acgöz alqoritmlər optimallaşdırma məsələlərinin həlli üçün tez-tez istifadə olunur, burada məqsəd müəyyən bir dəyəri maksimallaşdırmaq və ya minimallaşdırmaqdır.

Acgöz alqoritmlərin əsas prinsipləri

• Acgöz seçim: Hər addımda alqoritm ən yaxşı lokal variantı seçir, hansı ki, onun fikrincə, qlobal optimal həllə gətirib çıxaracaq.
• Optimal substruktur: Məsələ belə bir xüsusiyyətə malik olmalıdır ki, lokal optimal həllər qlobal optimal həll əldə etmək üçün birləşdirilə bilər.
• Monotonluq: Növbəti lokal optimal addım seçildikdən sonra həll sonrakı seçimlərdən pisləşməməlidir.

Acgöz alqoritmlərin üstünlükləri və çatışmazlıqları

Üstünlüklər:

• Sadə icra: Acgöz alqoritmləri başa düşmək və icra etmək adətən sadədir.
• Effektivlik: Adətən daha mürəkkəb alqoritmlərdən, məsələn, dinamik proqramlaşdırmadan daha tez işləyir.

Çatışmazlıqlar:

• Qlobal optimallığın çatışmazlığı: Acgöz alqoritmlər həmişə qlobal optimal həllə gətirib çıxarmır.
• Bütün məsələlər uyğun deyil: Yalnız müəyyən məsələlər acgöz alqoritmlərlə həll edilə bilər.

Elə bir sinif məsələlər var ki, onların ən yaxşı həlli acgöz alqoritmlə əldə edilir. Bu haqda öyrənmək sənə faydalı olacaq.

4.2 Pulun qaytarılması məsələsi.

Məsələ:

Müxtəlif dəyərdə qəpiklərimiz var. Verilən məbləği qaytarmaq üçün minimum qəpik sayını tapmaq lazımdır.

Həll yolu:

Həmişə qalan məbləğdən böyük olmayan ən böyük dəyərə malik qəpik götürülür.

Zaman mürəkkəbliyi: O(n), burada n - qəpik növlərinin sayıdır.

Python-da kod nümunəsi:

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 Çanta tapşırığı

Tapşırıq:

Bizdə dəyəri və çəkisi məlum olan əşyalar var. Biz istəyirik ki, sabit ölçülü çantaya mümkün qədər yüksək məbləğdə şeylər yerləşdirək.

Bu tapşırığın bu variantında əşyaları hissələrə bölmək mümkündür. Məsələn, müxtəlif dənli bitkiləri almaq istəyirik və 1000 qram ya da 512 qram ala bilərik.

Həll:

Əşyaların nisbi qiymətə (dəyər/çəki) görə çeşidlənməsi və çantanı doldurana qədər ən yüksək nisbi qiymətlərin seçilməsi.

Vaxt mürəkkəbliyi: O(n log n), burada n - əşyaların sayı.

Python-da kod nümunəsi:

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 Seqmentlərin örtülməsi məsələsi

Məsələ:

Bir düz xətt üzərində seqmentlər verilmişdir, onların ucları ilə göstərilir (x1, x2), və bir hədəf seqment var. Hədəf seqmentin bütün nöqtələrini əhatə edən minimal sayı seqmentləri tapmaq lazımdır.

Həll:

Seqmentlərin sağ ucuna görə sıraya düzülməsi və cari nöqtəni əhatə edən ən kiçik seqmentin seçilməsi.

Zaman mürəkkəbliyi: O(n log n), burada n - seqmentlərin sayıdır.

Python-da nümunə kod:

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

Sorğu/viktorina

, səviyyə, dərs

Əlçatan deyil

Acgöz algoritmləri

Acgöz algoritmləri

Açıq