Azaltma

Bir problemi başka bir probleme azaltmayı öğrenirsin.

Azaltma

Azaltma (reduction), bir problemi başka bir probleme dönüştürmektir. Eğer A, B'ye polinom zamanda azaltılırsa ve B çözülürse A da çözülür.

Bu teknik, NP-complete problemleri kanıtlamak için kullanılır. Yeni bir problemin NP-complete olduğunu göstermek için bilinen bir NP-complete problemi ona azaltılır.

Çözüm doğrulama

Bir alt kümenin toplamı hedefe eşit mi diye doğrulama O(n)'dir. Bu, subset sum'in NP'de olduğunu gösterir.

Doğrulama polinom zamanda yapılır; bu yüzden subset sum NP'dedir. Ama çözümü bulmak NP-complete'tir.

Uygulama verify_subset fonksiyonu

verify_subset(arr, subset, target) yaz. subset'in toplamı target'a eşit mi döndür. print(verify_subset([3, 5, 7], [3, 7], 10)) ile True yazdır.

Örnek çözümü göster

def verify_subset(arr, subset, target):
    # Alt kümenin toplamı hedefe eşit mi
    return sum(subset) == target
print(verify_subset([3, 5, 7], [3, 7], 10))

Kendini test et

Azaltma: kavramları eşleştir

A → B

Azaltma
polinom

Hızlı
B çözülür

A çözülür
NP-complete

Hedef
Subset sum'in doğrulaması ne kadar sürede?
- O(1)
- O(2^n)
- O(n²)
- O(n)
Cevabı göster

O(n) — Doğrulama O(n)'dir; sadece alt kümenin toplamı hesaplanır.

toplam hesabı

return sum(____) == target

Cevabı göster

return sum(subset) == target

Sıradaki ders: Özet - NP-completeness

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler