Best-First Search VS A* (Arad-Bucharest)
Tidak seperti Depth-First Search (DFS) atau Breadth-First Search BFS), Best-First Search adalah algoritma pencarian dengan menggunakan heuristic. Berikut adalah contoh penggunaan metode BFS untuk permasalahan Arad-Bucharest.Berikut ini adalah peta Romania dengan jarak jalan-jalan yang menghubungkan kota-kota dalam km.
Adapun jarak kota-kota terhadap kota Bucharest jika ditarik garis lurus adalah sebagai berikut :
Arad 366
Bucharest 0
Craiova 160
Dobreta 242
Eforie 161
Fagaras 178
Giurgiu 77
Hirsova 151
Iasi 226
Lugoj 244
Mehadia 241
Neamt 234
Oradea 380
Pitesti 98
Rimnicu Vilcea 193
Sibiu 253
Timisoara 329
Urziceni 80
Vaslui 199
Zerind 374
Permasalahannya adalah untuk mencari jalan terdekat dari kota Arad menuju kota Bucharest dengan menggunakan metoda Best First Search dan A*.
Best First Search
Heuristik yang digunakan adalah jarak kota-kota terhadap kota Bucharest jika ditarik garis lurus yang jaraknya seperti yang tertera di atas dengan asumsi kota terhubung yang letaknya paling dekat dengan kota Bucharest adalah jalan yang paling optimal.
Diagram pohon langkah-langkah penelusuran dengan metode Best First Search adalah sebagai berikut :
Langkah 1
Langkah 2
Langkah 3
Langkah 4
Dari Langkah-langkah di atas, dengan metode Best First Search didapatkan kota-kota yang harus dilalui untuk mendapatkan jalan yang paling dekat jaraknya dari Arad ke Bucharest adalah : Arad – Sibiu – Fagaras – Bucharest. Dari peta di atas, panjang jalan yang dilalui adalah 140+99+211 = 450 km.
A* Algorthm
A* Algorithm menggunakan dua fungsi cost sebagai acuan penelusuran yaitu jarak yang telah dilalui dari kota asal Arad ke kota tersebut ditambah dengan heuristik jarak kota-kota terhadap kota Bucharest jika ditarik garis lurus 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
Langkah 4
Langkah 5
Dari Langkah-langkah di atas, dengan metode A* didapatkan kota-kota yang harus dilalui untuk mendapatkan rute jalan yang paling dekat jaraknya dari Arad ke Bucharest adalah : Arad – Sibiu – Rimnicu – Pitesti – Bucharest. Dari peta di atas, panjang jalan yang dilalui adalah 140+80+97+101 = 418 km.
Jika dibandingkan dengan hasil metode Best First Search, penelusuran dengan metode A* untuk mencapai goal lebih besar kedalamannya (BFS=4 langkah, A* = 5 langkah). Begitu juga Node yang dieksplore, metode A* lebih banyak daripada Best First Search (BFS=10 node, A*=14 node). Akan tetapi, rute yang dihasilkan dengan metode A* lebih baik dari Best First Search (BFS=450 km, A*= 418 km).
Jelas bahwa jika masalah yang dihadapi diprioritaskan kepada cost yang optimum, metode A* lebih baik digunakan, sedangkan jika kecepatan mencapai goal lebih diprioritaskan maka metode Best First Search lebih baik digunakan.
