Abstrak Modified Bi-Directional A* (MBDA*)

Abstrak Modified Bi-Directional A* (MBDA*) merupakan salah satu variasi algoritma A* yang dapat digunakan untuk menyelesaikan masalah shortest path. Algortima tersebut mampu menghasilkan performa yang bagus dalam menyelesaikan masalah shortest path dibandingkan dengan A* dalam pencarian yang lebih kompleks dan jumlah node yang besar. Pada tugas akhir ini, diterapkan algoritma MBDA* untuk menyelesaikan masalah shortest path namun dengan menambahkan fungsi, yaitu untuk menemukan middle node. Sehingga pencarian solusi akan dibangkitkan dari start menuju middle node dan dilanjutkan dengan pencarian dari middle node menuju goal node. Penulis memberi nama metode pencarian tersebut dengan Dgraph-MBDA*. Diharapkan dengan penambahan fungsi tersebut, waktu proses pencarian solusi semakin lebih cepat, dibandingkan dengan MBDA* yang dilakukan dengan cara biasa. Setelah dilakukan pengujian dapat disimpulkan bahwa, dengan menggunakan Dgraph-MBDA* ternyata waktu proses pencarian solusinya lebih cepat dibandingkan dengan MBDA*, namun algoritma Dgraph-MBDA* ini masih belum bisa untuk menemukan solusi yang optimal, dikarenakan masih terjebak dalam menentukan middle node yang akan digunakan sebagai pembagi graf ke dalam dua bagian. Kata Kunci : MBDA*, shortest path, Dgraph-MBDA*