Nədir qənaət algoritmi və o, problemlərin həllində…

Qənaət algoritmi, hər addımda lokal olaraq ən yaxşı qərarı qəbul edən və ümid edir ki, bu, qlobal olaraq ən yaxşı həllə gətirib çıxaracaq bir heuristik yanaşmadır.

Tətbiqlər:

Fəaliyyətlərin seçimi problemi:

Problem: Verilmiş bir toplanmadan vaxt baxımından üst-üstə düşməyən ən çox intervalları seçin.
Qənaət həlli: İntervalları artan bitmə vaxtına görə sıralayın. Hər addımda, artıq seçilmişlərlə üst-üstə düşməyən ən kiçik bitmə vaxtına malik intervalu seçin.

# Fəaliyyətlərin seçimi nümunəsi
# activities = [(start_time, end_time)]

activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
activities.sort(key=lambda x: x[1]) # Bitmə vaxtına görə sıralama

selected_activities = []
last_finish_time = -1

for activity in activities:
    if activity[0] >= last_finish_time:
        selected_activities.append(activity)
        last_finish_time = activity[1]

print(selected_activities) # [ (1, 4), (5, 7), (8, 11), (12, 16) ]

Pul dəyişdirmə problemi (Coin Change Problem) kanoik moneta dəstləri üçün:
- Problem: Verilmiş məbləği minimum sayda moneta ilə ödəmək.
- Qənaət həlli: Ən böyük nominalı olan monetaları mümkün qədər çox istifadə edin, məbləğ ödənənə qədər. Bu, yalnız müəyyən moneta dəstləri üçün işləyir (məsələn, 1, 5, 10, 25).
```
# Məsəl üçün, moneta dəyişdirmə nümunəsi (kanoik monetalar üçün)
coins = [25, 10, 5, 1]
amount = 67
result = {}

for coin in coins:
    while amount >= coin:
        result[coin] = result.get(coin, 0) + 1
        amount -= coin

print(result) # {25: 2, 10: 1, 5: 1, 1: 2}
```
Kruskal alqoritmi ilə minimal yayılma ağacını tapmaq:
- Problem: Bütün düyünləri ən az ümumi çəkisi ilə bağlayan, əlaqəli, çəkili, yönəldilməmiş qrafın kənarlarının alt toplusunu tapın.
- Qənaət həlli: Bütün kənarları çəkisinə görə artan sırayla sıralayın. Onları ardıcıllıqla əlavə edin, əgər artıq seçilmiş kənarlarla döngü yaratmırlarsa, n-1 kənar əlavə olunana qədər (n, düyünlərin sayı) davam edin.

Qənaət alqoritmləri asandır tətbiq etmək, lakin hər zaman qlobal olaraq optimal həll tapmır. Bəzi problemlər üçün (məsələn, moneta dəyişdirmə, ümumi çantanın problemi) qənaət yanaşması optimal deyil. Optimal və ya daha yaxşı yaxınlaşma təmin etmək üçün dinamik proqramlaşdırma və ya digər metodlar lazım ola bilər. Qənaət alqoritmindən istifadə etməzdən əvvəl, onun bu problem üçün uyğun olub-olmadığını yoxlamaq vacibdir.

Nədir qənaət algoritmi və o, problemlərin həllində necə tətbiq olunur?