Sabit Maliyet Araması (Uniform Cost Search)
Home / graf teorisi (graph theory, çizge kuramı) • veri yapıları • yapay zeka (artificial intelligence) / Sabit Maliyet Araması (Unifor ...
Bilgisayar bilimlerinde arama algoritmaları için kullanılan bir terimdir. Algoritma ağırlıklı graflar (weighted graphs) üzerinde çalışmaktadır. Ağaçlar da bir graf örneği olduğu için algoritmanın ağaçlar üzerinde çalışması da mümkündür. Algoritma basitçe aşağıdaki şekilde tanımlanabilir:
Kök düğümden başla (root node)
En düşük maliyetli komşuya git
Şayet aranan düğüm bulunduysa bit, bulunmadıysa 2. Adıma geri dön
Yukarıdaki 3 basit adımla açıklanabilen algoritmanın çalışmasını aşağıdaki temsili graf üzerinden açıklamaya çalışalım:
Yukarıdaki şekilde A düğümünden başladığımızı ve F düğümüne ulaşmak istediğimizi düşünelim. Algoritma ilk başta A düğümünün komşularının maliyetini çıkarır ve en az maliyetli komşuya gider.
Yukarıda gösterildiği üzere A düğümünün komşusu iki düğüm vardır. B ve E düğümleri bu sayede kontrol edilmiş olunur.
Yukarıdaki şekilde mavi gösterilen düğümler gittiğimiz, kırmızı olanlar ise baktığımız düğümlerdir. Yani ilk adımda B ve E düğümlerine bakılır bu düğümlerden kısa olan B düğümüne gidilir.
B düğümünden yine komşu düğümler kontrol edilir.
Böylelikle C ve D düğümlerini de kontrol etmiş oluruz. Bu düğümlerden kısa mesafeli olan D düğümü seçilir.
Son olarak D düğümünün komşularına bakıldığında hedef olan F düğümü bulunur ve bu düğüm seçilerek algoritma bitirilir.
Sonuçta arama algoritmamız, A,B,D ve F düğümlerini dolaşarak hedefe varmış olur.
Yukarıdaki örnek, yönlü ve ağırlıklı graf üzerinden anlatılmıştır (weighted directed graph) aynı algoritma yönsüz ve ağırlıklı bir grafik üzerinde de çalışır.
Ayrıca yukarıdaki örnekte az sayıda düğüm olduğu için bütün düğümlere bir kez bakılmıştır. Ancak sabit maliyetli arama algoritmasında bu her zaman gerçekleşmek zorunda değildir. Yani arama algoritmamızın sonucu bulduğu ama grafta bakmadığı düğümler olduğu durumlar olabilir.
Sabit maliyetli arama algoritmasını aslında bir öncelik sırasına (priority queue) benzetmek mümkündür. Algoritma başlangıç düğümünden başlayarak graftaki bütün düğümleri, başlangıç düğümüne olan mesafelerine göre dolaşır.
Örneğin yukarıdaki graf için her düğümün başlangıca uzaklığı yazılacak olursa:
Uzunluklarına sahiptir ve bu durumda düğümler uzaklıklarına göre sıralandığında
Sırası çıkar ki bu sıralamada F düğümüne ulaşan yol yukarıdaki arama sonucunda bulunan A,B,D,F sırası olur.
Sadece bu algoritmayı daha iyi anlayabilmek için yukarıdaki graf üzerinde ufak bir değişiklik yapalım ve D-F aralığının maliyetini 7’ye çıkaralım. Ayrıca grafın yönsüz olduğunu kabul edelim.
Yukarıdaki yeni haliyle grafımız bir öncekine göre daha ilginç çalışacaktır. Algoritmamız gereği yine A düğümünden başlayacağız ve D düğümüne gelene kadar aynı şekilde arama işlemi devam edecektir. Çünkü D düğümüne ulaşana kadar ne algoritmada ne de grafta bir farklılık yoktur.
Yukarıdaki şekilde D düğümüne ulaşıldıktan sonra F düğümüne giden yolun maliyeti yüksek bulunacaktır. Bunun sebebi D düğümünden F düğümüne ulaşan yolun maliyetinin toplamda A-B + B-D + D-F maliyetlerinden oluşması ve bunun da 3 + 2 + 7 = 12 olmasıdır.
Algoritmamız bu değere ulaştıktan sonra A,B,D,E ve F yolunu deneyecek, bu maliyeti bir öncekine göre daha ucuz bulacaktır. 3+2+3+2 = 10
Ancak E düğümüne ulaşma maliyeti A-E dolaşması sırasında zaten 6 olarak bulunmuştu. Bu durumda algoritmamız yeni yol olarak A,E,F şeklinde sonucu bulacaktır ve maliyeti 6+2 = 8 olarak en kısa yola sahiptir.
Yukarıdaki bu yeni yaklaşımda geri izleme algoritması (back tracking algorithm) kullanılmıştır.
zehra Mayıs 1, 2011 at 6:01 pm
mrb şadi bey yukarıdaki verdiğiniz iki örnekte en kısa maliyetli yol seçimi yapılarak hedefe ulaşılmak istenmiş fakat anladığım kadarıyla ikinci örnekte farlı bir algoritma kulanılmış biz uniform cost search algoritmasını yazarken içinde bu algoritmayıdamı eklememiz gerekir yoksa bu ikinci algoritma tamamen bağımsızmı bu konuda bilgi verirseniz sevinirim iyi günler.
Şadi Evren ŞEKER Article Author Mayıs 1, 2011 at 7:34 pm
iki örnekte aynı şeyi anlatmaktadır. Kodlama açısından en kolay yol, bir sıra (queue) yazmaktır. Buna göre başlangıç düğümünden itibaren komşuların tamamı bir öncelik sırasına (priority queue) yerleştirilir. Sıradaki önceliği, düğüme giden mesafe belirler ve en yakın olan düğüm en yüksek önceliğe sahiptir. Ardından sıradan bir düğüm alınır.
Bu veri yapısını daha iyi anlayabilmek açısından yukarıdaki şekil üzerinden anlatmaya çalışayım.
Aşağıda teker teker sıradaki işlemleri veriyorum:
1. A 0 // sadece A düğümü var ve başlangıç olduğu için maliyet 0
2. B 3 > E 6 // A düğümünün komşuları var ve en düşük maliyetli olan en başta (en yüksek öncelikte)
3. D 5 > E 6 > C 8 // B düğümüne gittiğimiz için bu düğümün komşuları da eklendi
4. F 6 > E 6 > C 8 // F düğümünü bulduk
Yukarıdaki işlemlerden 4. adımda E ve F düğümlerinin maliyeti eşit. Bu durumda belki algoritmamız F düğümünü E düğümünden sonraya koyabilir, bu durumda arama işlemi bir adım daha ilerlemiş olur.
Kısacası, sorunuza cevap olması açısından, sabit maliyet aramasında (uniform cost search) bir öncelik sırası (priority queue) kodlamanızda ve yukarıda anlatıldığı üzere bu veri yapısını kullanmanızda fayda vardır.