Algoritma Pencarian atau Searching yang biasa digunalkan pada mesin pencari atau kecerdasan buatan.ppt

Algoritma pencarian atau Searching adalah algoritma yang di gunakan pada mesin pencari atau file explorer

1. Pencarian (Searching)
M. Haviz Irfani, S.Si, MTI

2. Makna Pencarian
•Penting menyelesaikan masalah karena tiap
state menyatakan langkah2x penyelesaian.
•Penting untuk perencanaan, karena tiap state
menggambarkan posisi saat tertentu untuk
menentukan apa yg harus dilakukan.
•Penting karena bagian dari kesimpulan, state
menggambarkan hipotesis dalam sebuah
rangkaian deduktif.

3. Pendahuluan
Hal penting dalam menentukan sistem kecerdasan
buatan adalah kesuksesan dalam pencarian.
keberhasilan Pencarian melalui ruang keadaan
melibatkan, antara lain:
1.Sebuah himpunan state (simpul)
2.Operator (aturan-aturan) dan biaya yang
dikeluarkan
3.Simpul awal
4.Tes untuk mengecek simpul GOAL

4. Algoritma Dasar Pencarian
Misalkan L sebagai sebuah List (daftar)mengandung keadaan awal.
Loop
if L = empty return failure (gagal)
node select(L)
if node=goal then return node
(jalur yang dilalui dari keadaan awal)
else {bangkitkan semua successor node, dan
{gabungkan state baru yang dihasilkan dalam L}
End Loop
Note: sama halnya seperti mencari file dari sebuah storage dalam
sebuah pohon file.

5. Kriteria Pencarian
1.Completeness: Apakah metode tsb menjamin
adanya solusi jika solusinya ada?
2.Time Complexity: Berapa lama waktu untuk
menemukan solusi?
3.Space Complexity: Berapa banyak memori yang
dibutuhkan untuk menemukan solusi?
4.Optimality: Apakah metode tersebut menjamin
menemukan solusi terbaik jika terdapat
beberapa solusi yang berbeda?

6. Terminologi Pohon
A
B C D
E F
Akar Level 1
Level 2
Level 3
Daun
Simpul: A,B,C,D,E,F
Path: A,B,E atau A,B,F atau A,C atau A,D
Ruang Simpul: {(A,B),(A,C),(B,E),(B,F),(A,D)}
Orang tua
anak

7. Jenis Metode Pencarian
1.Pencarian Buta(uninformed/Blind Search)
BFS (Breadth First Search)
DFS (Depth First Search)
2. Pencarian Terbimbing (informed/Heuristic Search)
Generate and Test
Hill Climbing (Pendakian Bukit)
Best First Search (Pencarian Terbaik Pertama)

8. Breadth First Search
•Breadth First Search (BFS) merupakan
metode pencarian yang bertujuan untuk
memperluas dan memeriksa semua simpul
pada graph atau urutan kombinasi dengan
pencarian secara sistematis melalui setiap
solusi.

9. •BFS melakukan pencarian secara mendalam
pada keseluruhan graph atau urutan tanpa
memperhatikan tujuan sehingga menemukan
tujuan tersebut.
•BFS tidak menggunakan algoritma heuristik.
Breadth First Search

10. Karakteristik BFS :
- Jika ada solusi, BFS akan menemukannya.
- BFS akan menemukan solusi dengan jalur terpendek.
- BFS tidak akan terjebak dalam “looping”.
- BFS membutuhkan space untuk menyimpan node list
antrian dan space yang dibutuhkan dan mungkin space
yang dibutuhkan itu cukup besar.
- Asumsi :
1. Ada solusi dalam pohon
2. Pencarian tree adalah secara terurut.
Breadth First Search

11. •BFS melakukan searching pada semua node
yang berada pada level yang sama terlebih
dahulu, sebelum melanjutkan proses
searching pada node di level berikutnya.
Breadth First Search

12. Breadth First Search
Keterangan :
1.Pada metode breadth-first search, semua node pada level n akan
dikunjungi terlebih dahulu sebelum mengunjungi node-node pada level
n+1.
2.Pencarian dimulai dari node akar terus ke level ke-1 dari kiri ke
kanan, kemudian berpindah ke level berikutnya, demikian pula dari kiri ke
kanan hingga ditemukannya solusi.

13. Keuntungan BFS :
•Tidak akan menemui jalan buntu
•Jika ada satu solusi, maka breadth-first search akan
menemukannya. dan, jika ada lebih dari satu solusi,
maka solusi minimum akan ditemukan.
Kelemahan BFS:
•Membutuhkan memori yang cukup banyak, karena
menyimpan semua node dalam satu pohon
•Membutuhkan waktu yang cukup lama, karena akan
menguji n level untuk mendapatkan solusi pada level
yang ke-(n+1).
Breadth First Search

14. •Depth-first search (DFS) adalah proses
searching sistematis buta yang melakukan
ekspansi sebuah path (jalur) menuju
penyelesaian masalah sebelum melakukan
ekplorasi terhadap path yang lain.
•Proses searching mengikuti sebuah path
tunggal sampai menemukan goal atau dead
end.
Depth First Search

15. •Apabila proses searching menemukan dead-
end, DFS akan melakukan penelusuran balik ke
node terakhir untuk melihat apakah node
tersebut memiliki path cabang yang belum
dieksplorasi.
Depth First Search

16. Depth First Search

17. Depth First Search

18. Kelebihan DFS :
•Pemakaian memori hanya sedikit, berbeda jauh dengan BFS
yang harus menyimpan semua node yang pernah dibangkitkan.
•Jika solusi yang dicari berada pada level yang dalam dan paling
kiri, maka DFS akan menemukannya secara cepat.
Kelemahan DFS :
•Jika pohon yang dibangkitkan mempunyai level yang dalam
(tak terhingga), maka tidak ada jaminan untuk menemukan
solusi (Tidak Complete).
•Jika terdapat lebih dari satu solusi yang sama tetapi berada
pada level yang berbeda, maka pada DFS tidak ada jaminan
untuk menemukan solusi yang paling baik (Tidak Optimal).
Depth First Search

19. Depth First Search

20. SELESAI