Ağırlıklı matroid - Weighted matroid

İçinde kombinatorik bir dalı matematik, bir ağırlıklı matroid bir matroid kişinin yapabileceği işlevle donatılmış Açgözlü algoritma.

Bir ağırlık fonksiyonu matroid için her bir öğeye kesinlikle pozitif bir ağırlık verir . İşlevi alt kümelerine genişletiyoruz toplama yoluyla; toplamı bitmiş içinde . Ağırlık işleviyle ilişkili bir matroid, ağırlıklı matroid olarak adlandırılır.

Orman algoritmalarını kapsayan

Basit bir örnek olarak, diyelim ki maksimum genişleyen orman bir grafiğin. Yani, her kenar için bir grafik ve ağırlık verildiğinde, her tepe noktasını içeren ve ağaçtaki kenarların toplam ağırlığını en üst düzeye çıkaran bir orman bulun. Bu sorun bazı kümeleme uygulamalarında ortaya çıkmaktadır. Yukarıdaki orman matroidinin tanımına bakarsak, maksimum yayılan ormanın basitçe en büyük toplam ağırlığa sahip bağımsız küme olduğunu görürüz - böyle bir küme grafiği kapsamalıdır, aksi takdirde döngü oluşturmadan kenarlar ekleyebiliriz. Ama onu nasıl bulacağız?

Bir temel bulmak

Temel bulmak için basit bir algoritma var:

  • Başlangıçta izin ver boş küme olun.
  • Her biri için içinde
    • Eğer bağımsızdır, sonra ayarlayın -e .

Sonuç açıkça bağımsız bir kümedir. Maksimum bağımsız bir kümedir çünkü eğer bazı alt kümeler için bağımsız değil nın-nin , sonra bağımsız da değildir (kontrpozitif, kalıtsal mülkiyet ). Bu nedenle, bir öğeyi atlatırsak, onu daha sonra kullanma fırsatımız olmayacak. Daha zor bir problemi çözmek için bu algoritmayı genelleştireceğiz.

Optimal genişletme

Bağımsız bir en büyük toplam ağırlık kümesi denir en uygun Ayarlamak. Optimal kümeler her zaman temeldir, çünkü bir kenar eklenebiliyorsa, olması gerekir; bu yalnızca toplam ağırlığı artırır. Görünüşe göre, önemsiz bir şey var Açgözlü algoritma optimum bir ağırlıklı matroid kümesini hesaplamak için. Aşağıdaki gibi çalışır:

  • Başlangıçta izin ver boş küme olun.
  • Her biri için içinde ağırlıkça azalan sırada (monoton olarak) alınır
    • Eğer bağımsızdır, sonra ayarlayın -e .

Bu algoritma, yukarıdaki algoritmanın özel bir durumu olduğu için bir temel bulur. Her zaman bağımsızlığı korurken alabileceği en büyük ağırlığı seçer (dolayısıyla "açgözlü" terimi). Bu her zaman optimum bir küme üretir: ürettiğini varsayalım ve şu . Şimdi herhangi biri için ile , açık kümeleri düşünün ve . Dan beri den daha küçük bazı unsurlar var içine konulabilir sonuç hala bağımsızdır. ancak eklenebilecek maksimum ağırlık unsurudur bağımsızlığı korumak için. Böylece bazı unsurlarından daha hafif değildir , ve dolayısıyla en az ağırlıkça büyük . Bu herkes için doğru olduğu gibi , daha ağır .

Karmaşıklık analizi

Üyelerini dolaşmanın en kolay yolu onları istenilen sırada sıralamaktır. Bu gerektirir karşılaştırma kullanarak zaman sıralama algoritması. Ayrıca her biri için test etmemiz gerekiyor olup olmadığı bağımsızdır; bağımsızlık testlerinin gerektirdiğini varsaymak süre, algoritmanın toplam süresi .

Bunun yerine bir minimum kapsayan ağaç bulmak istiyorsak, ağırlık fonksiyonunu büyük bir sabitten çıkararak basitçe "ters çeviririz". Daha spesifik olarak , nerede tüm grafik kenarlarında toplam ağırlığı aşıyor. Birçok durumda daha özel özelliklerden yararlanan daha verimli algoritmalar bulunabilmesine rağmen, her tür matroid ve ağırlık fonksiyonuyla ilgili daha birçok optimizasyon problemi bu önemsiz şekilde çözülebilir.

Matroid gereksinimi

Ayrıca bir set alırsak bir matroid değil, "bağımsız" kümeler varsa, açgözlü algoritma her zaman çalışmayacaktır. O zaman bağımsız kümeler var ve ile ama öyle ki hayır dır-dir bağımsız.

Bir seçin ve öyle ki . Öğelerini ağırlıklandırın aralıkta -e unsurları aralıkta -e unsurları aralıkta -e ve geri kalanı aralıkta -e . Açgözlü algoritma, ve sonra herhangi bir öğe seçemezsiniz . Bu nedenle, oluşturduğu bağımsız küme en fazla ağırlıkta olacaktır. ağırlığından daha küçük olan .

Tarih

1971'e kadar değildi Jack Edmonds "Matroidler ve açgözlü algoritma" adlı makalesinde ağırlıklı matroidleri açgözlü algoritmalara bağladı. Korte ve Lovász, bu fikirleri, Greedoids, açgözlü algoritmalarla daha büyük sorun sınıflarının çözülmesine izin veren.

Referanslar

  • Jack Edmonds. Matroidler ve Açgözlü Algoritma. Matematiksel Programlama, cilt 1, s. 125–136. 1971.