Yaklaşık algoritmalar
- Algoritmalar kursu
- Uzman seviye
- Ders 9/41
- 4 dk
Polinomsal zamanda yaklaşık çözüm veren algoritmaları öğrenirsin.
Yaklaşık algoritmalar
NP-complete problemler için kesin çözüm üsteledir. Yaklaşık algoritma, kabul edilebilir sürede kalıteli ama kesin olmayan çözüm üretir.
Yaklaşık oranı (approximation ratio), çözümün optimima ne kadar yakın olduğunu ölçer. Örneğin 2-yaklaşık algoritma en fazla iki kat kötü sonuç verir.
En büyük bulma
Bir dizinin en büyük elemanını bulmak, yaklaşık algoritmalar için basit bir başlangıçtır. Doğrusal tarama ile kesin çözüm O(n)'dir.
Bu örnek, yaklaşık algoritmaların temelindeki 'iyi çözüm' kavramını gösterir. Sonraki adımlarda yaklaşık ve rastgele yöntemleri inceleyeceğiz.
Uygulama find_max fonksiyonu
find_max(arr) yaz. Dizinin en büyük elemanını döndür. print(find_max([3, 5, 7, 1, 9])) ile 9 yazdır.
Başlangıç kodu
def find_max(arr):
# En büyük elemanı bulÖrnek çözüm
def find_max(arr):
# En büyük elemanı bul
best = arr[0]
for i in range(1, len(arr)):
if arr[i] > best:
best = arr[i]
return best
print(find_max([3, 5, 7, 1, 9]))Beklenen çıktı
9
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Yaklaşık algoritma ne sağlar?
- Kesin çözüm
- Hızlı ve yakın çözüm Doğru cevap
- Hiç çözüm
- Rastgele çözüm
Açıklama: Yaklaşık algoritma hızlı ve yakın çözüm sağlar.
2 en büyük bulma
best = arr[____]best = arr[0]Açıklama: 0 doğru.
3 Yaklaşık algoritmalar: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
approximation |
Yaklaşık |
ratio |
Oran |
NP-complete |
Zor |
hızlı |
O(n) |