Algoritmalar – Multimedya Bölümü – Multimedya Bölümü Ödevleri – Multimedya Bölümü Tez Yaptırma –Multimedya Bölümü Ödev Ücretleri

 Algoritmalar

Karar ağacı, etiketlenmemiş tek bir kök düğümden başlayarak oluşturulur. Bu kök düğümün birinci düzey torunları, her bir benzersiz, tek öğeli satır sütun öğesiyle ark etiketlidir. Toplamda altı olası permütasyon vardır; ancak, yalnızca iki benzersiz tek öğeli satır-sütun öğesi vardır.

Bu nedenle, a ve b etiketli yaylarla kök düğümden iki alt öğe vardır. Bu düğümlerin her birinden sonraki olası her satır-sütun elemanı için bir yay eklenerek ağaç devam ettirilir.

Böylece, b etiketli yaydan, bitişik matrisler arasında üç olası sonraki satır-sütun elemanı vardır, bu nedenle üç alt öğe vardır. Süreç, gösterildiği gibi, model ve permütasyonları ağacın yaprakları olacak şekilde, ağaç olası tüm bitişik matrisleri ifade edene kadar devam eder.

Aynı süreç kullanılarak karar ağacına ek grafikler eklenebilir, gerektiğinde yeni düğümler ve yaylar oluşturulabilir. İzomorfik alt çizgeleri paylaşan çizgelerin avantajı, paylaşılan her bir alt çizgenin ağaçta yalnızca bir kez temsil edilmesiyle hemen görülür. Bunun basit bir örneği, {C} ve {F} matrislerini temsil eden düğümlerin atası olarak bir düğümün kullanıldığı görülmektedir.

Bir giriş grafiğinden (GI) model grafiklere (Mi) izomorfizmlerin tespiti, giriş grafiğini temsil eden komşuluk matrisi kullanılarak gerçekleştirilir. GI’yi oluşturan satır-sütun öğeleri, iki sonlandırma koşulundan biriyle karşılaşılıncaya kadar karar ağacının yaylarında gezinmek için kullanılır.

Sonlandırma koşulları şunlardır:

1. GI matrisinin tüm satır-sütun elemanları bir yayda gezinmek için kullanılmıştır.
2. GI’dan bir sonraki satır-sütun elemanıyla eşleşen bir satır-sütun elemanı ile etiketlenmiş geçerli düğümden inen bir yay yoktur.

İlk sonlandırma koşuluyla karşılaşılırsa, ulaşılan son düğümle ilişkili tüm modellerin GI girişine izomorfik bir alt grafiği vardır. İkinci sonlandırma koşulu, GI girdisinden karar ağacında temsil edilen modellerin hiçbirine alt çizge izomorfizmi olmadığını gösterir.

Karar ağacı tarafından grafik ve alt grafik izomorfizm tespiti, giriş grafiklerinin çevrimiçi sınıflandırması için son derece hızlı bir algoritma sağlar. Bununla birlikte, hesaplama karmaşıklığı olumlu olsa da, uzay karmaşıklığı en büyük dezavantajdır.

Tam bir karar ağacı için elde edilebilecek en iyi uzay karmaşıklığı O(L | lv | (1 + | le |2)n)’dir. Burada L, veri tabanındaki modellerin sayısı, lv, farklı köşe etiketlerinin sayısı, le, farklı kenar etiketlerinin sayısı ve n, model grafiklerindeki köşelerin sayısıdır. Algoritmanın uygulanabilirliği üzerindeki kısıtlamalarla karar ağacını budamak için kullanılabilen bir dizi buluşsal yöntem vardır.

Algoritma Nedir Örnekleri
Algoritma Örnekleri
Algoritma cesitleri
Algoritma Nedir Kısaca
algoritma
Algoritma PDF
Algoritma cümle içinde kullanımı
Veri Yapıları ve Algoritmalar – PDF

Etiket sayısının sınırlı olduğu uygulamalar için karar ağacı algoritması, O(n2) zamanında girdi ile model veritabanı arasındaki çizge ve alt çizge izomorfizmlerini saptar; burada n, girdideki köşe sayısıdır.

Bu nedenle hesaplama karmaşıklığı, hem veri tabanındaki model sayısından hem de modellerdeki köşe sayısından bağımsızdır. Bu, genellikle tam eşbiçimlilik tespitine uygulanan algoritmayla, O(Lmnn2) hesaplama karmaşıklığına sahip Ullman algoritmasıyla iyi karşılaştırılır; m, modellerdeki köşe sayısıdır.

Karar ağacı algoritması, daha önce belirtildiği gibi, tam grafik ve alt grafik izomorfizm tespiti için hızlı bir çözüm sunsa da, bir veritabanında genellikle tam eşleşmeler yoktur. Daha sıklıkla görev, sorgunun kademeli olarak iyileştirilmesine izin vermek için en iyi tam olmayan eşleşmeleri tespit etmektir.

Messmer ve Bunke tarafından önerilen karar ağacı algoritmasının yararlı, kesin olmayan izomorfizm saptama yöntemi yoktur. Bir sonraki bölüm, benzerlik ölçüsü olarak LCSG’yi kullanan orijinal algoritmanın, kesin olmayan eşbiçimlilik tespitine yönelik bir uzantısını sunar. Bu algoritma, görüntü ve video veritabanlarında en sık bulunan benzerlik bulma görevi için çok uygundur.

Karar Ağacı Tabanlı LCSG Algoritması

Geleneksel algoritmalar tarafından iki grafik arasındaki en büyük ortak alt grafiğin saptanması, her iki grafiğin köşe sayısında üstel olan hesaplama karmaşıklığına sahiptir. Model grafiklerinden oluşan bir veritabanı ve bir girdi verildiğinde, bu, model sayısının doğrusal faktörü ile birleştirilir.

Önceki bölümde sunulan karar ağacı algoritması, bir girdi grafiği ile bir model grafikleri veritabanı arasında LCSG’nin hızlı bir şekilde algılanmasını sağlar, bu da hızlı yürütmeyi sürdürürken çok sayıda izomorfizmi algılamayı mümkün kılar. Bir giriş grafiği ile bir model grafik veritabanı arasındaki LCSG’nin saptanması için burada sunulan algoritma bu yaklaşımı benimser.

Karar ağacı algoritması başarısızlıkla sona erdiğinde, karar ağacında bir yaydan aşağı inmek için kullanılmamış bir veya daha fazla satır-sütun elemanı olacaktır. En basit durumda, başarısızlığın nedeni olan böyle bir satır-sütun elemanı olacaktır.

Bununla birlikte, birçok durumda, başarısızlığa neden olanın altında başka satır-sütun öğeleri olacaktır ve bu satır-sütun öğelerinden bir veya daha fazlasının daha aşağı inmek için kullanılması mümkündür.

Karar ağacına göre sınıflandırıldığında yalnızca ilk satır-sütun öğesiyle eşleşen bir bitişiklik matrisini gösterir. İkinci satır-sütun öğesi için eşleşme yok; ancak matris, ikinci ve üçüncü satır-sütun öğeleri değiştirilecek şekilde değiştirilirse, iki satır-sütun öğesi eşleştirilebilir.

Açıkça, kullanılan girdi komşuluk matrisinin en büyük bölümünü temsil eden karar ağacındaki en derin iniş, belirli girdi grafiği ve model veritabanı için mümkün olduğu kadar çok köşe kullanarak bir alt çizge izomorfizmi verir. Bu, girdi ile veritabanındaki modeller arasındaki bir LCSG’dir.

Böyle bir en derin düşüşü belirlemek için, giriş bitişiklik matrisini, kullanılamayan satır-sütun öğeleri matrisin sağ alt köşesinde olacak şekilde değiştirmek gerekir.

Bunu başarmak için, bitişiklik matrisi mümkün olduğu kadar derinlemesine sınıflandırılır, ardından arızaya neden olan satır-sütun elemanı, matristeki son satır-sütun elemanı konumuna göre değiştirilir. Aynı satır-sütun öğesini eşleştirmek için tekrarlanan girişimleri önlemek için, girdideki kullanılabilir köşelerin sayısı için geçici bir sayaç tutulur.

Bu sayaç, mevcut kümeden bir satır-sütun elemanı değiştirildiğinde her seferinde azaltılır. Bir noktada, olası tüm eşleşen satır-sütun öğeleri ağacın aşağısına inmek için kullanılmış olacaktır. Bu noktada giriş komşuluk matrisi gösterildiği gibi iki parçaya bölünür.

Makale Deniz

Biyografinin Tamamını Gör