Optimal alt yapı - Optimal substructure

Şekil 1. Optimum altyapıyı kullanarak en kısa yolu bulmak. Sayılar yolun uzunluğunu temsil eder; düz çizgiler tek gösterir kenarlar dalgalı çizgiler en kısayı gösterir yollar yani, burada gösterilmeyen başka köşeler olabilir.

İçinde bilgisayar Bilimi bir problem olduğu söyleniyor optimal altyapı eğer optimal bir çözüm, alt problemlerinin optimal çözümlerinden oluşturulabilirse. Bu özellik, bir problem için dinamik programlamanın ve açgözlü algoritmaların kullanışlılığını belirlemek için kullanılır.[1]

Tipik olarak bir Açgözlü algoritma bunun her adımda optimal olduğu tümevarımla kanıtlanabiliyorsa, bir problemi optimal alt yapı ile çözmek için kullanılır.[1] Aksi takdirde, sorunun gösterilmesi koşuluyla örtüşen alt problemler ayrıca dinamik program kullanıldı. Uygun bir açgözlü algoritma yoksa ve problem, üst üste binen alt problemleri göstermede başarısız olursa, çözüm uzayının uzun ama doğrudan araştırılması en iyi alternatiftir.

Uygulamasında dinamik program -e matematiksel optimizasyon, Richard Bellman 's Optimallik İlkesi bir başlangıç ​​döneminden itibaren dinamik bir optimizasyon problemini çözmek için t bazı bitiş dönemlerine Tdaha sonraki tarihlerden başlayarak alt problemleri örtük olarak çözmek zorundadır. s, nerede t . Bu, optimal alt yapı örneğidir. Optimallik İlkesi, Bellman denklemi, sorunun değerinin nasıl olduğunu gösterir. t sorunun değeri ile ilgilidir. s.

Misal

Bulmayı düşünün en kısa yol Şekil 1'de gösterildiği gibi, araba ile iki şehir arasında seyahat etmek için. Böyle bir örnek muhtemelen en uygun alt yapıyı sergileyecektir. Yani, Seattle'dan Los Angeles'a en kısa rota Portland'dan ve ardından Sacramento'dan geçerse, Portland'dan Los Angeles'a en kısa rota da Sacramento'dan geçmelidir. Yani, Portland'dan Los Angeles'a nasıl gidileceği sorunu, Seattle'dan Los Angeles'a nasıl gidilir sorusunun içinde iç içe geçmiş durumda. (Grafikteki dalgalı çizgiler alt problemlerin çözümlerini temsil eder.)

Optimal alt yapıyı sergileme olasılığı düşük olan bir soruna örnek olarak, Buenos Aires'ten Moskova'ya en ucuz uçak biletini bulma sorununu düşünün. Bu bilet Miami ve ardından Londra'daki durakları içerse bile, Miami'den Moskova'ya en ucuz biletin Londra'da durduğu sonucuna varamayız, çünkü bir havayolunun çok uçuşlu bir seyahat sattığı fiyat genellikle fiyatların toplamı değildir. yolculuktaki bireysel uçuşları satacağı.

Tanım

Optimal alt yapının biraz daha resmi bir tanımı verilebilir. Bir "sorun", "alternatifler" toplamı olsun ve her alternatifin ilişkili bir maliyeti olsun, CA). Görev, en aza indiren bir dizi alternatif bulmaktır. CA). Varsayalım ki alternatifler bölümlenmiş alt kümelere, yani her alternatif yalnızca bir alt kümeye aittir. Her alt kümenin kendi maliyet işlevi olduğunu varsayalım. Bu maliyet fonksiyonlarının her birinin minimumları ve küresel maliyet fonksiyonunun minimumları bulunabilir, aynı alt kümelerle sınırlı. Eğer bu minimumlar her bir alt küme için eşleşirse, o zaman küresel bir minimumun tüm alternatifler setinden değil, sadece tanımladığımız daha küçük, yerel maliyet fonksiyonlarının minimumlarından oluşan setten seçilebileceği neredeyse açıktır. Yerel fonksiyonların en aza indirilmesi bir "alt düzey" problemiyse ve (özellikle) bu indirgemelerin sınırlı bir sayısından sonra problem önemsiz hale gelirse, problemin optimal bir alt yapısı vardır.

Optimum alt yapı ile ilgili sorunlar

Problemler olmadan optimal altyapı

  • En uzun yol problemi
  • En düşük maliyetli havayolu ücreti. (Çevrimiçi uçuş aramayı kullanarak, A havalimanından B havalimanına en ucuz uçuşun, C havalimanı üzerinden tek bir bağlantı içerdiğini, ancak A havalimanından C havalimanına en ucuz uçuşun, başka bir D havalimanı üzerinden bir bağlantıyı içerdiğini sık sık bulacağız.) Bununla birlikte, Eğer problem maksimum aktarma sayısını bir parametre olarak alırsa, problemin optimal alt yapısı vardır: A'dan B'ye tek bir bağlantı içeren en ucuz uçuş ya direkt uçuştur; veya A'dan bir C noktasına uçuş, artı C'den B'ye optimum direkt uçuş.

Ayrıca bakınız

Referanslar

  1. ^ a b Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Algoritmalara Giriş (3. baskı). MIT Basın. ISBN  978-0-262-03384-8.