Özet - Approximation and randomized

Rastgele yaklaşık çözümü yazdıran mini görev yaparsın.

Özet - Approximation and randomized

Bu grupta yaklaşık ve rastgele algoritmaları öğrendin. Yaklaşık oranı, Las Vegas ve Monte Carlo birleşince NP-complete problemlere pratik yaklaşımlar mümkün olur.

Şimdi tüm parçaları bir araya getiren bir fonksiyon yazacaksın. Bu özet, grubun kavramlarını tek bir kodda birleştirir.

Uygulama is_within_factor fonksiyonu

is_within_factor(approx, optimal, factor) yaz. approx <= optimal * factor ise True döndür. print(is_within_factor(9, 9, 2)) ile True yazdır.

Örnek çözümü göster

def is_within_factor(approx, optimal, factor):
    # Çözüm faktör içinde mi
    if approx <= optimal * factor:
        return True
    return False
print(is_within_factor(9, 9, 2))

Kendini test et

Bir 2-yaklaşık algoritma en kötü durumda ne verir?
- Optimalın en fazla iki katı
- Optimal
- Üstel zaman
- Hiç çözüm
Cevabı göster

Optimalın en fazla iki katı — 2-yaklaşık algoritma optimalın en fazla iki katını verir.

karşılaştırma

if approx <= optimal * ____:

Cevabı göster

if approx <= optimal * factor:

Özet - Approximation and randomized: kavramları eşleştir

find_max

Maksimum
sample_max

Örneklem
approx_ratio

Oran
factor

Çarpan

Sıradaki ders: KMP algoritması

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler