"Best First Search (BFS) adalah salah satu cara pencarian /search yang digunakan didalam membuat program kecerdasan buatan (Artificial Intelligence/AI).
Sebelum kita membahas tentang BFS, alangkah baiknya jika kita mengetahui Mengetahui metode pencarian yang lainnya."
Metode Pencarian:
Dibagi menjadi 3 bagian..
*Pencarian Buta:
Merupakan metode sederhana yang berusaha mencari kemungkinan penyelesaian, tanpa memperhatikan efisiensi dari pencarian. Diantaranya:
- -Breadth First Search
- -Depth First Search
- -Hill Climbing Search
- -Beam Search
- -Best First Search
*Penyelesaian Optimal:
Merupakan metode yang lebih kompleks yang mencari jarak terpendek dalam suatu pencarian
- -British Museum
- -Branch & Bound
- -Dynamic Programming
- -Algoritma A*
*Permainan:
Metode yang digunakan saat berhadapan dengan musuh (contohnya pada game single player yang mengharuskan player bermain melawan komputer)
- -Minimax
- -Alpha-beta Prunning
METODE BFS:
BFS merupakan metode pencarian yang menggabungkan ciri khas dari teknik Depth First Search dan Breadth First Search. Tujuannya adalah untuk menelusuri satu jalur, namun dapat berpindah ketika jalur lain terlihat lebih baik dari jalur yang sedang ditelusuri. Untuk itu dipasang skala prioritas pada setiap state saat dilewati, dengan fungsi "Heuristic".
Pencarian akan pindah ke level dibawahnya, jika didalam satu level tidak ada yang memiliki skala prioritas yang tinggi.
Untuk mengimplementasikan metode ini, butuh 2 antrian yang berisi node, yaitu:
1) Open: berisi simpul yang berpeluang menjadi simpul terbaik
2) Closed: berisi simpul yang sudah tidak mungkin terpilih sebagai simpul yang akan dilewati.
terdapat 2 metode pencarian yang menggunakan fungsi Heuristic.
1) Greedy Best First Search (Update Soon)
2) Algoritma A* (Update Soon)
1 komentar:
Mong-senpaaai :v