Las Vegas ve Monte Carlo

Las Vegas ve Monte Carlo algoritmalarını karşılaştırırsın.

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.

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.

Örnek çözümü göster

def approx_ratio(approx, optimal):
    # Yaklaşık oranı hesapla
    return (approx * 10) // optimal
print(approx_ratio(9, 9))

oran hesabı

ratio = (approx * ____) // optimal

Cevabı göster

ratio = (approx * 10) // optimal