Penyelesaian Masalah melalui Proses Pencarian / Searching

Nama : Safira Regia Tama Basmalah

Kelas  : 3KA10

NPM  : 16115327

Dosen: Essy Malays Sari Sakti

Metode Pencarian Terdapat banyak metode yang telah diusulkan. Semua metode yang ada dapat dibedakan ke dalam 2 jenis:

1.    Pencarian buta / tanpa informasi (blind / un-informed search)

2.    Pencarian heuristik / dengan informasi (heuristic atau informed search)

Setiap metode mempunyai karakteristik yang berbeda-beda dengan kelebihan dan kekurangan masing-masing.

1.    UNINFORMED SEARCH

Metode pencarian yang kurang informasi menawarkan berbagai teknik untuk grafik cari, masing-masing dengan kelebihan dan kekurangan tersendiri. Metode ini adalah dieksplorasi di sini dengan diskusi tentang karakteristik dan kompleksitasnya. Notasi Big-O akan digunakan untuk membandingkan algoritma. Notasi ini mendefinisikan batas atas asimtotik dari algoritma yang diberikan kedalaman (d) dari pohon dan faktor percabangan, atau rata-rata jumlah cabang (b) dari tiap simpul. Ada sejumlah kompleksitas umum yang ada algoritma pencarian Ini ditunjukkan pada Tabel 2.1. Tabel 2.1: Perintah umum fungsi pencarian.

Perintah O-Notasi

O (1) Konstan (terlepas dari jumlah nodus)

O (n) Linear (konsisten dengan jumlah node)

O (log n) Logaritma

O (n2) Kuadrat

O (cn) Geometrik

O (n!) Kombinatorial

Notasi Big-O menyediakan ukuran terburuk dari kompleksitas pencarian algoritma dan merupakan alat pembanding yang umum untuk algoritma. Kita akan membandingkan Algoritma pencarian menggunakan kompleksitas ruang (ukuran memori diperlukan selama pencarian) dan kompleksitas waktu (waktu terburuk yang dibutuhkan untuk mencari solusinya). Kami juga akan meninjau algoritma untuk kelengkapan (bisa Algoritma menemukan jalur ke simpul tujuan jika ada dalam grafik) dan optimalitasnya (temukan solusi biaya terendah yang tersedia).

A.  Kedalaman-Pertama Cari (DFS)

Algoritma Depth-First Search (DFS) adalah teknik untuk mencari a grafik
yang dimulai di root node, dan secara mendalam mencari setiap cabang ke
kedalaman terbesar sebelum mundur ke cabang yang sebelumnya belum dijelajahi.
Node ditemukan tapi belum ditinjau disimpan dalam antrian LIFO (juga dikenal
sebagai stack).

B.  Kedalaman-Terbatas Pencarian (DLS)

Depth-Limited Search (DLS) adalah modifikasi dari pencarian mendalampertama itu meminimalkan kedalaman algoritma pencarian. Selain mulai Denganakar dan simpul tujuan, kedalaman disediakan agar algoritma tidak turun di
bawah (lihat daftar 2.3). Setiap simpul di bawah kedalaman tersebut dihilangkandari pencarian. Modifikasi ini menjaga algoritma dari bersepeda tanpa batas
waktu dengan menghentikan pencarian setelah kedalaman yang telah ditentukan
sebelumnya.

C.  Iterative Deepening Search (IDS)

Iterative Deepening Search (IDS) adalah turunan dari DLS dan
menggabungkan fitur pencarian mendalam pertama dengan penelusuran luas pertama.
IDS beroperasi dengan melakukan pencarian DLS dengan kedalaman yang meningkat
sampai tujuan ditemukan.

D.  Breadth-First Search (BFS)

Dalam Breadth-First Search (BFS), kita mencari grafik dari root node di urutan jarak dari akar. Karena pencarian order paling dekat root, BFS dijamin untuk menemukan solusi terbaik (dangkal) dalam grafik non-tertimbang, dan karena itu juga lengkap. Alih-alih menggali jauh ke dalam grafik, maju lebih jauh dan lebih jauh dari akar (seperti halnya dengan DFS), BFS memeriksa setiap node yang terdekat dengan root sebelumnya turun ke tingkat berikutnya (lihat Gambar 2.14). Implementasi BFS menggunakan antrian FIFO (first-in-first-out) Berbeda dengan implementasi stack (LIFO) untuk DFS. Sebagai node baru ditemukan untuk dicari, node ini diperiksa terhadap tujuan, dan jika Tujuannya tidak ditemukan, node baru ditambahkan ke antrian. Untuk melanjutkan pencarian, simpul tertua adalah dequeued (urutan FIFO). Menggunakan perintah FIFO Untuk pencarian simpul baru, kami selalu memeriksa node tertua terlebih dahulu, sehingga menghasilkan
ulasan pertama.

E.   Bidirectional pencarian

Algoritma Search bidirectional adalah turunan dari BFS yang beroperasi
oleh melakukan dua pencarian pertama secara bersamaan, yang dimulai dari awal simpul
akar dan yang lainnya dari simpul tujuan. Saat keduanya mencari Bertemu di
tengah, jalan bisa direkonstruksi dari akar ke gawang. Pertemuan pencarian
ditentukan saat simpul umum ditemukan (sebuah simpul dikunjungi oleh kedua
pencarian, lihat Gambar 2.15). Hal ini dilakukan dengan menjaga daftar tertutup
dari node yang dikunjungi Pencarian dua arah merupakan ide yang menarik, namun
membutuhkan kita untuk mengetahui tujuan yang kami cari dalam grafik Hal ini
tidak selalu praktis, yang membatasi penerapan algoritma. Bila bisa ditentukan,
algoritma memiliki karakteristik yang bermanfaat. Kompleksitas waktu dan ruang
bidirectional Pencarian adalah O (bd / 2), karena kita hanya diminta untuk mencari
setengah dari kedalaman pohon. Karena didasarkan pada BFS, pencarian dua arah
keduanya lengkap dan optimal.

2.    INFORMED SEARCH

A.  BEST-FIRST SEARCH (BEST-FS)

Dalam pencarian Best-First, ruang pencarian dievaluasi menurut heuristik fungsi. Node yang belum dievaluasi disimpan dalam daftar OPEN dan yang itu yang telah dievaluasi disimpan dalam daftar CLOSED. Daftar OPEN adalah Diwakili sebagai antrian prioritas, sehingga nodus yang tidak dikunjungi dapat diwariskan dalam rangka fungsi evaluasi mereka (ingat antrian prioritas dari Bab 2 untuk Pencarian Biaya Seragam). Fungsi evaluasi f (n) terdiri dari dua bagian. Ini adalah fungsi heuristik (h (n)) dan taksiran biaya (g (n)), di mana

f (n) = g (n) + h (n)

Referensi
        http://www.mediafire.com/file/sq6k4qs4tsz6sx2/buku12.pdf