Yazan : Şadi Evren ŞEKER
Bilgisayar bilimlerinde klasik olarak kaynaklarda geçen ve problem çözümünü belirli bir alanda bulmayı hedefleyen problemlerden birisidir.
Problemi tanımlayacak olursak:
5 litrelik tamamen dolu ve 2 litrelik boş bir bidon ile başlanarak, 2 litrelik bidonda 1 litre elde edilmesi için gereken adımları bulunuz.
Problemin çözüm adımlarını aşağıdaki şekilde bir karar ağacına ve dolayısıyla ihtimaller silsilesine bağlamak mümkündür:
Problemi tanımlarken 5 lt ve 2 lt iki bidonu aşağıdaki şekilde gösterlim:
İlk durumda, 5lt dolu olduğuna göre aşağıdaki şekilde gösterebiliriz:
Şimdi bu durumdan başlanarak izlenebilecek yolları bir ağaç yapısında gösterelim:
Görüldüğü üzere problemde birkaç farklı ihtimalin izlenmesi söz konusudur. Yukarıdaki yapı için bir ağaç yapısı kullanılabileceği gibi bir graf yapısı da kullanılabilir. Yukarıdaki her adımdan gidilebilecek diğer adımlar ok ile gösterilmiştir. Sol alt köşede bulunan durum ise son durumdur ve bu duruma ulaşılınca hedefe ulaşıldığı için daha fazla ihtimal hesabı yapılmaz.
Yukarıdaki bu problemi farklı şekil arama algoritmaları ile (graph search algorithms) farklı şekillerde dolaşmak ve hedefe ulaşmak mümkündür. Yukarıdaki şekildeki her ihtimali aşağıdaki şekilde bir harf ile gösterecek olursak:
Derin öncelikli arama (depth first search) : A B C E F G
Sığ önceliki arama (Breadth first search) : A H B C A D E H F D G
Derin Sarmallı arama (iterative deepining search) : A B H A B C D A A B C E H A B C E F D A B C E F G
Görüldüğü üzere bu tip problemlerde derin öncelikli arama algoritmalarının daha hızlı sonuca ulaştığı söylenebilir. Genelde çözüm hedefi derinde olacağı ve başlangıca en uzak noktada bulunacağı için derin öncelikli arama , sığ öncelikli aramaya göre daha iyi sonuç verir.