Programlama | Programlama Dilleri | C Programlama Dili |C++

Anasayfa Programlama C# 3 Kap Problemi


3 Kap Problemi

3 KAP PROBLEMİ

            Problemde boyutları belirli 3 tane kap verilir. Başlangıçta kaplarda bir miktar su vardır. Başlangıç durumundan belirli bir duruma gidilmek istenir. Örneğin 8 lt, 5 lt ve 3 lt boyutlarında 3 kap verilir. Başlangıçta 8 litrelik kap dolu, diğerleri boştur. Sonuç olarak 8 lt ve 5lt’lik kaplarda 4’er lt su kalması istenir. Problemin zorluğu elimizdeki kaplardan başka bir ölçü aleti kullanamamamızdadır. Kapların kapasitelerini ölçü aleti olarak kullanabiliriz. Problemi çözerken bütün olasılıklar denenebilir. Fakat bu yöntem aşırı işlem gerektirecektir.

            Problemin çözümünde barisentrik koordinatlardan yararlanıldığında problem çok kolay bir şekilde çözülebilmektedir. Verdiğimiz örnek için problemin barisentrik koordinatlardaki karşılığı aşağıdaki gibidir.

3 kap problemi çözüm görünümü

 

            Koordinatları (u,v,t) olarak alırsak; u, v ve t her bir kaptaki su miktarına karşılık gelir. Kırmızı nokta başlangıç durumunu temsil eder. Başlangıçta 8 litrelik kap doludur ve diğerleri boştur. Bu durumdan 4,4,0 durumuna gidilmek istenmektedir. Hedef durumunu yeşil nokta temsil eder. Kırmızı çizgilerle çizilmiş alan kapların kapasitelerine göre mümkün gidilebilecek durumları ifade eder.

            Problemin çözümü bilardo oynamaya benzer. Bir durumdan yola çıktığınızda bir duvara çarpıncaya kadar ilerlersiniz.Duvara çarpınca bu durum bir sonraki durumunuz olur.Örneğin 8,0,0 durumundan sol alt çapraz yönünde ilerlerseniz duracağınız bir sonraki nokta 3,5,0 ’dır.Bunun anlamı 8 litrelik kaptan 5 litrelik kaba, kap doluncaya kadar su dökmektir..3,5,0 noktasına geldiğinizde ise buradan 3 farklı yöne gidebilirsiniz.Bu şekilde bir noktadan çıktıktan sonra duvarlar üzerinde ilerleyerek çözüme ulaşmaya çalışılır.

            Bazı durumların çözümü yoktur. Örneğin 8,0,0 noktasından çıkıp 4,3,1 noktasına gelmek imkansızdır.

Çözüm Algoritması

            Problemi çözerken her bir durumu graf yapısıyla ifade edilmiştir. Her bir durumun mümkün 6 tane komşu durumu olabilir. Bu komşuluklarda yön önemlidir.6 farklı yönde ilerleme yapılabilir. Başlangıç olarak büyük üçgen içerisindeki noktalar ve komşulukları oluşturulur. Daha sonra kapların kapasitelerine göre mümkün gidilebilecek durumlar çıkartılır(kırmızı çizgilerin içerisindeki alan)

            Başlangıç durumundan başlayarak ilerlemeye başlanır. Bir duvara çarpınca bu şu anki durumumuzu ifade eder. Bir durumdan başka bir duruma gidilirken çıkığımız düğüm çözüm uzayından silinir. Böylelikle bir daha bu noktaya bakmamıza gerek kalmaz. Sonraki adımda rekürsif olarak şu an bulunduğumuz durumun komşularından birine doğru yola çıkılır ve çıkılan düğüm çözüm uzayından çıkarılır. Bir duvara çarpıldığında ise bu bir sonraki durum olur.Burada duvardan kasıt çözüm uzayını sınırlayan çizgilerdir.Buradaki duvarlar kızmızı çizgilerin kapladığı alanın sınır çizgileridir. Aynı işlemler çözüm uzayında hiçbir nokta kalmayana kadar veya çözüm durumuna ulaşılana kadar devam eder. Eğer çözüm uzayında hiç düğüm kalmamışsa ve de çözüm durumuna halen gelinememişse çözüm yoktur.

            Bir durumdan yola çıkarken gidilebilecek birden fazla yön olabilir. Bu yönlerin seçilmesinde bir sezgisellik izlenebilir. Algoritmada yönleri seçerken o yöndeki komşusunun sınır noktası olup olmadığına bakılır. Sınır noktaları kırmızı çokgenin en dıştaki noktalarıdır. Yön seçerken bir puanlama yapılır. Eğer gidilecek yöndeki komşu düğüm sınır noktası değilse o yönün puanına belirli bir değer eklenir. Yön tercihi yapılırken öncelik yüksek puanlı yönlerdedir. Bu yöntem bazı durumlar için iyi sonuç vermesine rağmen bazı durumlarda kötü çözümleri de bulabilir.

            Tüm çözümler bulunurken, gidilen bütün durumlardan gidilebilecek mümkün yönlerin hepsi denenir.

 

Programın Tamamını Aşağıdaki Linkten İndirebilirsiniz

Linki Görebilmeniz İçin Üye Olmanız Gerekmektedir...

Üye Kayıt

Yorumlar (0)
Sadece kayıtlı kullanıcılar yorum yazabilir!
Son Güncelleme ( Perşembe, 07 Nisan 2011 21:08 )