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

Hata
  • XML Parsing Error at 1:82. Error 9: Invalid character
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 )  
404 Not Found

404

Not Found

The resource requested could not be found on this server!


Proudly powered by LiteSpeed Web Server

Please be advised that LiteSpeed Technologies Inc. is not a web hosting company and, as such, has no control over content found on this site.