Yazan : Şadi Evren ŞEKER

Bu yazının amacı, algoritma analizi konusunda geçen ve algoritmaları sınıflandırmak için kullanılan bir yaklaşımı, dallanma ve sınırlandırma (branch and bound) yaklaşımını açıklamaktır.

Algoritma, basitçe verilen bir fonksiyon için en iyi (optimum) çözümü bulmayı amaçlar. Bu amaca sahip çok sayıdaki yaklaşımdan farkı ise bu amaca ulaşmak için iki çok önemli aracı kullanıyor olmasıdır:

  • Parçalama (Splitting) veya Dallandırmda (Branching)

  • Sınırlandırmda (Bounding)

Bu iki yaklaşım sırasıyla probleme uygulanır. Parçalama aşamasında, problem alt parçalarına ayrılır (Burası parçala fethet (divide and conquere) yaklaşımına benzemektedir) ardından bu parçalar için alt ve üst sınırlar (upper and lower bounds) belirlenir.

Algoritma özellikle oyun programlamada sıkça kullanılmaktadır. Yapay zeka yaklaşımının kodlandığı ve karar ağacı oluşturulduğu durumlarda, ağacın dallarına bölünmesi ve her dal için limitlerin belirlenmesi şeklinde çalışır.

Ayrıca algoritmanın iyileştirilmesi için alfa-beta budaması (alpha beta prunning) benzeri yöntemler kullanılabilir.

Algoritmanın en önemli özelliklerinden birisi NP-Hard problem grubu için kullanışlı olmasıdır.

Algoritmanın kullanıldığı bazı problem tipleri aşağıda sıralanmıştır:

Örnek olarak 0-1 Torba problemini (0-1 Knapsack problem) çözmeye çalışalım. Öncelikle problemi hızlıca hatırlayalım. Amacımız elimizdeki torbayı mümkün olan en değerli şekilde doldurmaktır. 0-1 torba problemi ise klasik torba probleminin özel bir halidir ve bu özel halinde bir eşya, ya tamamen alınır ya da tamamen bırakılır, bir eşyanın bir kısmını almak mümkün değildir.

Örneğin aşağıdaki tabloda verilenleri ele alalım:

Eşya

Ağırlığı (w)

Değeri (v)

Değer/Ağırlık

1

4kg

40 TL

10

2

7kg

42 TL

6

3

5kg

25 TL

5

4

3kg

12 TL

4

Elimizde sadece 10kg alabilecek bir torbamız olduğunu düşünelim. Bu durumda en yüksek doldurma değerimiz, yani en pahalı şekilde bu torbayı nasıl doldurabiliriz?

Yukarıda verilen değerler çerçevesinde bir karar ağacı oluşturacağız. Önce problemin çözümünü verip ardından açıklamak istiyorum:

Şekildeki kök düğümünden başlayarak diğer düğümleri dolaşmak istiyor olalım. Dallanma ve sınırlandırma problemi bizim başlangıç düğümünden başlayarak problemi alt paralara bölmemizi söyler (branching). Buna göre kök düğümünden başlandıktan sonra olası 2 ayrı yolu 2 alt problem olarak görebiliriz ve elbette bu alt problemlerin de alt problemleri bulunmaktadır. Yani problemin çözümüne sol veya sağ düğümünden devam edilmesi alt problemlerdir. Burada problemi parçalara bölerek bir dallanma elde ediyoruz. Genelde problemin bu aşamasında özyineli (recursive) bir yaklaşım izlenir.

Hemen bu noktada önemli bir durumu belirtmek istiyorum. Dallanma ve sınırlandırma (Branch and bound) algoritmalarının çok benzediği bir yaklaşım da geri izleme (bactracking) algoritmalarıdır. Aynen geri izleme algoritmalarında olduğu gibi bir yoldan başlanır başarıya ulaşılamazsa farklı bir yola girilir ve arama işleminin en son başarılı olduğu yerden herşey devam eder. Ancak dallanma ve sınırlandırma algoritmaları, geri izleme algoritmalarında olduğu gibi bize belirli bir yolu dikte etmez. Yani sığ öncelikli arama (breadth first search) veya derin öncelikli arama (depth first search) gibi sistematik olarak nasıl gidileceğini belirten bir yanı yoktur. Bunlardan herhangi birisi kullanılabileceği gibi tamamen başka bir yöntem de seçilebilir.

Gelelim problemin sınırlandırılmasına (bounding). Sınırlandırma sırasında bulunan değer elimizdeki en iyi değerle karşılaştırılır. Şayet daha kötü bir sonuçsa çözüm olma ihtimali yoktur (non-promising) şayet elimizdeki sınırdan iyi bir durumdaysa o zaman çözüm ihtimali olabilir (promising) ve bu şekilde tutulur.

Yukarıda sınırlar için kullanılan ub (upper bound, üst sınır) değerinin hesaplanması aşağıdaki şekildedir:

Buradaki hesaplama işlemi sırasında W, toplam torbanın kapasitesini, w o ana kadar torbadaki eşyaların ağırılğını, vi+1, o anda alınmasına karar verilmeye çalışılan eşyanın değerini ve wi+1 ise o anda alınmasına karar verilmeye çalışılan eşyanın ağırlığını ifade etmektedir.

Diğer bir deyişle elimizdeki torbada, o ana kadar aldığımız eşyaların değerine, yeni eklenen eşyanın kg başına değerini ekliyoruz. Bu yeni eklenen değeri de torbada kalan boş yer ile çarpıyoruz. Bu sayede şayet torbadaki boşyerden daha fazla yer kaplıyorsa eksi değer olarak sisteme etki ediyor. Şayet torbaya sığıyorsa, alınabilecek en değerli eşyanın en fazla yeri kaplamasını istiyoruz.

Örneğin başlangıç durumunu hesaplayalım:

ub = + ( 10 – 0 ) (10TL)= 100 TL

Yani başlangıçta torbamızda elimizde 0 TL değerinde eşya, 0 kg ağırlığında eşya ve en fazla kilogramı 10TL gelebilecek eşya bulunuyor (tablodan görülebilir). Dolayısıyla üst limitimiz 100TL. İddiamız şu an itibariyle 100TL’den daha değerli bir torba doldurma alternatifi olmadığı (üst limit, upper bound) ki bu durum tamamen doğrudur.

Diyelim ki ilk ürünü aldık ve ikinci ürüne karar vermek istiyoruz. Bu durumda formülümüz aşağıdaki şekilde olacak:

40 TL + (10-4) * 6 = 76

Yukarıdaki hesapta, 40 TL ilk ürünün alınmış değeridir. Bu değerin üzerine, ikinci ürün için torbamızda kalan yer ile ikinci ürünün değerinin çarpımı eklenerek 76 sonucu bulunmuştur. Demek ki iki ürünü alırsak torbanın değeri 76 olacak. Peki şimdi de ilk ürünün alınmaması durumunu görelim:

0 + (10 – 0 ) * 6 = 60

Burada ilk ürün alınmayacaksa, zaten elimizdeki torbadaki ürünlerin değeri 0 olacağına göre 10 kg boş yerimizi elimizdeki alınabilecek en yüksek değer ile çarpıyoruz ( bir önceki adımdan farklı olarak ilk ürünü artık alamayacağımız için en yüksek değer 6 olmuştur).

Yukarıdaki hesaplamalar, üst limitleri belirtiyor. Bu üst limitlerin yanında ağacımızda o ana kadar alının ürünlerin toplam değeri ve ağırlığıda tutulmaktadır. Bazı durumlarda toplam ağırlık kapasitemizi aştığı için ve problem 0-1 torba problemi olduğu için mümkün olmayan durumlarla karşılaşılmıştır.

Netice olarak 1 ve 3 numaralı eşyaları alıp 2 ve 4 numaralı eşyaları almazsak en yüksek torba değerine ulaşılmış olunur.

Ağacın oluşturulması sırasında, önce sol tarafı oluşturmaya çalıştım. Bu sırada 8 numaralı düğüme (node) kadar ulaşmış oldum. Bu değere ulaştıktan sonra kökten ayrılan sağ tarafın hesaplanması, daha fazla hesaba gerek kalmadan budama (prunning) yapılmasını sağlıyor çünkü elimizdeki limitten daha kötü bir üst limit elde ediyoruz. Yani 8 numaralı düğümde torba değerimizi 65 olarak hesapladık. 2 numaralı düğümde ise üst limiti (alınabilecek en yüksek değeri) 60 olarak bulduk. Demek ki bu düğümün altında, 60’dan daha büyük bir değer olamaz. O halde bu düğümün altındaki hiçbir düğümün hesaplanmasının anlamı yoktur çünkü bütün ihtimaller daha kötü olacaktır.

İşte yukarıdaki son paragraf dallanma ve sınırlandırma (Branch and bounding) yaklaşımının özünü oluşturur.


Yorumlar

Bir cevap yazın

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