Tugas 2 Problem Solving, Search

Dalam mengembangkan Artificial Intellegence hal yang sangat diperhatikan adalah sebuah sistem harus mampu mencari solusi dan menyelesaikan suatu masalah. PadaArtificial Intellegence permasalahan di definisikan dalam 4 item :

1. Initial State, merupakan keadaan awal dari suatu masalah.
2. Successor Function, merupakan kombinasi dari berbagai aksi.
3. Goal Test, menentukan tujuan yang akan dicapai.
4. Path Cost, adalah total besarnya biaya(jarak, aksi, dll) untuk setiap langkahnya.

Pada kesempatan ini saya akan membahas masalah dan pencarian solusi dari game teka-teki Missionaries and Cannibals. Permasalahan dalam game ini adalah terdapat 3 misionaris dan 3 kanibal yang harus menyebrang ke sisi sungai menggunakan sebuah perahu, dimana perahu tersebut dapat berjalan jika terdapat minimal 1 orang dan maksimal 2 orang. Tetapi jumlah kanibal tidak boleh lebih banyak dari jumlah misionaris di salah satu sisi, jika tidak maka misionaris akan dimakan oleh kanibal.

Salah satu metode yang digunakan untuk mencari solusi pada game ini adalah algoritma BFS (Breadth-First Search). Pencarian solusi menggunakan algoritma ini menghasilkan langkah yang optimal, dikarenakan pencarian dilakukan secara melebar dari node akar sampai node akhir.

Penerapan Breadth-First Search  pada game

Setiap state dijadikan sebuah simpul pada pohon. State awal adalah sisi kiri masih kosong, dan sisi kanan terdapat 3 misionaris & 3 kanibal. Untuk mempermudah penggambaran, maka dibuat notasi untuk setiap simpul. Untuk state awal, notasinya adalah “(0,0)|(3,3)K” yg berarti di sisi kiri terdapat 0 misionaris & 0 kanibal, dan di sisi kanan terdapat 3 misionaris & 3 kanibal. Sedangkan notasi akhirnya adalah “K(3,3)|(0,0)”. Berikut state space pohon pencariannya :

Langkah penyelesaian/solusi dari game Missionaries and Cannibals :

1. Kanibal dengan kanibal menyebrang, satu kanibal turun.

2. Kanibal kembali

3. Kanibal dengan kanibal menyebrang, satu kanibal turun

4. Kanibal kembali dan turun

5. Dua misionaris menyebrang, satu turun

6. Satu misionaris kembali bersama kanibal, kanibal turun

7. Dua misionaris menyebrang, keduanya turun

8. Kanibal naik dan menjemput kanibal

9. Satu kanibal turun

10. Kanibal satunya menjemput

11. Dua kanibal menyebrang dan turun

Kesimpulan

Algoritma Breadth-First Search (BFS) dapat diterapkan untuk berbagai macam masalah, salah satunya adalah untuk pencarian solusi dari game Missionaries and Cannibals. Karena pencarian dilakukan secara melebar dari node akar sampai node akhir. Kelemahan dari algoritma ini adalah memerlukan banyak memori dikarenakan pencarian yang banyak. Dan keuntungannya adalah langkah yang dihasilkan lebih optimal.