PENERAPAN POHON PELACAKAN DALAM MENCARI LINTASAN YANG DAPAT DILALUI OLEH SEEKOR SEMUT PADA BIDANG KARTESIAN DENGAN METODE BREADTH FIRST SEARCH

Abstract

Pohon Pelacakan adalah suatu metode pelacakan yang dapat diterapkan untuk mencari solusi pada bidang ilmu Artificial Intelligence (AI). Salah satu contoh persoalan AI yang memerlukan penerapan pohon pelacakan adalah dalam pencarian lintasan yang dapat dilalui oleh seekor semut melalui bidang kartesian. Bidang Kartesian merupakan sistem dua dimensi sistem koordinat yang terdiri dari dua salib sumbu yang saling tegak lurus. Pencarian dimulai dari posisi awal semut sebagai node akar, selanjutnya metode BFS mencari solusi dengan mengembangkan node akar ke level-level berikutnya, semua pergerakan yang memungkinkan, tidak melanggar ketentuan dan syarat serta menghasilkan kondisi baru yang dapat dikembangkan semaksimal mungkin. Pencarian berakhir apabila tidak ada lagi node atau kondisi baru yang dapat dikembangkan. Semua node yang merupakan posisi tujuan merupakan solusi. Hasil penelitian ini adalah sebuah perangkat lunak dapat digunakan untuk bermain ‘Permainan Semut Mencari Permen’ pada sebuah komputer.
Kata Kunci : Pohon Pelacakan, Bidang Kartesian, Metode Breadth First Search.