Yaklaşık algoritmalar

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.

Örnek çözümü göster

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]))

Kendini test et

Yaklaşık algoritma ne sağlar?
- Kesin çözüm
- Hızlı ve yakın çözüm
- Hiç çözüm
- Rastgele çözüm
Cevabı göster

Hızlı ve yakın çözüm — Yaklaşık algoritma hızlı ve yakın çözüm sağlar.
en büyük bulma
```
best = arr[____]
```
Cevabı göster
```
best = arr[0]
```
Yaklaşık algoritmalar: kavramları eşleştir

approximation

Yaklaşık
ratio

Oran
NP-complete

Zor
hızlı

O(n)

Sıradaki ders: Rastgele algoritmalar

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler