BFS dan Algorithm

Nama    : Petronela H. Manehat
Nim     : 11110097
Kelas   : Extention

Best-First Search VS A* (Kupang-Toraja)

Best-First Search adalah algoritma pencarian dengan menggunakan heuristic. Berikut adalah contoh penggunaan metode BFS untuk permasalahan Kupang -Toraja.

Berikut ini adalah peta Indonesia dengan jarak jalan-jalan yang menghubungkan kota-kota dalam km.

 

Adapun jarak kota-kota terhadap kota Toraja jika ditarik garis lurus (perkiraan atau h(n)) adalah sebagai berikut :

Kota	Estimasi Awal ke Tujuan
Kupang	2000
Soe	2110
Kefa	2200
Atambua	2230
Toraja	0
Malang	1800
Surabaya	1700
Makasar	500
Ambon	300
Nabire	2300

Permasalahannya adalah untuk mencari jalan terdekat dari kota Kupang menuju kota Toraja dengan menggunakan metoda Best First Search dan A*.

 Best First Search

Heuristik yang digunakan adalah jarak kota-kota terhadap kota Toraja jika ditarik garis lurus (perkiraan) yang jaraknya seperti yang tertera di atas dengan asumsi kota terhubung yang letaknya paling dekat dengan kota Toraja adalah jalan yang paling optimal.

Diagram pohon langkah-langkah penelusuran dengan metode Best First Search adalah sebagai berikut :

Langkah 1

 

Langkah 2

 

Langkah 3

 

Dari Langkah-langkah di atas, dengan metode Best First Search didapatkan kota-kota yang harus dilalui untuk mendapatkan jalan yang paling dekat jaraknya dari Kupang ke Toraja adalah : Kupang – Makassar – Toraja.

Dari peta diatas, panjang jalan yang dilalui adalah 1300 + 245 = 1545 Km.

A* Algorithm

A* Algorithm menggunakan dua fungsi cost sebagai acuan penelusuran yaitu jarak yang telah dilalui dari kota asal Kupang ke kota tersebut ditambah dengan heuristik jarak kota-kota terhadap kota Toraja jika ditarik garis lurus  (perkiraan) seperti yang digunakan pada Best First Search, jadi fungsi cost  àf(n) = g(n) + h(n).

Diagram pohon langkah-langkah penelusuran dengan metode A* adalah sebagai berikut :

Langkah 1

 

Langkah 2

  

Langkah 3

 
 

 

Dari Langkah-langkah di atas, dengan metode A* didapatkan kota-kota yang harus dilalui untuk mendapatkan rute jalan yang paling dekat jaraknya dari Kupang ke Toraja adalah :

Kupang – Makassar – Toraja.

Dari peta di atas, panjang jalan yang dilalui adalah

1800 + 245 = 2045 km.

Jika dibandingkan dengan hasil metode Best First Search, penelusuran dengan metode A* untuk mencapai goal lebih sama kedalamannya (BFS=3 langkah, A* = 3 langkah). Begitu juga Node yang dieksplore, metode A* sama banyak dengan Best First Search. Akan tetapi, rute yang dihasilkan dengan metode Best First Search lebih baik dari A*  (BFS=1545 km, A*= 2045)