IMPLEMENTASI ALGORITMA BREADTH FIRST SEARCH

PENJELASAN BREADTH FIRST SEARCH

Algoritma Breadth-First Search (BFS) atau dikenal juga dengan nama algoritma pencarian melebar adalah algoritma yang melakukan pencarian secara melebar yang mengunjungi simpul secara preorder yaitu mengunjungi suatu simpul kemudian mengunjungi semua simpul yang bertetangga dengan simpul tersebut terlebih dahulu. Selanjutnya, simpul yang belum dikunjungi dan bertetangga dengan simpulsimpul yang tadi dikunjungi , demikian seterusnya.

ALUR ALGORITMA BREADTH FIRST SEARCH

Dalam algoritma Breadth First Search, simpul anak yang telah dikunjung disimpan dalam antrian. Antrian ini digunakan untuk mengacu simpul-simpul yang bertetangga dengan yang akan dikunjung kemudian sesuai urutan pengantrian untuk memperjelas cara kerja algoritma BFS beserta antrian yang digunakannya.

Berikut langkah-langkah Breadth First Search :

1.     Masukkan simpul ujung (akar) ke dalam antrian.

2.    Ambil simpul dari awal antrian, lalu cek apakah simpul merupakan solusi.

3.    Jika simpul merupakan solusi, pencarian selesai dan hasil dikembalikan.

4.    Jika simpul bukan solusi, masukkan seluruh simpul yang bertetangga dengan simpul tersebut (simpulanak) ke dalam antrian.

CONTOH IMPLEMENTASI PENYELESAIAN MASALAH DENGAN MENGGUNAKAN ALGORITMA BREADTH FIRST SEARCH

       Berikut ini adalah penyelesaian masalah algoritma breadth first search dengan judul jurnal “Simulasi Rute Terpendek Lokasi Pariwisata Di Nias Dengan Metode Breadth First Search dan Tabu Search”.

BFS merupakan mencarian jalur terpendek namun tidak optimal berdasarkan jarak oleh sebab itu perlu Modifikasi algoritma Breadth First Search dan Tabu Search untuk memperoleh jalur terpendek berdasarkan jarak, berikut contoh modifikasi algoritma BFS dan tabu search seperti yang ada pada gambar ini.

Misalkan menetukan jalur terpendek dari A ke E berdasarkan modifikasi Breadth First Search dengan Tabu Search, maka berdasarkan pada gambar ini,

kita dapat mengimplementasikan kedalam BFS dan Tabu Search untuk memperoleh jalur terpendek dengan langkah-langkah sebagai berikut.

Ø  Langkah ke 1

Kita ambil state awal adalah A, A memiliki pilihan jalur yaitu menuju B dan D dan F sehingga kita dapat repsentasif pohon pencarian.

Ø  Langkah ke 2

Kita melakukan pencarian jalur terpendek berdasarkan konsep dari Breadth First Search yang telah dimodifikasi dengan algoritma Tabu Search. Tujuan dari pencarian adalah menemukan titik E. Pencarian diawali dengan menelusuri titik pangkal yaitu titik A, karena titik A merupakan titik dengan level tertinggi maka penelusuran dilanjutkan dengan menjelajahi titik-titik pada level di bawahnya atau simpul yang bertetangga dengan simpul tersebut (simpul anak), seperti yang terlihat pada gambar ini.

bahwa ini bukan merupakan solusi maka dilakukan pencarian lagi untuk menemukan tujuan atau solusinya.

Ø  Langkah ke 3

Solusi ditemukan dengan jarak 9000, goal ini disimpan tetapi ini belum tentu merupakan jalur terpendek maka melakukan pencarian lagi untuk mendapatkan jalur terpendek.

Ø  Langkah ke 4

Cek jarak untuk melihat node yang tidak bisa lagi dilanjutkan pencariannya karena melampaui atau sama dengan jarak sebelumnya.

Solusi ditemukan lagi dengan jarak 8000 maka jarak ini disimpan dan menggantikan jarak sebelumnya, tetapiini belum tentu merupakan jalur terpendek maka melakukan pencarian lagi untuk mendapatkan jalur terpendek

Solusi ditemukan lagi dengan jarak 6000 maka jarak ini disimpan dan menggantikan jarak sebelumnya, dengan demikian proses pencarian berhenti karena jarak yang akan lalui sudah melampaui atau sama dengan jarak sebelumnya. Maka berdasarkan proes penelusuran diatas dengan metode Breadth First Search dan Tabu Search ditemukan jalur terpendek dari A menuju E adalah A,D,C,E dengan jarak 6000.

KESIMPULAN

Berdasarkan hasil implementasi rancangan dari simulasi rute terpendek lokasi pariwisata di pulau Nias berbasis web dengan metode Breadth First Searchdan Tabu Searchmaka dapat disimpulkan bahwa aplikasi pencarian jalur terpendek menggunakan algoritma modifikasi Breadth First Search dengan Tabu Searchdapat diimpelementasikan dan digunakan di pulau Nias dan program simulasi yang dibuat mampu menunjukkan jalur terpendek yang optimal dengan modifikasi algoritma Breadth First Search dan Tabu Search.

REFERENSI

Zai, D., Budiati, H., & Berutu, S. S. (2016). SIMULASI RUTE TERPENDEKLOKASI PARIWISATA DI NIASDENGANMETODE BREADTH FIRST SEARCH DANTABUSEARCH. Jurnal InFact, 30-41.