Desain & Analisis Algoritma

Menyelesaikan game dengan Algoritma

Domain Masalah : Seorang Petani akan berpergian ke kota dengan membawa seekor Domba, Sayuran dan Serigala Yang ketiganya memliki berat yang tidak jauh berbeda, ditengah jalan petani harus menyebrangi sungai dengan menggunakan perahu dan untuk melaluinya petani tersebut tidak diperbolehkan membawa sekaligus bawaannya mengingat kapasitas kekuatan perahu tersebut, dan untuk melaluinya petani harus membawa satu persatu bawaannya.

Ruang Lingkup :
a. Keadaan Awal

Petani, Domba, Sayuran dan Serigala ada di sebelah kanan atau daerah awal

b. Keadaan Akhir

Petani, Domba, Sayuran dan Serigala ada disebelah kiri atau daerah tujuan

Aturan-aturan :

a.   Perahu hanya memuat 2 penumpang

b.   Tidak boleh meninggalkan sayuran dan domba

c.   Tidak boleh meninggalkan domba dan serigala

d.   Semua objek harus menyebrang

Ditanya: Berapa kali petani tersebut harus menyebrangkan ketiga objek tersebut dengan memperhatikan bahwa Domba makan Sayuran, dan Serigala makan Domba ?

Penyelesaian :

1. Seberangkan Domba ke tepi kiri.
2. Setelah di seberang kiri, Turunkan Dombanya lalu Manusia menyeberang lagi ke tepi kanan.
3. Seberangkan Sayuran ke tepi kiri
4. Setelah di seberang kiri, Turunkan Sayuran lalu masukkan Domba ke perahu kemudian menyeberang lagi ke tepi kanan.
5. Setelah di seberang kanan, Turunkan Dombanya kemudian masukkan Serigala lalu menyeberang lagi ke tepi kiri.
6. Setelah di seberang kiri, Keluarkan Srigala lalu meneyeberang lagi ke tepi kanan.
7. Setelah di seberang kanan, masukkan Domba lalu meneyeberang lagi ke tepi kiri lalu turunkan.

Kesimpulan : Petani tersebut harus 7kali menyebrang agar tidak meninggalkan 2 objek yang berhubungan, misalnya sayuran dengan domba atau domba dengan serigala.