Browse By

Kapsama Problemi – Rota Algoritması

Ayrık Matematik Kapsama Problemi  konusunda mutlak satır olması ve Kapsanan satır, sütun olması durumlarında kapsamanın yazılmasını anlatmıştık. Bu yazıda ise Rota Algoritması ‘nı anlatmayı deneyeceğim.

Eğer oluşturulan tabloda mutlak satır yoksa, kapsanan satır ve sütun bilinmiyorsa “ Rota Algoritması ” ndan yararlanılır. Sezgisel olan bu algoritmanın adımları aşağıdaki gibidir;

  1. Sütun ağırlıkları hesaplanır ve minimum ağırlığa sahip satırlar işaretlenir. (sütun ağırlığı  o sütunda bulunan tüm 1’lerin toplamı demektir.)
  2. 2.  Sk = m ∑ 1/αi ,    i = 1, 2,….t
    İşaretlenmiş satırların (sütun ağırlığı en az olan sütunlarda 1 değeri olan satırlardır.) ağırlıkları yukarıdaki formül ile hesaplanır. Burada  Sk -> k. Satırın ağırlığı, m -> satır sayısı, t -> satırdaki “1” değerinin bulunduğu sütundaki toplam 1’lerin sayısı,  αi -> satır 1’leri demektir.
  3. Minimum ağırlığa sahip olan satır seçilerek tablodan silinir.
  4. Mutlak satırlar kapsamaya dahil edilir ve tablo sıfırlanana kadar 1-3 adımları tekrarlanır.

rotaalgoritmasi1

Öncelikle sütun ağırlığını hesaplıyoruz, örneğin birinci sütun için 1. satırda, 6. satırda 8. ve 9. satırlarda 1 vardır yani toplamda 4 tane bunu yeşil renkle tablonun altına yazdık. Tüm satırlar için bu işlemi yaptıktan sonra minimum ağırlıklı sütunları işaretliyoruz. Bu tablo için minimum ağırlıklı olan sütunlar altında nokta bulunan 2 ağırlıklı 2. 6. 9. ve 10. sütunlardır.

rotaalgoritmasi2

 

Bu sütunlarda 1’i bulunan satırların verilen formül ile ağırlıkları hesaplayıp tablonun sağ tarafına yazdık, örneğin 2. sütun için 2. ve 3. satırlardır. Hepsi için satır ağırlıklarını bulduktan sonra minimum ağırlıklı -9- olan 6. satırı tablodan siliyoruz. 6. satırı tablodan çıkardıktan sonra oluşan mutlak satırları  kapsamaya dahil edip o satırları ve kapsadıkları sütunları da tablodan çıkarıyoruz. Tabloda kapsanmayan satır ve sütun kalmayana kadar işlemleri tekrar ediyoruz. (tabloda ilk aşamada 5. satır ağırlığı 9 çıkmaktadır, 6. ve 3. satır çıkarıldıktan sonra ikinci aşamada 9.7 çıkmaktadır, isterseniz ilk aşamada 6. satır yerine 5. satırı da silebilirsiniz.)

rotaalgoritmasi3

rotaalgoritmasi4

 

  1. satır mutlak satır olduğundan kapsamaya dahil edilerek 3. ,  4. ve 10. sütunlar tablodan silinir ve minimum kapsama olarak π = { 3, 8, 4 } elde edilir.

-> Satır ve sütun ağırlıklarının birbirine eşit olduğu durumlarda algoritmanın devam ettirilebilmesi için rastgele bir satır kapsamaya dahil edilerek işlemlere devam edilir.

 

2 thoughts on “Kapsama Problemi – Rota Algoritması”

  1. onrcvk says:

    Merhaba acaba bu yazıların devamı gelicek mi zira bu kapsama ile ilgili internette çok az bilgi var ve bu site cidden işime yarıyor (Özellikle önümüzdeki haftalarda olacak olan ayrık matematik vizem için 🙂 Ayrıca bu konuların anlatıldığı önerebileceğiniz herhangi bir kitap,site, kaynak var mı ?

    1. Mrs.BytE says:

      en kısa sürede tamamlarım yazının devamını, belirli bir kaynak yok elimde ders notlarını kullanıyorum genelde ama Vasif Nabiyev’in “Algoritmalar” adında bir kitabı var bazı konular içinde var sanırım.

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir