Analisis Performansi Algoritma MBDA* pada Penyelesaian Shortest Path dengan Membagi Graf Menjadi Dua Bagian

Hutari Laksono

Informasi Umum

Kode

113071037

Klasifikasi

005.1 - Computer programming

Jenis

Karya Ilmiah - Skripsi (S1) - Reference

Subjek

Informatika Teori Dan Pemrograman

Dilihat

28 kali

Informasi Lainnya

Abstraksi

ABSTRAKSI: 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-MBDAABSTRACT: Modified Bi-Directional A * (MBDA *) is one variation of A * algorithm that can beused to solve shortest path problems. These Algorithms, able to produce good performance in solving the shortest path problem in comparison with A * in the search for more complex and a large number of nodes. In this thesis, MBDA * algorithm is applied to solve the shortest path problem, but withadded functions, namely to find the middle node. So the search for solutions will be raised from the start to the middle node and followed by searching of the middle node to the goal node. The author gave the name search method with Dgraph-MBDA *. Expected with the addition of these functions, the process of finding the solution, more quickly than with MBDA * conducted in the normal way. After testing it can be concluded that, by using Dgraph-MBDA * was the time the process of finding a solution more quickly than the MBDA *, but the algorithmDgraph-MBDA * is still not able to find the optimal solution, because it still stuck in the middle node will determine used as a divider graph into two parts.Keyword: MBDA, shortest path, Dgraph-MBDA*