Bir çobanın bir kurdu, bir koyunu, bir balya da otu var.
Bunları nehrin karşı yakasına taşımak istiyor.
Nehirde bir kayık var.
Kayık ancak çobanı ve bir adet şeyi (ot, koyun ya da kurt) taşıyacak kadar büyük.
Başlarında çoban olmaz ise; kurt kuzuya saldırabiliyor, kuzu ise otu yiyebiliyor.
Çoban herkesi sağ salim nasıl karşıya taşır?
Evet, farkındayım… Basit bir bulmaca.
Peki ya bunu kod ile çozecek olsak?
İleride mantık-proglamlamadan ve declarative programlamadan bahsedeceğim. Bu yazı da o geleceğin ön-izlemesi olsun.
Potassco: Cevap Kümesi Programlama
Mantık programlama, problemi mantık kuralları halinde yazıp çözüme gidilen bir programlama biçimi.
Cevap-Kümesi programlama (Answer Set Programming) ise bunun daha da özel bir hali: doğru/yanlış tüm çözümlerin nasıl üretileceğini ve kısıtlarınızı belirtiyorsunuz. Sistem bu bilgiler çerçevesinde bulabildiği çözümleri sıralıyor.
Potassco(https://potassco.org/about/) da bu yaklaşımı sunan yegane çözümlerden birisi.
Dili ve yaklaşımı daha ufak bir problem ile örneklendireyim:
Üçe İkili Takla Attırmaca
-
Elinizde yan yana dizili 3 kart var.
-
Bu kartların üzerinde soldan sağa sırayla "A", "B" ve "C" yazıyor.
-
Yapabileceğiniz iki çeşit hamle var: soldaki kart ile ortadaki kartı yer değiştirebilirsiniz ya da ortadaki kart ile sağdaki kartı yer değiştirebilirsiniz.
-
Hangi hamleleri yapmanız gerekir ki kartlar ters sıraya girsinler: soldan sağa "C", "B", "A" şeklinde.
finish(c, b, a).
max_moves(3).
state(0, a, b, c).
state(T+1, Y, X, Z) :- state(T, X, Y, Z), not state(T+1, X, Z, Y), not max_moves(T). (1)
state(T+1, X, Z, Y) :- state(T, X, Y, Z), not state(T+1, Y, X, Z), not max_moves(T). (2)
:- state(M, X, Y, Z), max_moves(M), not finish(X, Y, Z). (3)
#show state/4. (4)| 1 | Eğer T vaktinde X,Y,Z halinde bir sistemim var ise T+1 halinde bu X,Z,Y olabilir (Y ve Z yer değiştirirse), eğer zaten T+1 anı için ben X ve Y'yi yer değiştirmeyi seçmemiş isem. |
| 2 | bir evvelki maddenin benzeri |
| 3 | Son state’in istediğim hal olmadığı durumları istemiyorum |
| 4 | Sonuçta sadece state kuralına dair bilgileri göster (/4 denmesi bu state kuralının 4 argüman aldığını belirtiyor) |
|
Bu ve tüm clingo kodlarını https://potassco.org/clingo/run/ adresinde deneyebilirsiniz. |
Solving... Answer: 1 state(0,a,b,c) state(1,a,c,b) state(2,c,a,b) state(3,c,b,a) SATISFIABLE
Ancak bu T'den T+1'e geçiş anı için tanımladığım kural bu seviyede bir problem için yeterli olsa da daha karmaşık olanlarda zorluk çıkaracak. Üstesinden kısıt-kapsamında-kural üreterek gelebiliyoruz:
card(a; b; c).
finish(c, b, a).
max_moves(3).
{ state(T, X, Y, Z) : card(X), card(Y), card(Z) } = 1 :- max_moves(M), T=1..M. (1)
state(0, a, b, c).
achievable_state(T+1, X, Z, Y) :- state(T, X, Y, Z).
achievable_state(T+1, Y, X, Z) :- state(T, X, Y, Z).
:- state(M, X, Y, Z), max_moves(M), not finish(X, Y, Z).
:- state(T, X, Y, Z), not achievable_state(T, X, Y, Z), max_moves(M), T=1..M. (2)
#show state/4.| 1 | 1'den max_moves'a kadar her bir T için sadece 1 değer üret. |
| 2 | bir yer-değiştirme ile elde edilemeyecek durumları istemiyorum. |
|
Bu 3 kart probleminde yapmamıza izin verilen 2 hamle ile kartların olabileceği tüm dizilimleri elde etmek mümkün. Bu 3 kart üzerinde tanımlayabileceğimiz her yeni hamleyi (1’nci kart ile 3’ncü kartı yer değiştirmek gibi, kartları bir sağa kaydırmak gibi [ Bu gibi sistemlere matematikte "grup", sistemi üretebilen en ufak hamle kümesine (bize verilen 2 hamle gibi) de sistemin "üreticileri"(generator) deniyor. Grup teorisine de ileriki zamanlarda değinmeyi düşünüyorum. |
Asıl Probleme Dönüş
Kurt, kuzu, ot probleminin, daha fazla kısıtı olması haricinde kart-değiştirme probleminden bir farkı yok.
shore(a; b).
item(wolf;sheep;grass).
attacks(wolf, sheep).
attacks(sheep, grass).
init_shore(X, a) :- item(X). (1)
goal_shore(X, b) :- item(X). (2)
my_start_shore(a).
moves(7).
{ move(X,S,T; nothing,S,T) : item(X), shore(S) } = 1 :- moves(M), T = 1..M.
myshore(S, 0) :- my_start_shore(S).
myshore(S, T) :- move(_,S,T). (3)
onshore(X, S, 0) :- init_shore(X, S).
onshore(X, S, T) :- item(X), move(X, S, T). (4)
onshore(X, S, T+1) :- onshore(X, S, T), not move(X, _, T+1), not moves(T). (4)
danger(S, T) :- item(X), item(Y), attacks(X, Y), onshore(X, S, T), onshore(Y, S, T), not myshore(S, T). (5)
:- move(_, S, T), move(_, S, T+1), shore(S). (6)
:- move(X, S, T+1), onshore(X, S2, T), not myshore(S2, T). (7)
:- not onshore(X, S, T), goal_shore(X, S), moves(T). (8)
:- danger(S, T), shore(S), moves(M), T=1..M. (9)
#show move/3.| 1 | Her bir item a yakasında başlamalı |
| 2 | Her bit item b yakasında bitirmeli |
| 3 | Benim (yani çobanın) bulunduğu yaka en son hamlenin yapıldığı yakadır |
| 4 | Eğer bir şey bir yakaya taşınmış ise, o an itibariyle o yakadadır. Eğer bir şeye son hamlemde dokunmamış isem, o şey önceden nerede ise oradadır |
| 5 | Eğer çobanın olmadığı bir yakadaki iki şeyden biri diğerine saldırmaya meyilli ise tehlike vardır. |
| 6 | Bir yakadan aynı yakaya hamle yapılmasın |
| 7 | Bulunduğum yakada olmayan şeyleri taşıyamam |
| 8 | Her şeyin çözümün sonunda gitmesi gereken yakaya gitmediği durumları istemiyorum |
| 9 | Herhangi bir anda tehlikeli bir durum olmasın |
Solving...
Answer: 1
move(sheep,b,1)
move(nothing,a,2)
move(wolf,b,3)
move(sheep,a,4)
move(grass,b,5)
move(nothing,a,6)
move(sheep,b,7)
SATISFIABLEBu yaklaşımı daha gündelik hayatta çözdüğümüz yazılım problemlerine nasıl yansıtacağımıza, hangi dillerde zaten aynı şeyi yaptığımıza daha sonra değineceğim.