Best-First Search VS A* (Kupang-Toraja)
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 Sebagian daerah Indonesia dengan jarak jalan-jalan yang menghubungkan kota-kota dalam km.
Adapun jarak kota-kota terhadap kota Bucharest jika ditarik garis lurus (perkiraan atau h(n)) adalah sebagai berikut :
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 Bucharest jika ditarik garis lurus (perkiraan) 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
perkiraan jarak dari kupang ke toraja bila di tarik garis lurus
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 :
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 besar kedalamannya (BFS=3 langkah, A* = 3 langkah). Begitu juga Node yang dieksplore, metode A* sama banyak dengan Best First Search (BFS=10 node, A*=14 node). Akan tetapi, rute yang dihasilkan dengan metode Best First Search lebih baik dari A* (BFS=1545 km, A*= 2045 km).
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 Sebagian daerah Indonesia dengan jarak jalan-jalan yang menghubungkan kota-kota dalam km.
Adapun jarak kota-kota terhadap kota Bucharest 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*.
Heuristik yang digunakan adalah jarak kota-kota terhadap kota Bucharest jika ditarik garis lurus (perkiraan) 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
perkiraan jarak dari kupang ke toraja bila di tarik garis lurus
Langkah 2
Cabang atau pilihan jalan yang dapat di lalui dari kota kupang menuju toraja
Langkah 3
Memilih Cabang yang memiliki Estimasi jarak terdekat dengan kota tujuan(toraja).
Yaiti makasar, maka kita ambil lagi cabang atau pilihan jalan yang dapat di lalui dari kota makasar.
namun ternyata dari kota makasar terdapa jalan yang langsung menuju ke toraja,
maka selesai...
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.Yaiti makasar, maka kita ambil lagi cabang atau pilihan jalan yang dapat di lalui dari kota makasar.
namun ternyata dari kota makasar terdapa jalan yang langsung menuju ke toraja,
maka selesai...
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
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 besar kedalamannya (BFS=3 langkah, A* = 3 langkah). Begitu juga Node yang dieksplore, metode A* sama banyak dengan Best First Search (BFS=10 node, A*=14 node). Akan tetapi, rute yang dihasilkan dengan metode Best First Search lebih baik dari A* (BFS=1545 km, A*= 2045 km).
0 komentar:
Post a Comment