Studi Komparasi Algoritma A* Dan Algoritma Breadth First Search (Bfs)
Total View This Week0
Total View This Week0
Institusion
Universitas Komputer Indonesia
Author
Aditiya, Valdyna
Subject
620_Engineering & Allied Operations.
Datestamp
2022-05-27 08:36:57
Abstract :
Tujuan penelitian ini adalah untuk membandingkan antara algoritma Breadth First Search (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 mencapai titik goal. 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 sehingga membuat waktu eksekusi menjadi perbedaan. 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.
Tujuan penelitian ini adalah untuk membandingkan antara algoritma Breadth First Search (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 mencapai titik goal. 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 sehingga membuat waktu eksekusi menjadi perbedaan. 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.
File :
UNIKOM_Valdyna A_Cover.pdf
UNIKOM_Valdyna A_Lembar Pengesahan.pdf
UNIKOM_Valdyna A_Bab V.pdf
UNIKOM_Valdyna A_Daftar Pustaka.pdf
Kontak Penulis dan Kontributor Penelitian.pdf
UNIKOM_Valdyna A_Surat Keterangan Persetujuan Publikasi.pdf
UNIKOM_Valdyna A_Surat Pernyataan Tidak Plagiat.pdf
UNIKOM_Valdyna A_Kata Pengantar.pdf
UNIKOM_Valdyna A_Daftar Isi.pdf
UNIKOM_Valdyna A_Bab I.pdf
UNIKOM_Valdyna A_Bab II.pdf
UNIKOM_Valdyna A_Bab III.pdf
UNIKOM_Valdyna A_Bab IV.pdf
Download
book
BibTex
Latex, Jabref
cloud_download
Original Resource
url resource Institution
