PENCARIAN BERBENTUK
NAMA : SITI CAHYANI (16115603)
KELAS : 3KA10
DOSEN : ESSY MALAYS SARI SAKTI
Best-First Search
Sesuai dengan namanya,
best-first search
merupakan sebuah metode yang membangkitkan simpul dari
sebuah simpul sebelumnya (yang sejauh ini terbaik di antara semua simpul yang pernah
dibangkitkan). Penentuan simpul terbaik dilakukan dengan menggunakan sebuah
fungsi yang disebut fungsi evaluasi f(n)[5]. Pada best-first search jika successor digunakan, maka dikatakan algoritma mengembangkan
simpul tersebut. Setiap sebuah simpul dikembangkan,
algoritma akan menyimpan setiap successor simpul n sekaligus dengan harga (cost) dan petunjuk pendahulunya yang disebut
―parent‖. Algoritma akan berakhir pada simpul tujuan, dan tidak ada lagi
pengembangan simpul. Fungsi evaluasi pada best-first search dapat berupa informasi biaya
perkiraan dan suatu simpul menuju ke simpul tujuan atau gabungan antara biaya
sebenarnya dan biaya perkiraan tersebut. Biaya perkiraan dapat diperoleh dengan
menggunakan suatu fungsi yang disebut fungsi heuristic. Pada strategi
best-first search, cost
sebenarnya yaitu dari simpul awal ke simpul n, dinotasikan
dengan g(n) dan
fungsi heuristic
yang digunakan yaitu perkiraan\estimasi nilai dari simpul nke simpul tujuan dinotasikan
dengan h(n).
Algoritma yang menggunakan metode best-first search, yaitu :
§Greedy
Best-First Search
§Algoritma
A*Berikut akan diberikan beberapa istilah yang sering digunakan pada metode
best-first search:
§Start Node adalah sebuah terminologi untuk
posisi awal sebuah pencarian.
§Current Node
adalah simpul yang sedang dijalankan (yang sekarang) dalam algoritma pencarian
jalan terpendek.
§Kandidat
(successor) adalah simpul-simpul yang berbatasan dengan current node, dengan
kata lain simpul-simpul yang akan diperiksa berikutnya.
§Simpul (node)
merupakan representasi dari area pencarian
§Open list adalah tempat menyimpan data simpul
yang mungkin diakses dari starting node maupun simpul yang sedang dijalankan.
§Closed list adalah tempat menyimpan data simpul
yang juga merupakan bagian dari jalur terpendek yang telah berhasil didapatkan.
§Goal nodeyaitu
simpul tujuan.
Parent
adalah current node dari successor/kandidat.
Fungsi Heuristic
Fungsi heuristic h(n)merupakan estimasi cost dari n ke simpul tujuan. Sangat penting
untuk memilih fungsi Heuristic
yang baik. Misalkan h*(n) merupakan cost sebenarnya dari simpul nke simpul
tujuan, maka pada algoritma A* terdapat kemungkinan yang terjadi pada pemilihan
fungsi Heuristic yang
digunakan yaitu (Amit Gaming):
§Jika h(n)–0,
sehingga hanya g(n)yang terlibat maka A* akan bekerja seperti halnya algoritma Djikstra.
§Jika h(n)≤ h*(n),
maka A* akan mengembangkan titik dengan nilai paling rendah dan algoritma A*
menjamin ditemukannya lintasan terpendek. Nilai h(n)terendah akan membuat
algoritma mengembangkan lebih banyak simpul. Jika h(n) ≤ h*(n), maka h(n) dikatakan heuristic yang admissible.
§Jika h(n)= h*(n),
maka A* akan mengikuti lintasan terbaik dan tidak akan mengembangkan titik-titik
yang lain sehingga akan berjalan cepat. Tetapi hal ini tidak akan terjadi pada
semua kasus. Informasi yang baik akan mempercepat kinerja A*.
§Jika h(n)≥ h*(n),
maka A* tidak menjamin pencarian rute terpendek, tetapi berjalan dengan cepat.
§Jika h(n) terlalu tinggi relative dengan g(n) sehingga hanya h(n) yang bekerja maka A* berubah jadi Greedy
Best First Search.
Algoritma pencarian lokal untuk masalah optimisasi
kombinatorik biasanya
digunakan pada
pseudopolynomial running time dan algoritma polynomial-time sering tidak
dapat menemukan solusi optimum lokal untuk masalah optimisasi NP−hard. Penelitian ini bertujuan
mengenalkan konsep optimalitas
-lokal dan
menunjukkan bahwa optimum
-lokal dapat diidentifikasi dengan waktu polyno-mial pada
masalah ukuran dan bilamana
hubungan ketetanggan dapat dicaridengan polynomial time
untuk ε
>0. Akibatnya, masalah
optimisasi kombi-natorial memiliki banyak pola pendekatan
polynomial-time jika dan hanya jika
memiliki fully polynomial-time pola tambahan (augmentation).
Referensi

Komentar
Posting Komentar