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 kenarları , dalgalı çizgiler en kısa yolları belirtir , yani burada gösterilmeyen başka köşeler olabilir.

Olarak bilgisayar biliminin , bir sorun olduğu söylenir uygun alt yapı , optimal bir çözüm kendi alt problemlerden uygun solüsyonlardan inşa edilmesi mümkün bulunmaktadır. 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.

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

Uygulanmasında dinamik programlama için matematiksel optimizasyon , Richard Bellman 'ın En iyilik prensibi bazı başlangıç dönemi bir dinamik optimizasyon problemi çözmek amacıyla fikrine dayanmaktadır t bazı bitiş dönemine T , bir örtülü başlayarak altproblemleri çözmek zorundadır daha sonra tarih s , t <s <t . Bu, optimal bir alt yapı örneğidir. En iyilik Prensibi türetmek için kullanılır Bellman denklemi başlayarak sorun değerini gösterir, t başlayarak sorun değerine ilgilidir s .

Misal

Şekil 1'de gösterildiği gibi, iki şehir arasında araba ile seyahat etmek için en kısa yolu bulmayı düşünün . Böyle bir örnek muhtemelen en uygun alt yapıyı sergileyecektir. Yani, Seattle'dan Los Angeles'a giden en kısa rota Portland'dan sonra da Sacramento'dan geçerse, Portland'dan Los Angeles'a giden 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.)

Optimum altyapı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 altyapının biraz daha resmi bir tanımı verilebilir. Bir "problem", "alternatifler" toplamı olsun ve her alternatifin ilişkili bir maliyeti, c (a) olsun . Görev, c (a) ' yı en aza indiren bir dizi alternatif bulmaktır . Alternatif olabilir varsayalım paylaştırıldı alt-grup halinde, yani her bir alternatif sadece bir alt-kümesi aittir. Her alt kümenin kendi maliyet işlevi olduğunu varsayalım. Bu maliyet fonksiyonlarının her birinin minimumları, küresel maliyet fonksiyonunun minimumları gibi , aynı alt kümelerle sınırlı olarak bulunabilir . Eğer bu minimumlar her bir alt küme için eşleşirse, o zaman küresel bir minimumun tüm alternatifler kümesinden değil, yalnızca tanımladığımız daha küçük, yerel maliyet fonksiyonlarının minimumlarından oluşan kümeden 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

Optimum altyapısı olmayan sorunlar

  • En uzun yol problemi
  • Toplama zinciri üs alma
  • 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. Eğer problem bir parametre olarak maksimum aktarma sayısını alırsa, problemin optimal alt yapısı vardır: A'dan B'ye tek bir bağlantıyı içeren en ucuz uçuş ya direkt uçuştur; veya A'dan herhangi 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 .