Las Vegas ve Monte Carlo
- Algoritmalar kursu
- Uzman seviye
- Ders 11/41
- 4 dk
Las Vegas ve Monte Carlo algoritmalarını karşılaştırırsın.
Las Vegas ve Monte Carlo
Las Vegas algoritmaları her zaman doğru sonuç verir; süre rastgele. Monte Carlo algoritmaları ise sabit sürede biter ama sonuç olasılıklıdır.
Hangisini kullanacağız, soruna bağlıdır. Kesin sonuç gerekiyorsa Las Vegas; hızlı sonuç gerekiyorsa Monte Carlo.
Yaklaşık oranı
Bir yaklaşık çözümün kalıtesi, approx / optimal oranıyla ölçülür. Oran 1'e ne kadar yakınsa çözüm o kadar iyidir.
2-yaklaşık algoritma, en kötü durumda optimimin iki katına kadar çözüm verebilir. Bu, NP-complete problemler için kabul edilebilir.
Uygulama approx_ratio fonksiyonu
approx_ratio(approx, optimal) yaz. (approx * 10) // optimal döndür (oranı 10 ile ölçekle). print(approx_ratio(9, 9)) ile 10 yazdır.
Başlangıç kodu
def approx_ratio(approx, optimal):
# Yaklaşık oranı hesaplaÖrnek çözüm
def approx_ratio(approx, optimal):
# Yaklaşık oranı hesapla
return (approx * 10) // optimal
print(approx_ratio(9, 9))Beklenen çıktı
10
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Las Vegas ve Monte Carlo: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
Las Vegas |
Kesin |
Monte Carlo |
Olasılıklı |
süre |
Sabit olmayan |
sonuç |
Doğru |
2 Yaklaşık oranı 1 ne anlama gelir?
- Optimalden kötü
- Optimalın iki katı
- Üst sınır yok
- Optimal Doğru cevap
Açıklama: Oran 1, çözümün optimal olduğunu gösterir.
3 oran hesabı
ratio = (approx * ____) // optimalratio = (approx * 10) // optimalAçıklama: 10 doğru.