Geri İzleme Algoritması – Bilgisayar Bilimleri Ödevleri – Bilgisayar Bilimleri Ödev Hazırlatma – Bilgisayar Bilimleri Alanında Tez Yazdırma – Bilgisayar Bilimleri Ödev Yaptırma Fiyatları
Basit Bir Geri İzleme Algoritması
İlk yöntem için, bir eşbiçimlilik bulmak için tepe değişmezlerini kullanan bir algoritma veriyoruz. Değişmez ne kadar güçlü olursa, n’den izomorfizm olduğu test edilen fonksiyonların sayısı o kadar az olur! olası olanlar R, ‘<‘ doğrusal sıralı bir küme olsun. inv : V → R bazı köşe değişmezlerini göstersin, örn. inv(v) = d(v) ve R = . Π(V,inv) = V1,…,Vk, V’nin inv’ye göre sıralı köşe bölümü olsun.
G1 = V = {v1,…,vn},E1 ve G2 = W = {w1,…,wn},E2 izomorfizm açısından kontrol edilen iki grafiği göstersin. Algoritmanın çıktısı, {1,…,n}’nin bir φ permütasyonu olacaktır, öyle ki vi → wφ(i), 1 ≤ i ≤ n, G1 ve G2 arasında bir izomorfizm veya ‘izomorfik olmayan’ , eğer izomorfizm yoksa. Algoritma, izomorfizmleri G1 ve G2’nin alt grafikleri arasında adım adım genişletecek ve bir izomorfizm tüm grafiklere genişletilebiliyorsa duracaktır.
Tüm olasılıklar başarısız bir şekilde kontrol edildiyse. Alt grafiklerdeki izomorfizmler φ’ ile gösterilecektir. Herhangi bir φ”nin, {1,…,n}’nin iki altkümesi arasındaki bir eşleştirme olduğuna dikkat edin. Başlangıçta Π(V,inv) = (V1,…,Vk) ve Π(W,inv) = (W1,…,Wk′) hesaplanır.Ifk̸=k′ veya|Vi|̸=|Wi| herhangi bir1≤i≤k için, iki çizge izomorfik olamaz çünkü olası her eşleme env’yi korumaz.
k = k’ ve |V | = |W | ön işlemede başarılı; o zaman İzomorf G1, G2, (Π(V, inv), Π(W, inv), ∅ denir.
İlk olarak, bölümün tüm alt kümeleri arasında minimum kardinaliteye sahip köşe alt kümesi Vi belirlenir; Açıkçası Wi aynı kardinaliteye sahiptir. G1 ve G2 arasındaki herhangi bir φ izomorfizmi, Vi’nin köşelerini Wi’nin köşeleriyle eşlemelidir. Bu nedenle, Vi ve Wi’nin bir tepe noktası arasında bir eşlemeyi düzeltmek ve devam etmek yeterlidir.
En küçük hücre, ‘İzomorfizm OLMAYAN’ı olabildiğince hızlı tespit etme umuduyla seçilir. Şimdi, for döngüsünde eşlemeyi belirliyoruz. Eğer bir φ izomorfizmi varsa, o zaman φ(vi1) ∈ Wi ve bir izomorfizm elde etmek için tüm vi1 → wij eşlemelerinin kontrol edilmesi yeterlidir. φ′ ∪ {vi1 → wij }’yi bir φ izomorfizmine genişletmek hala mümkünse, kalan eşlenmemiş köşelerin eşlemelerini kontrol ederiz. Bu, özyinelemeli bir Isomorph çağrısıyla yapılır.
Nauty Algoritması
Uygulanan bir kanonik etiketi hesaplama yaklaşımına bir örnek, McKay’in nauty algoritmasıdır. Hangi nauty’de henüz otomorfizma yok demektir?
İlk önce McKay’in kanonik bir etiket tanımlama fikrini açıklıyoruz. V = {v1,v2,…,vn} ile yönsüz bir G = (V,E) grafiği için, vδ(1),vδ köşe sırasına göre G’nin komşuluk matrisi Adj(G,δ) olsun. (2),…,vδ(n), burada δ,{1,…,n}’nin bir permütasyonudur. ArdındanCadj tanımlanır.
Adj(G,δ)’nin tüm satırların birleştirilmesiyle türetilen n2 bitlik bir ikili sayı olarak yorumlandığı bir kanonik etiket. İki etiket Cadj(G1) ve Cadj(G2), ancak ve ancak G1 ve G2 izomorfik ise eşittir. Bunun nedeni, minimum bitişiklik matrisinin benzersiz bir şekilde tanımlanması ve iki grafiğin, yalnızca eşit bitişiklik matrislerini veren köşe sıraları varsa izomorfik olmasıdır.
Cadj(G)’yi hesaplamaya yönelik saf yaklaşım, tüm n! köşe sıraları ve her sıra için n × n boyutunda iki bitişik matrisi karşılaştırın. Bununla birlikte, nispeten küçük n değerleri için bile bu, kabul edilebilir bir süre içinde mümkün olmayacaktır.
Bu yaklaşımı hızlandırmak için McKay, bir C(G) etiketini hesaplamak için nauty algoritmasında çeşitli teknikler kullanır. Genel olarak, nauty algoritması n’ye bakmadığından C(G) Cadj(G)’den farklı olacaktır! siparişler ancak özel bir numunede ve aralarındaki minimum matrisi hesaplar.
Backtracking algoritması örnekleri
Backtracking algoritması Nedir
Branch and bound Algoritması
Kaba kuvvet algoritması
Backtracking C++ code
Sezgisel buluşsal algoritmalar
Sezgisel ve meta sezgisel algoritmalar
Arıtma Prosedürü bu numuneleri belirleyecektir. Örnek sayısı grafiğin yapısına bağlıdır, ancak genellikle örnek boyutu n!’den önemli ölçüde küçüktür. Kontrol edilecek tüm köşe sıralarını hesaplamak için nauty algoritması, her bir yaprağın bir tepe sırasına karşılık geldiği bir arama ağacı T kullanır.
Algoritma T’yi kat eder ve ziyaret edilen yaprakların köşe sıraları tarafından indüklenen tüm bitişik matrisleri inceler. Şimdi bir sonraki numara devreye giriyor: tüm yapraklar ziyaret edilmiyor. Grup teorisi, daha kesin olarak, otomorfizm grubu Aut(G) hakkında zaten bilinen bilgi, T’nin alt ağaçlarını geçişten hariç tutmaya izin verir.
Bir alt ağaç, yalnızca şimdiye kadar bulunan en iyi olandan daha küçük olmayan bitişik matrislere yol açan köşe sıralarını içerdiği biliniyorsa budanır. Başta grup teorisi olmak üzere cebir kullanılarak, bu yaklaşımla türetilen C etiketinin gerçekten kanonik olduğu gösterilmiştir.
T’yi budamak için başka bir teknik daha var ama çok soyut olduğu için bölüm notlarında sadece kısaca bahsedeceğiz. Ardından, devam filminde ihtiyaç duyduğumuz grup teorisinden bazı temel bilgileri tanıtacağız.
Grup Teorisinin Temelleri
n elemanın permütasyon grubunu Sn ile gösteriyoruz. Bir δ ∈ Sn elemanı, basitçe {1,…,n} ve {1,…,n} kümeleri arasındaki bir eşleştirmedir. Açıkçası, n var! bu tür ön yargılar. Bir fonksiyon grubundaki iki eleman f ve g’nin çarpımı, bileşimle tanımlanır, yani f · g = f ◦ g. Sonlu bir G grubu ve F ⊆ G öğelerinin bir alt kümesi için G’deki F’nin grup ürünü, tanımlanan ⟨F⟩ alt grubudur.
Bir G grubu, bir σ : G × M → M fonksiyonuna göre bir M kümesi üzerinde çalışır, eğer nötr eleman e ∈ G ve tüm f,g ∈ G ve x ∈ M için σ(e, x) = x ve σ(f ·g, x) = σ(f, σ(g, x)). Daha sonra G ve σ, M üzerinde aşağıdaki şekilde bir denklik ilişkisine neden olur.
x’in denklik sınıfını, yani {σ(f, x) | f ∈ G}, x’in yörüngesi. M’nin G ve σ’ya göre tüm denklik sınıflarının kümesine yörünge bölümü denir. Bizim durumumuzda, bir G = (V, E) grafiğinin otomorfizm grubunun bir Φ ⊆ Aut(G) alt grubu V üzerinde işlem yapacaktır. Bir otomorfizm φ ∈ Φ ve bir v ∈ V tepe noktası için σ fonksiyonu basitçe σ(φ, v) = φ(v) ile tanımlanır.
Backtracking algoritması Nedir Backtracking algoritması örnekleri Backtracking C++ code Branch and bound Algoritması Kaba kuvvet algoritması Sezgisel buluşsal algoritmalar Sezgisel ve meta sezgisel algoritmalar