Yamyamlar & Misyonerler

Yamyamlar ve Misyonerler, bir çoğumuzun bildiği “Kurt, kuzu, saman, nehir” bilmecesinin bir benzeridir.

Problem

Bilmece şu şekildedir:

Nehrin bir kenarında 3 tane misyoner, 3 tane de yamyam bulunmaktadır. Bunlar bir kayık ile nehrin diğer tarafına geçecektir. Ancak bu kayık aynı anda en fazla iki kişi taşıyabilmektedir ve kayığın hareket edebilmesi için en az bir kişinin kayıkta olması gerekmektedir. Nehrin iki tarafı için ayrı ayrı, eğer yamyam sayısı misyoner sayısından fazla olursa yamyamlar misyonerleri yemektedir. Bu topluluk hiç kayıp vermeden karşıya nasıl geçer?

Çözüm

Bu problem üzerinde geçen sene Yapay Zeka dersinde durmuştuk. Problemin BFS (Breadth First Search) arama yöntemi ile çözümünü kodlamıştım.

private final static Integer[] startingArray = { 3, 3, 1 };

private final static Integer[] solutionArray = { 0, 0, 0 };

static { 
    possibleActions.add(new Integer[] { 2, 0, 1 }); 
    possibleActions.add(new Integer[] { 1, 0, 1 }); 
    possibleActions.add(new Integer[] { 1, 1, 1 }); 
    possibleActions.add(new Integer[] { 0, 1, 1 }); 
    possibleActions.add(new Integer[] { 0, 2, 1 }); 
}

startingArray ile, nehrin sol kıyısındaki (sırasıyla) misyoner, yamyam ve kayık sayısı verilir. (başlangıç durumu)

solutionArray ile problemin çözüldüğü durumda nehrin sol kıyısının nasıl görünmesi gerektiğinin bilgisi verilir. (hiç kimse yok) (aranan durum, çözüm)

possibleActions ile, kayık üzerinde yapılabilecek hareketler verilir. Örneğin, ilk satırda 2 misyonerin 1 kayık ile gidebileceği, üçüncü satırda ise 1 misyoner ve 1 yamyamın 1 kayık ile gidebileceği bilgisi tanımlanmaktadır.

Daha sonra BFS ile tüm olasılıklar gezilerek çözüm aranır.

İndir

• JAVA ile yazılmış Yamyamlar ve Misyonerler (Missionaries & Cannibals) problemi çözümü
• Oyna (Flash ile programlanmış, oynanabilir bir sürüm)