canibali
💻 Bilgisayar, 💾 Programlama

Yamyamlar & Misyonerler

canibaliYamyamlar 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

👋 🚨 Yeni yazılardan haberdar olmak ister misiniz? 👇

Yamyamlar & Misyonerler 5 yorum aldı.

  1. Bunun için fonksiyon falan yapamıyor muyuz? Misal:

    function possibleActions($theAction) {
    $action = possibleActions.add(new Integer[] { $theAction});
    return $action;
    }

    desek, ne güzel olmaz mı? 😀

    İğrenç bir dil. Nefret ediyor ve hemen kaçıyorum bu yazıdan.

  2. ilk satırda iki misyonerin kayıkla karşı taafa geçmesi…hatalı bence…tek kalan ile yamyamlar iftarı açarlar artık…ne diyelim Allah kabul etsin.

  3. Algoritma hatalı 3. adımda hata var doğrusunda 9 adım değil minumum 11 adımda bulunabiliyor.

  4. Çözüm hatalı. Taşıma işlemini yaparken sağ taraftaki yamyam sayısı misyoner sayısından fazla oluyor.

Bir yanıt yazın

E-posta adresiniz yayınlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir