Analisis Perbandingan Algoritma Breadth First Search (BFS) dan Algoritma A*

Author

Budi Herdiana, S.T., M.T.

Abstrak

Pada path planning terdapat beberapa metode yang dapat digunakan. Metode yang dapat digunakan untuk path planning yaitu algoritma Breadth First Search (BFS) dan algoritma A*. Metode yang digunakan tergantung dari keadaan lingkungan. Pengujian path planning pada berbagai lingkungan dengan menggunakan metode yang berbeda dapat mengetahui performansi tiap metode tersebut. Sehingga tujuan penelitian ini adalah untuk membandingkan antara algoritma BFS dengan algoritma A* dalam melakukan path planning. Proses perbandingan dilakukan pada lima lingkungan pengujian. Lingkungan pengujian yang digunakan yaitu tanpa obstacle, obstacle trap, obstacle sederhana, obstacle maze dan obstacle narrow. Perbandingan algoritma BFS dan algoritma A* berdasarkan waktu eksekusi dan jumlah node yang dibutuhkan untuk melakukan path planning. Hasil penelitian menunjukkan bahwa pencarian jalur dari titik start ke titik goal dapat diselesaikan dengan algoritma BFS dan A*. Pada algoritma BFS maupun A* menghasilkan biaya jalur yang sama. Perbedaan terjadi pada node-node yang dibutuhkan algoritma BFS dan A* untuk menghasilkan jalur dari titik start hingga titik goal. Algoritma BFS membutuhkan node lebih banyak dibandingkan dengan A* untuk mencapai titik goal. Perbedaan jumlah node tersebut membuat waktu eksekusi menjadi berbeda. Waktu eksekusi pada algoritma BFS membutuhkan waktu lebih banyak dibandingkan dengan A*. Berdasarkan pengujian yang telah dilakukan maka algoritma A* lebih cepat dalam melakukan path planning. Tetapi pada lingkungan pengujian maze terjadi perbedaan waktu yang sedikit. Pada BFS memerlukan waktu tercepat 4,09 detik serta pada A* memerlukan waktu tercepat 3,88 detik. Serta pada lingkungan maze memiliki perbedaan jumlah node cukup sedikit yaitu 26 node. Hal tersebut membuktikan bahwa A* tidak selalu unggul jauh dengan BFS.