Evaluasi dan Usaha Optimalisasi Algoritma Depth First Search dan Breadth First Search dengan Penerapan pada Aplikasi Rat Race dan Web Peta
Daftar Isi:
- Rat Race adalah permainan labirin dimana hanya terdapat satu jalan masuk dan satu jalan keluar. Tujuan dari permaianan ini adalah untuk mencari jalan keluar dari dalam labirin. Dalam permainan ini digunakan karakter tikus, tikus harus bisa berjalan didalam labirin untuk mencari jalankeluar. Dalam permainan ini digunakan algoritma yang menerapkan kecerdasan buatan, hal ini bertujuan agar tikus tidak hanya asal berjalan saja di dalam labirin. Dalam permainan ini terdapat beberapa aturan yaitu tikus hanya bisa berjalan ke empat arah atas, bawah, kiri dan kanan. Tiap kali tikus melangkah akan dihitung. Tujuan dari aplikasi ini adalah membuat karakter tikus menjadi pintar, dapat melihat, berjalan dan mengingat labirin ataupun langkah yang telah diambilnya. Terdapat dua algoritma yang digunakan dalam aplikasi ini, Depth First Search danBreadth First Search. Algoritma Depth First Searchmemiliki fungsi backtracking untuk membuat karakter tikus menjadi lebih pintar. Breadth First Search juga memiliki fungsibacktracking tetapi dengan bantuan algoritma bidirectional search, yang bertujuan menemukan rute. Pada aplikasi yang baru, perbaikan dilakukan agar tikus dapat mencari jalan keluar dengan lebih cepat dan pintar. Perbaikan pada algoritma Depth First Searchdilakukan pada fungsi backtracking. Pada fungsi ini pengecekan tujuan yang dilakukan oleh tikus dikurangi, karena sebelumnya telah dilakukan pengecekan tujuan. Jadi pengecekan tujuan tidak dilakukan berulang-ulang. Pada algoritma Breadth First Search perbaikan dilakukan pada cara tikus melihat dan membuat pohon pencarian. Level pada pohon pencarian baru akan bertambah jika tikus menemukan persimpangan. Hasil perbaikan pada algoritmaBreadth First Search menghasilkan jumlah langkah yang lebih sedikit dibandingkan dengan algoritma yang lama. Pada algoritma Depth First Search pengecekan tujuan menjadi lebih sedikit. Selain itu terdapat aplikasi lain yang dinamakan “WebPeta”. Aplikasi ini bertujuan menerapkan algoritma pencarian pada peta jalan. Aplikasi dapat mencari rute terpendek dan rute alternatif dari satu tempat ke tempat lain didalam peta menggunakan algoritma Depth First Search. Aplikasi ini menunjukan bahwa algoritma pencarian dalam hal ini Depth First Search dapat diterapkan pada aplikasi lain selain Rat Race.