Özet - Approximation and randomized
- Algoritmalar kursu
- Uzman seviye
- Ders 12/41
- 4 dk
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.
Başlangıç kodu
def is_within_factor(approx, optimal, factor):
# Çözüm faktör içinde miÖrnek çözüm
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))Beklenen çıktı
True
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Bir 2-yaklaşık algoritma en kötü durumda ne verir?
- Optimalın en fazla iki katı Doğru cevap
- Optimal
- Üstel zaman
- Hiç çözüm
Açıklama: 2-yaklaşık algoritma optimalın en fazla iki katını verir.
2 karşılaştırma
Soru
if approx <= optimal * ____:
Cevap
if approx <= optimal * factor:Açıklama: factor doğru.
3 Özet - Approximation and randomized: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
find_max |
Maksimum |
sample_max |
Örneklem |
approx_ratio |
Oran |
factor |
Çarpan |