Perbandingan Algoritma A* dan Algoritma Best First Search Modification Untuk Mencari Jalur Terpendek Pasar Swalayan di Kota Medan

Abstract

Supermarkets, are the main provider of our daily essential needs. But often the items that we want aren't available in one particular supermarket but obtainable in the other. To acquire those particular items, we have to reach the next nearest supermarket. Yet sometimes the shortest route isn't familiar to us, especially in a large city like Medan. To tackle the problem, a system to identify the optimal route from a supermarket to another would be needed. For this purpose, in this research an optimal route finder system to find the optimal route to the designated supermarket was created. This system has the ability to find the optimal route based on a chosen starting point to a chosen destination point. To optimize the route searching process the system utilizes the A* algorithm and the Best First Search Modification algorithm. The results of these two algorithms would be then compared, based on their complexity and their respective running time. After the implementation of the two algorithms, it is known that the A* algorithm with a complexity of θ (n3) has an average running time of 151.30ms. Meanwhile, the Best First Search Modification algorithm with a complexity of θ (n3) has an average running time of 124.31ms. From the aforementioned results, it was concluded that the Best First Search Modification algorithm is the more efficient algorithm based on their running time and would nevertheless find the most efficient and the shortest pathway to the destination point.

Pasar Swalayan adalah pusat pembelian kebutuhan pokok, kadang kita tidak menemukan barang atau kebutuhan yang ingin kita beli dan kita akan mencari barang tersebut di Pasar Swalayan lainnya. Kita tidak tau jalur mana yang terdekat ke pasar swalayan yang ingin kita tuju terlebih lagi untuk kota besar seperti kota Medan. Dibutuhkan sebuah sistem yang berfungsi untuk mencari rute optimum dari Pasar Swalayan yang kita tempati saat ini ke Pasar Swalayan yang lainnya. Pada penelitian ini, maka dibuatlah sebuah sistem pencarian rute yang optimum untuk mencari Pasar Swalayan yang ingin dituju. Sistem ini memiliki menu untuk melakukan pencarian dengan memilih titik awal serta titik tujuan yang akan menghasilkan rute optimum untuk mencapai titik tujuan tersebut. Untuk mendukung optimasi pencarian rute dalam sistem ini diterapkan algoritma A* dan algoritma Best First Search Modification yang kemudian akan dibandingkan performa running time. Setelah itu dilakukanlah implementasi dan perbandingan kedua algoritma tersebut dan lalu diketahui bahwasanya kompleksitas algoritma ... adalah ... dan memiliki rata-rata running time 151.30 ms sedangkan kompleksitas algoritma Best First Search Modification adalah .... dan memiliki rata-rata running time 124.31 ms. Maka disimpulkan bahwa algoritma Best First Search Modification lebih efisien dalam waktu (running time) dibandingkan algoritma ... dan juga menghasilkan jarak yang terpendek dalam pencarian jalur yang pertama.