9.2.10

Genişlik Önceli Arama ile Su Kovaları Problemi

Öncelikle size problemden bahsetmek istiyorum. Elimizde 3 adet su kovası var bunların kaç litre kapasitesi oldukları kullanıcı tarafından belirlenecektir. Aynı zamanda kullanıcı bu kovalarla elde edilmek istenen su miktarını da belirleyecektir. Bizim bulmamız gereken sınırsız suyu kullanarak kapları birbiri içine boşaltarak istenen suyu elde etmektir. İstenen miktar en yüksek kapasiteli kovadan büyük olamaz. Programın çıktısı işlem sayısı olarak en az olmalıdır.Örneğin:

Kovalarım 3 lt , 5 lt ve 9 lt kapasiteli olsun. Hedefimiz 7 lt olsun. Programın üreteceği çıktı (suları çeşmeden doldurduğumuzu varsayalım):

çeşme->>    9
 9       ->>   5
çeşme ->>   3
3         ->>   9

Bu işlemlerden sonra 9 lt lik kapta 7 litrelik suyu elde etmiş oluruz. Bu problemin birden fazla çözümü de olabilir. Ama en kısa çözümler 4 basamak halinde olanlar olacaktır.

Problemin çözümü için genişlik öncelikli arama algoritmasını kullanmak en uygun olacaktır. Genişlik öncelikli arama tüm ihtimalleri sırasıyla dener. Aynı örneği göz önünde bulundurursak algoritmanın çalışması şöyledir:

İlk basamaktaki tüm ihtimaller: (Ç : çeşme , Y: yere dökmek)

Ç -> 3
Ç -> 5
Ç -> 9
3  -> 9
3  -> 5
3  -> Y
5  -> 3
5 -> 9
5 -> Y
9 -> 3
9 ->5
9 ->Y

Algoritmanın ikinci basamağı agacın dalları gibi dallanır. Kaplar için bir class tanımlarsak iki integer üyesi kapasitesi ve de içindeki su miktarı olacaktır. Eğer biz yukarı da ki gibi dallanma işimlerini kodla çözdürürken Kapların herhangi birisinin içinde hedefi yakalarsak programın arama kısmından cıkar ve de ekrana yapılan işlemleri yazdırırız.

Kodları indirmek için: tıklayın

2 yorum:

  1. link ölmüş ,yenileyebilir misin

    YanıtlaSil
  2. yeniledim, uyarı için teşekkürler

    YanıtlaSil