Bağlantı, akış ve rotalar · 32 / 53
Euler, Hamilton ve TSP ayrımı
Anla → iz sür → uygula → gerekçelendir
2 dk okuma · uygulama için ayrıca zaman ayırEuler trail her kenarı tam bir kez, Hamilton path her düğümü tam bir kez kullanır. TSP Hamilton tur ararken toplam ağırlığı minimize eden optimizasyon problemidir. “Kargo problemi” tek bir problem adı değildir: edge coverage, vertex visit, shortest route ve vehicle routing farklı modellerdir.
Bağlantılı yönsüz grafın Euler circuit'i bütün dereceler çift olduğunda vardır; açık trail'de iki tek dereceli düğüm olabilir. İzole düğümler edge coverage bağlamında ayrı ele alınır. Hierholzer kullanılmamış kenarlardan yürür, çıkmazda stack'ten çıkarıp sonucu ters sırada kurar. Parallel edges için kullanıldı bilgisini edge ID ile tut.
Hamilton varlığını degree parity ile çözemezsin; genel problem NP-complete'tir. Küçük n için subset DP veya backtracking, büyük optimizasyon problemleri için özel yapı/heuristic/approximation değerlendirilir. Bir Euler turunu bulmak ile bütün Hamilton turlarını enumerate etmek karmaşıklık açısından bambaşkadır.
Adım adım iz sürme
Üçgen A-B-C-A: Euler circuit ve Hamilton cycle vardır. İki üçgenin tek ortak düğümü varsa Euler olabilir ama ortak düğümü tekrarlamadan bütün vertices dolaşan Hamilton cycle olmayabilir.
Maliyet ve varsayımlar
Hierholzer O(V+E). Held–Karp TSP subset DP O(n²2ⁿ) zaman, O(n2ⁿ) alan.
Çalıştırılabilir örnek
Python 3 ile çalıştır. Assert küçük bir örneği denetler; genel doğruluk ispatı değildir. Bazı ileri örnekler özellikle küçük model veya referans oracle'dır; tam üretim uygulaması değildir.
from collections import Counter
edges = [("A","B"),("B","C"),("C","A")]
degree = Counter(v for e in edges for v in e)
assert all(d % 2 == 0 for d in degree.values())
# Even degrees alone need connectivity among non-isolated vertices.KAVRADIĞINI KONTROL ET
Sıra sende
İki ayrı üçgende bütün degrees çift; tek Euler turu var mı?
Çözümün mantığını göster
Hayır. Kenar taşıyan bütün düğümler aynı bileşende olmalıdır. Degree koşulunu connectivity olmadan kullanamazsın.
Bir adım ileri
- Örneği değiştirmeden önce girdi sözleşmesini ve invariantı yaz.
- Uygun olan boş, sınır, tekrar ve adversarial girdileri ekle. Basit bir oracle ile karşılaştır.
- Belirtilen modelde maliyeti çıkar; farklı girdi büyüklüklerini ölç ve farkları gerekçelendir.
Temel kaynaklar ve ders notları
Bu eğitimde özgün anlatım kullanıldı; aşağıdaki kaynaklar ispatlar ve ileri okumalar sunar. Bağlantılar daha geniş ders modülünü kapsayabilir.
Jeff Erickson · Algorithms ↗