Yedinci filmi ile Türkiye'de izlenme rekorlarını alt üst eden Hızlı ve Öfkeli efsanesinden güzel haber: 
Hızlı ve Öfkeli 8, 14 Nisan 2017'de geliyor!

Türkiye En Az Alkol Tüketen İkinci Ülke

OECD'nin alkolün zararları ve kamu sağlığına etkileriyle ilgili raporuna göre, Türkiye Endonezya'dan sonra 40 ülke içinde en az alkol tüketen ikinci ülke oldu.

Sezgisel Algoritmalar

Sezgisel Algoritmalar

Bilgisayar bilimlerinde, sezgisel ya da buluşsal (heuristic) bir problem çözme tekniniğidir. Sonucun doğruluğunun kanıtlanabilir olup olmadığını önemsememektedir fakat genelde iyiye yakın çözüm yolları elde eder. Sezgisel algoritmalar ise geçiş süresinde daha verimli hale gelebilmek için en iyi çözümü aramaktan vaz geçerek çözüm zamanını azaltan algoritmalardır.
Sezgisel algoritmalar en iyi sonucu bulacaklarını garanti etmezler fakat makul bir süre içerisinde bir çözüm elde edeceklerini garanti ederler. Genellikle en iyiye yakın olan çözüm yolununa hızlı ve kolay bir şekilde ulaşırlar.
Sezgisel arama algoritmalarına örnek olarak

• A* araması (A star)
• Demet araması (Beam search)
• Tırmanış Araması (Hill climbing)
• En iyi öncelikli arama (Best first search)
• Açgözlü en iyi öncelikli arama (Greedy best first search)

Heuristic diğer bir anlamıyla; bir düğümden (node) başka bir düğüme olan en kısa yolun maliyetini hesaplayan fonksiyonlar olarak bilinir.

Bilgisayar bilimlerinde en kısa yol bulmak için kullanılan algoritmalardan birisidir. Örneğin seyyar tüccar problemi (travelling salesman problem, TSP) gibi bir problemin çözümünde kullanılabilir. Benzer şekilde oyun programlamada, oyunda bulunan oyuncuların en kısa yolu bularak hedefe gitmeleri için de sıklıkla kullanılan algoritmadır.

Kısaca bir düğümden (node) hedef bir düğüme (target node) en kısa hangi düğümler üzerinden gidileceğini bulmaya yarayan “en iyi yerleştirme (best fit)” algoritmasıdır. Ve işte bazı sezgisel algoritmalara örnekler;

A* algoritması

yapı olarak muteber sezgisel (admissable heuristic) bir algoritma olarak sınıflandırılabilir. Bunun sebebi algoritmasının mesafe hesaplamada kullandığı fonksiyondur:

f(n) = g(n) + h(n)

denklemindeki

f(n) = hesaplama yapan sezgisel (heuristic) fonksiyon.

g(n) = Başlangıç düğümünden mevcut düğüme kadar gelmenin maliyeti

h(n) = Mevcut düğümden hedef düğüme varmak için tahmin edilen mesafe.

Dikkat edileceği üzere f(n) fonksiyonunun sezgisel olma sebebi, bu fonksiyon içerisinde bulunan ve tahmine dayalı olan h(n) sezgisel fonksiyonudur.

Algoritmanın çalışması:

Algoritma yukarıdaki toplama işlemini kullanan oldukça basit bir yapıya sahiptir. Veri yapısı olarak bir öncelik sırası (priority queue) kullanan algoritmada en öncelikli olan düğüm f(n) değeri en düşük olan düğümdür.

1.      Algoritma her adımda en düşük değeri (Ve dolayısıyla en önemli) düğümü alır (yani bu düğüme gider) ve düğümü sıradan (queue) çıkarır.

2.      Gidilen bu düğüme göre komşu olan bütün düğümlerin değerleri güncellenir (artık bu düğüme gelmenin bir maliyeti vardır ve dikkat edilirse f(n) fonksiyonu içerisinde bu değer yer almaktadır.)

3.      Algoritma yukarıdaki adımları hedefe varana kadar (yani hedef düğümü öncelik sırasında (priority queue) en öne gelene kadar) veya sırada (queue) düğüm kalmayana kadar tekrarlar.

4.     Örnek Çalışma:

5.     Algoritmanın çalışması için aşağıdaki örneği ele alalım:

6.     

7.     Yukarıdaki grafikte sol üst köşedeki düğümden, sağ alt köşedeki düğüme gitmek isteyelim. Bu durumda f(n) fonksiyonunu oluşturan mesafe değeri, grafik üzerindeki yol maliyetleri olarak hesaplanbilir. Sezgisel fonksiyon olarak, bir düğümün hedefe olan kuş uçuşu mesafesini alalım. Yani iki düğüm arasındaki mesafeyi çizilen yoldan değil de iki düğüm arasındaki cetvel ile ölçülen değer olarak kabul edelim.

8.     Bu durumda düğümlerin sezgisel mesafelerini (heuristic) gösteren graf aşağıdaki şekildedir:

9.     

10. Yukarıdaki bu grafikte kırmızı renkle gösterilen değerler, o düğümden hedef düğüm olan sağ alt köşedeki düğüme olan kuş uçuşu mesafeyi göstermektedir. Bu değerleri kısaca h(n) olarak kabul edebiliriz.

11. Başlangıç düğümümüz olan sol üst köşedeki düğümden başlayarak iki düğümün değerini hesaplayalım. Başlangıcın altında bulunan düğüm için h(n) = 9 ve g(n) = 4 olmaktadır.

12. Başlangıcın sağında bulunan düğüm için ise h(n) = 8 ve g(n) = 3 olmaktadır. Buna göre:

13. f(aşağı) = 9+4 = 13

14. f(sağa) = 8 +3 = 11

15. olarak bulunmaktadır. Algoritmamız bu seçimler arasından küçük olan (ve önceliği yüksek olan) sağa gitmeyi tercih eder.

16. Bu seçimi aşağıdaki şekilde gösterelim.

17. 

18. Yukarıdaki bu seçimden sonra değerler tekrar hesaplanır. Yukarıda yapılan seçime göre düğümlerin değerleri tekrar f(n) = g(n) + h(n) olarak hesaplanırsa:

19. 

20. Yukarıdaki bu grafikte görüldüğü üzere sıramızda (queue) iki düğüm bulunmakta ve iki düğümün değerleri sırasıyla 13 ve 11 olmaktadır.

21. Bu durumda 11 olan düğümü seçip aşağı doğru hareket ediyoruz.

22. 

23. Yukarıdaki son durumda 13 ve 21 değerleri olan iki düğüm arasında seçim yapıldığında, kısa değer olarak 13 bulunduğu için A* arama algoritmamız bu aşamada geldiği alternatif yoldan vaz geçerek en kısa yolun bu yeni düğüm olabileceğini düşünür ve bu yola gider.

24. 

25. Yukarıdaki şekilde bu yeni seçim yeşil renk ile gösteirlmiştir. Yeni seçim yapıldıktan sonra ulaşılan komşu düğümler 14 ve 21 değerlerine sahiptir. Bu durumda 14 değerine sahip olan daha öncelikli düğüme hareket edilecektir.

26. Yeni halinde değerler hesaplandığında sonuç düğümüne gidilmesi mümkündür ve ulaşım değeri yukarıdaki dolaşmaya göre daha düşüktür.

27. 

28. Yukarıdaki son durumda hedefe ulaşılmış ve aşağıdaki yol kullanılmıştır. Sonuçta ulaşım için harcanan mesafe toplandığında 4+6+4 =14 mesafesi diğer alternatif olan 3+4+6+8 =21 değerine göre daha kısadır.

29. Tabi A* algoritması sezgisel bir algoritma olduğu için bu durumu bilmemektedir.

Demet araması(ışın) algoritması

En iyi ilk arama yaklaşımını kullanan arama algoritmaları, arama yaptıkları şekil (graph) üzerinde bütün çözüm ihtimallerini belirli bir sezgisel fonksiyona göre sıralarlar. Diğer bir deyişle arama işlemi sırasında sezgisel bir fonksiyona göre, aramada bazı kararlara öncelik verirler. Bu sezgisel fonksiyonun amacı, karar anında verilen kararın, sonuç durumuna (goal state) ne kadar yakın olduğunu yargılayabilmektir.
Işın aramasının bir özelliği de, daha önceden belirlenmiş ve sınırlı sayıdaki, yapmış olduğu seçimleri saklamasıdır.
Işın araması, bir arama ağacı (search tree) oluştururken, sığ öncelikli arama (breadth first search) yaklaşımı kullanır. buna göre ağacın herhangi bir seviyesinde, gidilebilecek düğümlerin sezgisel değerlerini hesaplar ve bunlardan sadece belirli sayıdaki düğümü, daha sonra geri dönülmek üzere hafızasında tutar. Bu değere ışın aramasına özgü olarak ışın genişliği (beam width) ismi verilir.
Işın genişliği arttıkça daha fazla düğüme bakılmaktadır. Işın genişliği azaldıkça da daha fazla düğüm budanmaktadır (prunning). Budama işleminin dez avantajı, şanssız bir şekilde en iyi sonucu verecek düğüme giden yolu budama riskidir. Ancak bu riskten dolayı bütün düğümleri tutmak (yani hiçbir düğümü budamamak) gibi bir karar verirsek, bu karar sonucunda da çok daha fazla hafıza ve işlem ihtiyacımız olacaktır. İşte ışın araması, bu iki karar arasında en iyi (optimum) noktayı bulmayı amaçlar.
Bu amaca yönelik olarak, ışın araması sabit ışın genişliği (fixed beam width) veya değişken ışın genişliği (variable beam width) kullanacak şekilde kodlanabilir. Değişken ışın genişliği alan arama algoritmasında, öncelikle ışın genişliği asgari değerde tutularak arama yapılır. Aranan en iyi sonuca ulaşılamazsa, ışın genişliği arttırılarak arama işlemi sürdürülür. Beklenen sonuca ulaşılana kadar da ışın genişliği arttırılır.

Işın aramasının kullanıldığı yerlerden birisi de bilgisayarlar tarafından otomatik olarak yapılan tercüme işlemleridir. Bilindiği üzere bir kelime, bilgisayar tarafından işlendiğinde, birden fazla anlama gelebilmektedir. İnsanlar kelimenin kullanımından (syntax, pragma) kelimenin anlamını kısa sürede doğru olarak anlayabilmekte ancak bilgisayarlar için bu anlama süreci ve doğru anlamın bulunması (semantics), hatırı sayılır bir süre almaktadır.
Çözüm olarak ışın araması algoritması, çok sayıdaki çeviri ihtimallerinden sadece belirli bir kısmını işleyerek doğru tercümeyi yapmak için kullanılabilir.

Tırmanış (Tepe Tırmanma) Algoritması

Bilgisayar bilimlerinde kullanılan arama algoritmalarından birisidir. Arama işleminin yapıldığı grafikteki tepelerden ismini alır. Basitçe bir grafikte bulunan en düşük noktanın aranması sırasında grafikte yapılan hareketin aslında tepe tırmanmaya benzemesinden ismini almaktadır.

Örneğin yukarıdaki şekilde gösterilen ok temsili bir tepe tırmanma işlemidir. Burada arama yapan algoritma aslında bir çukur bulmuş ancak daha iyisi için tepe tırmanmaktadır denilebilir.

Elbette olayı iki boyutlu bir grafik üzerinde yapılan bir arama veya tırmanılan bir tepe olarak görmek, algoritmanın önemini kavramayı engelleyebilir. Aslında burada anlatılmak istenen bilgisayar bilimleri de dahil olmak üzere, çeşitli bilim ve mühendislik alanlarında, birden fazla çözümü olan problemler için en iyi çözümün arandığı iyileştirme (optimization) problemleridir.

Yani şayet bir sistemin ya da bir programın daha iyi hale getirilmesi isteniyorsa, sistemin verdiği sonuçlara göre arama işlemi yapılarak iyileştirme amaçlanabilir. İşte bu noktada tepe tırmanma algoritması (hill climbing algorithm) de dahil olmak üzere çeşitli arama algoritmaları devreye girer. Örneğin literatürde sıkça kullanılan seyyar tüccar problemi (travelling salesman problem) bu problemlerden birisidir. Tepe tırmanma algoritması verilen bir harita için verilen bir sonucu iyileştirmeye çalışır. Elbette amaç bütün ihtimalleri denemeden iyi bir sonuç bulabilmektir.

Tepe tırmanma algoritması, arama algoritmaları arasındaki en iyi sonucu verene algoritma değildir. Ancak kodlanması ve tasarımının basit oluşundan dolayı sıklıkla kullanılır.

Tepe tırmanma algoritması çeşitleri

Algoritmanın üzerinde çeşitli iyileştirmeler yapılarak daha iyi sonuçlar elde edilmeye çalışılmıştır. Literatürde sıkça kullanılan bir iki tepe tırmanma algoritmasını farkları ile birlikte açıklamaya çalışalım.

Klasik tepe tırmanma algoritmasında amaç arama için merkez kabul edilen (veya başlangıç noktamız diyebileceğimiz) noktadan komşu olan noktaları gezerek daha iyi sonuçlar elde etmektir. Temel olarak bir grafikte rastgele seçilen bir nokta için 3 farklı ihtimal bulunmaktadır:

1.     Noktanın bir tarafında problem iyileşirken diğer tarafında kötüleşmektedir. Bu durumda iyi tarafa doğru tırmanma algoritmamız devam eder.

2.     Noktanın iki tarafında da problem sonucu kötüleşmektedir. Bu durumda bulunduğumuz nokta problem için en iyi noktalardan (optimum points) birisidir. Elbette bu en iyi sonuç olmayabilir yani bu sonuçtan daha iyi sonuçlar olabilir ancak klasik tepe tırmanma algoritması bu diğer sonuçları bulamaz ve bu noktada kalır.

3.     Noktanın iki tarafında da problem iyileşiyordur. Yani tesadüfen bulduğumuz nokta aslında problem için ulaşılabilecek en kötü noktalardan birisidir. Bu durumda tepe tırmanma algoritması yönlerden birisini seçerek tırmanmaya devam eder. Farklı bir çeşit olarak iki yöne de tırmanan algoritma bulunmaktadır.

Klasik tepe tırmanma algoritmasından farklı olarak steepest ascent hill climbing algoritmasında, bulunabilen bütün sonuçlar arasından bir seçim yapılır. Bu algoritmada da klasik tepe tırmanma algoritmasında da sorun aynıdır. Şayet arama işlemi sırasında bir yerel çukura (local minimum) rastlanılırsa bu durumdan algoritma kendisini kurtaramayarak en doğru sonucu bulamayabilir.

Buna karşılık olasılıksal tepe tırmanma algoritmasında ( stochastic hill climbing algorithm) bütün komşuların aranması ve komşuların verdiği sonuca göre hareket etmek yerine, rast gele olarak bir komşunun seçilmesi söz konusudur. Şayet gidilen bu komşu beklenen yönde bir iyileştirme sağlıyorsa, bu yönde aramaya (tırmanmaya) devam edilir, şayet beklenen iyileştirme sağlanamıyorsa, bu durumda daha farklı bir komşu denenir.

Yukarıdaki tepe tırmanma algoritmalarının yanında rastgele başlangıç tepe tırmanma algoritması (random restart hill climbing algorithm) şaşırtıcı derecede iyi sonuç veren bir algoritmadır. Bu algoritma basitçe bir x durumunu başlangıç kabul eder ve daha iyi bir durum bulunca başlangıç durumunu bu daha iyi duruma kaydırır. Algoritma iyi durum buldukça başlangıç durumunu kaydıran ancak bulamadığı durumlarda da aramaya devam eden bir yapıya sahiptir. Rastgele başlangıç tepe tırmanma algoritmasına bazı kaynaklarda pompalı tüfek tepe tırmanma algoritması (shotgun hill climbing algorithm) ismi de verilmektedir.

Tepe tırmanma algoritmaları genel olarak yerel bir başarı noktasında (local optimum point) takılmak gibi bir zafiyete sahiptirler. Daha iyi sonuçlar için simulated annealing gibi arama algoritmaları kullanılabilir.

Örneğin yukarıdaki şekilde x ve y noktaları arasında bir düzlük bulunmaktadır. Başlangıç noktası olarak bu aralıktaki herhangi bir noktadan başlanırsa algoritma komşuları aradığında daha iyi veya daha kötü bir sonuç bulamayacağı için hatalı karar verebilir.

Ayrıca tepe tırmanma algoritmaları problem sonuçlarında nadiren de olsa aynı sonucun elde edilmesi durumunda belirsizce hatalı sonuçlar verebilir. Bu şekildeki durumlara algoritmadaki düzlükler ismi verilir ve algoritma hangi yöne gidilirse gidilsin daha iyi bir sonuç çıkaramaz (hep aynı sonucu çıkarır). Elbette doğası gereği tepe tırmanmaya hazırlanmış algoritmamız, tepe bulamayınca hata yapmaktadır.

Algoritmanın kodlanması

Algoritma iki boyutlu bir grafik için rastgele yön seçimi yapılması durumunda aşağıdaki şekilde kodlanabilir:

Yukarıdaki kodda, basitçe başlangıç noktasından başlanarak, daha iyi sonuçlar bulunduğu sürece bir sonraki komşu noktaya hareket öngörülmüştür.

Ancak problemin çok boyutlu olması yani bir noktanın birden fazla komşusu bulunması durumunda bütün komşuların kontrol edilmesi ve en iyisinin bulunması daha sonra bu komşuya doğru hareket edilmesi gerekeceği için algoritmayı aşağıdaki şekilde yazmak mümkündür:

Yukarıdaki yeni kodda, bir noktanın birden çok komşusu olduğu kabul edilmiş ve bütün komşuları dolaşılarak en iyi komşu alınmış, ardından daha iyi komşu bulundukça bu işlem devam ettirilmiştir. Nihayetinde hiçbir komşu, bulunan son komşudan daha iyi olmayınca program sonlandırılmıştır

Zeki Alasya Mason muydu?

Zeki Alasya Mason muydu?

Yaşamını yitiren Zeki Alasya'nın Mason olduğu yönündeki açıklamaları da uzun süre gündemde kalmıştır.

Türk sinema ve tiyatrosunun en ünlü oyuncu ve yönetmenlerinden Zeki Alasya, neden Mason olduğunu açıklamıştı. Star gazetesinden Murat Menteş'e konuşan Alasya, partneri Metin Akpınar'ı Mason yapamamaktan şikayet etmişti.

İşte o röportajın ilgili bölümü...

Masonlukla bir ilginiz var mı?
Ben Masonum.

Masonların dünyayı yönettiği söyleniyor. Siz de yönetiyor musunuz?
Hayır, dünyayı yönetmiyorum. Masonluk bir ahlak ve kardeşlik sistemidir. Bir din değildir kesinlikle. İnsanların kardeş olması gerektiğini öne çıkaran bir yapıdır. Çok kötü tanınıyor. Ben Mason olmaya kalktığım günlerde ailem dehşete kapıldı.

Ne zaman Masonluğa geçtiniz?
15 sene oldu. Metin Akpınar 'Zeki bana Mason olmayı önerdi, kabul etmedim' diye bir açıklama yapmıştı. Öyle mi sahiden?
E tabii, ben Mason olunca, Metin'in de Mason olmasını istedim. Fakat yanaşmadı.

Kimler Mason oluyor?
Mesleğinde ileri gitmiş kişiler kabul ediliyor. Zenginlerin toplandığı bir yer değildir. Ben Mason olduğumda kiralarımı ödemekte zorluk çekiyordum.

Kaç Mason var?
Dünyada 6 milyon, Türkiye'de de 15 bin. Masonluk ulusal bir kuruluştur. Sanıldığı gibi kökü dışarıda, Siyonist filan değildir. Ateistseniz Mason olamazsınız.

Hangi dinden olmak gerekiyor?
Belli bir dinden ziyade, Yaratıcıya inanmak gerekir. Yaratıcı'ya 'Evrenin Ulu Mimarı' diyoruz. Bence çok güzel bir tabir. Masonluğu vahşi ve aşağılık bir şey olarak anlatan kitaplar okumuştum. Halbuki ahilik, Bektaşilik, Mevlevilik gibi bir oluşum.

Masonluk size çok şey kattı mı?
Çok. Sabırlıydım, sabrım arttı. Paylaşmayı severdim, paylaşımcılığım arttı. Üç-beş kişi bir araya gelip saçma sapan şeyler konuşuyorduk. Futbol, para, kadınlar, dedikodu... Bir arayışa girmiştim. Masonlukta karar kıldım. Çok memnunum.

Çok ilginç... Masonlar genellikle Masonluklarını gizler.
Evet. Başlarına bir şey gelecek diye korkuyorlar. Mesela Devlet Tiyatrosu'nda çok Mason var, söylese işinden olacak.

Eklemek istediğiniz bir şey var mı üstadım?
Bu üstat lafını çok severim, biz Masonlar çok kullanırız... Hayatta her şey olur, para gelir, şöhret gelir, bilgi gelir... Hepsinden önemlisi iyi insan olmaktır.

Zeki Alasya: Pişmanım, din düşmanı değilim
CNN Türk'te Cüneyt Özdemir'in hazırlayıp sunduğu "5N 1K" programına konuk olan Zeki Alasya 30. uluslararası İstanbul Film Festivalinde büyük tepki çeken konuşmalarına açıklık getirdi. Alasya namaz kılmanın gerekli ve kutsal bir ibadet olduğuna inanan biri olduğuna kimsenin görmesi için yapılan bir ibadet olmadığını ifade etti.

Talebeler Sahnede Toplu Namaz Kıldı
1967 yılında Milli Talebeler Birliğini dinci örgencilerin ele geçirdiğini oyun oynanan sahnede toplu şekilde namaz kılındığını sahneyi mescide dönüştürüldüğünü amaçları ise birilerine bir şeyler gönderme olduğundan dolayı tepki gösterdiğini belirtti.

Pişmanım - Ben de İnadet Ederim
Namaz kılmanın kutsallığına inan biri olduğunu ve söylediği sözlerden dolayı pişman olduğunu ifade eden Alasya, din düşmanı olmadığını, temiz bir müslüman olduğunu ve kendisinin de ibadet eden biri olduğunu söyledi.

Branch and Bound (Dallanma ve Sınırlandırma Yaklaşımı)

Branch and Bound Algoritması (Dallanma ve Sınırlandırma Yaklaşımı)

 Nedir Peki?

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:

• Azami Tatmin Problemi (Maximum Satisfaction Problem)
• Torba Problemi (Knapsack Problem)
• Seyyar Satıcı Problemi (Travelling Salesman Problem)

Ö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.

ve Videomuz