arşiv

yazılar buna göre etiketlendi; ‘algoritma’

Çizge Algoritmaları?

Pazar, 25 Nis 2010

Son projeme başladığımdan beri üniversitede öğrendiklerim daha bir işe yaramaya başladı. Hatta ilginçtir,  aklımda biraz daha bişeyler kalmış olsa daha iyi olurdu dediğim bir ders bile var, Graph Algorithms (Çizge Algoritmaları). Burada beni en çok düşündüren 2 problemi yazayım istedim, sonradan baktığımda “vay be, zamanında bunlarla da uğraşmışım” diyebilmek için. Ama tabii konu ile ilgili paylaşmak istediğiniz bir fikir varsa beklerim, hatta çok da memnun olurum.

Soruların ilki bir graphta ring (cycle, circuit, yuvarlak,… ne isim verirseniz artık) belirlemekle ilgili. Elimizde undirected bir graph var diyelim. Bunun içindeki elementary cycle ları bulup listelememiz gerekiyor. Graphta sadece cycle olup olmadığını belirlemek yetmiyor yani. Elementary cycle, sadece başlangıç nodunu 2 defa, diğer nodeları sadece 1 defa içeren cycle demek. Yazacağımız algoritma örneğin aşağıdaki graphta çalıştırıldığında şu sonuçları vermeli: 1 – 2 – 5 – 1, 1 – 2 – 3 – 4 – 5 – 1, 2 – 3 – 4 – 5 – 2.  1 – 2 – 3 – 4 – 5 – 2 – 1 gibi bir sonuç çıkmamalı çünkü bu sonuç elementary bir cycle değil.

Soru basit aslında. Ama verimli bir algoritma yazmak o kadar basit değil maalesef. Problemin boyutunun farkına varmadan oturup kendim çalışan bir kod yazdım aslında bununla ilgili. O da basitçe anlatmak gerekirse graphtaki her bir node a gidip o nodun bağlı bulunduğu bütün cycle ları buluyor. Bir yandan bulunan bütün cyclelar bir liste halinde tutuluyor, yeni bulunan cycle ın daha önce bulunanlardan farklı olduğu anlaşıldığında bu cycle da listeye ekleniyor.

Bu çözüm aslında 2 sorunu da beraberinde getiriyor. Bunlardan ilki, her node için yapılan aramada graphtaki node ve edge lerin tamamının dolaşılıyor olması, yani yavaşlık. İkincisi ise boş yere yapılan aramalar. Örneğin bir cycleda 10 node var diyelim, aynı cycle bu 10 nodun her biri için tekrar bulunuyor, bir de sonra tekrardan bu cycle bulunmuş muydu diye karşılaştırma yapılıyor. Yani yine yavaşlık. Büyük graphlar için tahminen feci yavaş çalışan bir algoritma yani bu.

Neyse, bunun farkına vardıktan sonra internette zaten paralel bir şekilde yaptığım araştırmaları biraz daha hızlandırdım ve bu konu ile ilgili yazılmış olan bir makale buldum. Etraflıca düşünmeden makalenin üzerine atladım, araya başka işler girdiği için hemen yazamadım ama sonunda bu hafta başında çalışır bir kod vardı elimde. Tam ne güzel yazdım, hallettim diye sevinirken benim akıllılığım ortaya çıktı, bu algoritmanın directed graphlar için yazılmış olması ve benim undirected graphı kolayca directed grapha çeviririm nasılsa düşüncem bir anda çöküverdi. Bunun üzerine tabii şöyle büyük bir bardak soğuk su içtim, sonrasında cidden undirected graphlar için yazılmış olan bir makale var mı onu araştırmaya başladım. Şunu ve bunu buldum şimdilik ama makalelerin orijinallerine ulaşamadığım için halen bunlar işe yarar mı bilmiyorum. Üniversite ağından bu yazıyı okuyan arkadaşlar makaleleri gönderebilirlerse süper olur hatta, sade vatandaşa paralı çünkü makaleler.

Geldik ikinci probleme. Şimdiden söyleyeyim, daha problem tanımı değişebileceği için uygulanacak çözüm de değişmek durumunda kalabilir ama her şekilde enteresan gördüğüm bir problem olduğu için yazıyorum buraya. Olay networkte dolaşan frameleri numaralandırmak ile ilgili. Elimizde bir network var diyelim, burada dolaşacak olan her bir frame i de önceden bildiğimizi kabul edelim. Bu dolaşacak framelere birbirinden farklı numaralar vermemiz gerekiyor. Networkte IO Controllerlar (IOC) ve IO Devicelar (IOD) var. Frameler ya bir IOC ile bir IOD arasında (genel durum), ya da bir veya birkaç IOC arasında (sayıları IOC – IOD framelerinden genelde daha az) transfer ediliyor, yani başlangıç ve bitişi IODler olan frameler yok. Networkü oluşturan graph connected, yani herhangi bir başlangıç nodunu seçtiğimiz zaman oradan diğer bütün nodelara ulaşabiliyoruz. Graphta cyclelar olması mümkün, hatta işi zorlaştıran kısım bu cycle lar. Yolculuğu sırasında herhangi bir cycle a ait bir node dan geçen bir frame a bandından, hiçbir cycle la alakası olmayan bir node da b bandından numara alıyor. Bu bantlar da birbirine bitişik. b bandı x ile y arası numaraları kapsarken a bandı da y+1 ile z arası numaraları kapsıyor.

Sorunun sıkıntılı kısmı şu: Her bir node (IOC ya da IOD) kendi üzerinden geçen framelerin numaralarını bir yerde tutuyor. Yalnız bu frameler öyle numaralandırılmalı ki bir nodun tuttuğu frame numaralarının en büyüğü ile en küçüğü arasındaki fark, o nodun maksimum tutabileceği farkı geçmesin. Örneğin bir node için bu değer 512 ise bizim verdiğimiz frame numaralarının en büyüğü ile en küçüğü arasındaki fark 512 den küçük olmalı. Bu değer her bir node için farklı bir değer olabilir.

Soruyu biraz daha elle tutulur hale getirebilmek için bir örnekle birlikte tekrar anlatmaya çalışayım:

Bu graphta dolaşan frameler de şu şekilde olsun: IOC1-IOD1, IOD1-IOC1, IOC1-IOD2, IOD2-IOC1, IOC1-IOD3, IOD3-IOC1, IOC2-IOD4, (her bir IOD ile o sütunun başındaki IOC arasında 2 frame şeklinde doldurulacak)…,IOD8-IOC3, IOC2-IOC4.

Her bir noddan geçen frameler de şu şekilde olmuş oluyor (Birkaç node için örnek):

IOC1 –> IOC1-IOD1, IOD1-IOC1, …, IOD3-IOC1

IOD1 –> IOC1-IOD1, IOD1-IOC1, IOC1-IOD2, IOD2-IOc1, IOC1-IOD3, IOD3-IOC1

IOC3 –> IOC3-IOD8, IOD8-IOC3, IOC2-IOC4

Bu örnekte IOC3 için bu maksimum fark değerinin 5 olduğunu varsayalım. Böyle bir durumda diğer her bir node için olan fark değerlerinden bağımsız, IOC3 üzerinden geçen frame numaraları birbirine çok yakın olmalı. IOC3 üzerinden geçen framelere baktığımızda IOC2-IOC4 frameinin cycle üzerinden geçen bir frame olduğu görülebilir. Bu frame için cycle frame bandı kullanılacağı için algoritma bu node üzerinden geçen bütün frameleri y’ye mümkün olduğunca yakın tutmaya çalışmalıdır. Örnek bir çözümdeki frame numaraları şöyle olabilir: IOC3-IOD8: y-1, IOD8-IOC3: y-2, IOC2-IOC4: y

Neyse, soru bu. Dediğim gibi daha üzerinde çok fazla düşünmeye vaktim olmadı. Bu soru gerçekten bana patlarsa daha sonra bulduğum çözümü de buraya yazarım. Bu arada dediğim gibi herhangi bir soruya, fikre ve çözüme de açığım.

Güncelleme: İlk problemle ilgili makaleleri sağolsun Soner gönderdi. İlk incelediğim makalede pek iş yoktu ama ikincisi beni tam anlamıyla kurtardı.  Makalede o zamana kadar bu problem ile ilgili yazılmış olan algoritmalar karşılaştırılmış. Sonuç olarak benim de implemente ettiğim Johnson’un algoritmasının içlerindeki en hızlısı olduğu sonucuna varılmış (O(e+n)(c+1), e: Edge sayısı, n: Node sayısı, c: Cycle sayısı). Ayrıca daha da güzeli, bu algoritmanın undirected graphlara nasıl uygulanabileceği de yazılmış, aslında tam da benim ilk başta yaptığım çevrim yapılmış.  Benim bu çevrimin çalışmayacağını düşünme sebebim, yöntemin kendisinin de çevrim sırasında orijinal undirected graphta olmayan cycleların ortaya çıkmasına sebep olmasıydı. Düşünemediğim şey ise bu sonradan çıkan cycleların sayısının aslında o kadar da çok olmamasıymış (Orijinal undirected graphta c cycle varsa directed çevriminde 2c+e kadar). O nedenle algoritma koştuktan sonra mantıklı bir eleme yapılabiliyor. Hatta şimdi yazarken aklıma geldi, diğer bir optimizasyon da bu algoritmanın verilen graphta gerçekten cycle varsa koşmasının sağlanması olabilir, bu sayede örneğin büyük graphlarda e fazladan ortaya çıkan e kadar cycle aranmak durumunda kalınmaz.

Bilgisayar , , , , , , , , , , ,