Blind (Uninformed) Search

-

 

Blind (Uninformed) Search

Secara garis besar tebagi menjadi:

  • Breadth-First Search (BFS)
  • Depth-First Search (DFS)
  • Depth-Limited Search (DLS)
  • Iterative-Deepening Search (IDS)
  • Uniform Cost Search (UCS)
  • Bi-Directional Search (BDS)

Ruang Pencarian

> Perhitungan ruang pencarian:

- Faktor percabangan (b)

- Kedalaman solusi (d)

> Contoh

- 8-Puzzle → b 2.13

- Kubus Rubik → b 13,34

- Rata-rata Permainan Catur b = 35

Breadth-First Search (BFS) Algorithm

> Menjelajahi node tetangga terlebih dahulu, sebelum pindah ke tetangga tingkat berikutnya. 

> first-in-first-out

> Ingat semua node yang dikunjungi sebelumnya (status)

Kinerja BFS

> Selesai

- pada akhirnya akan menemukan status kambing

> Optimal

> Kompleksitas Waktu = 0 (bd + 1)

> Kompleksitas Ruang = 0 (bd+1)

 Algoritma DFS

> Perluas node terdalam yang tidak diperluas

> terakhir-masuk-pertama-keluar

> Hanya ingat jalur yang dikunjungi saat ini

> Penundaan memeriksa apakah node telah ditemukan sampai node muncul dari tumpukan daripada memeriksa sebelum menambahkan node.

Performa DFS

> Tidak Lengkap

- mungkin tersesat di bagian grafik yang tidak memiliki status tujuan dan tidak pernah kembali

> Tidak Optimal

-Mungkin menemukan tujuan yang tidak optimal terlebih dahulu

> Kompleksitas Waktu = O (bm)

> Kompleksitas Ruang = 0 (bm) 

- Dengan m adalah pencarian kedalaman maksimum

Algoritma DLS

> DFS dengan area pencarian kedalaman terbatas

> Memperbaiki masalah pohon tak terbatas untuk DFS

> Jelajahi semua node anak - baik dicentang atau tidak

Kinerja DLS

> Selesai if   d

> Tidak Optimal

> Kompleksitas Waktu = 0 (b )

> Kompleksitas Ruang = 0 (bl)

- Dengan  adalah pencarian kedalaman maksimum

Iterative-Deepening Search (IDS)

> BFS → lengkap dan optimal

> DFS → kompleksitas ruang rendah

> DLS → pertanyaan "seberapa dalam?" 

> IDS menggabungkan BFS dengan DFS / DLS

> IDS lengkap, optimal, kompleksitas ruang rendah

> Kelemahan: Kompleksitas Waktu meningkat

IDS Algorithm

> Memanggil berulang kali algoritma DLS dari depth = 0 hingga menemukan tujuan

Kinerja IDS

> Selesai

> Optimal

> Kompleksitas Waktu = 0 (bd)

> Kompleksitas Ruang = 0 (bd)

Uniform Cost Search (UCS)

> BFS menggunakan urutan level dari yang terendah hingga tertinggi. 

> UCS menggunakan urutan biaya dari yang terkecil sampai yang terbesar. 

> UCS mencari solusi dengan biaya total terendah yang dihitung berdasarkan biaya node asal ke node tujuan. 

> G (n) = biaya node asal ke node n.

Performa UCS

> Lengkap

> Optimal

> Kompleksitas Waktu = 0 (bd)

> Kompleksitas Ruang = 0 (bd)

Pencarian dua arah (BDS)

> Pencarian maju (dari awal awal ke tujuan) dan pencarian mundur (dari tujuan ke awal). 

> Ketika dua pencarian mencapai node yang sama, maka solusinya telah ditemukan. 

> Gabungkan dua jalur.

Performa BDS

> Lengkap

> Optimal

> Kompleksitas Waktu = 0 (b d/2)

> Kompleksitas Ruang = 0 (b d/2)

Masalah dengan BDS

> Pencarian dua arah kelihatannya menarik karena kinerjanya 0 (bd/2), tetapi tidak semudah itu, terutama pada bagian implementasi. 

- Require Reversal Operator

> Tidaklah mudah untuk merumuskan masalah sedemikian rupa sehingga setiap state dapat dibalik, yaitu berpindah dari head ke tail seperti berpindah dari tail ke head.

 - Tidak semua operator bisa dibalik

Masalah dengan BDS

> Harus selalu menguji apakah node yang baru dihasilkan telah dimunculkan dengan mencari di arah yang berlawanan

> Rentan jika ada beberapa node tujuan yang berbeda

 

 

 

 

 

 

Comments

Post a Comment

Popular posts from this blog

Cara menambah lokasi baru di google maps

-
Image
Nama : Arsyah kumalasari NIM    : 18.01.013.023 Jangan lupa kunjungin web UTS : https://uts.ac.id/ Dan juga link facebook NUsa baca https://www.facebook.com/nusa.baca.18 Ada yang tau gimana cara tambah lokasi baru di google maps??  Kalo belum tau mari baca langkahnya di bawah ini... Disini saya menambahkan lokasi balai desa dusun Sela desa Batu Tering dan warung makan bu Hatma 1. Buka Google Maps dan jangan lupa mengaktifkan lokasi 2. Ketuk tombol menu pada pojok kiri atas 3. Gulir ke bawah dan cari tambahkan tempat, jika sudah ketemu pilih opsi tersebut 4. Isi keterangan yang sesuai minimal pada Nama, Alamat, dan kategori A. Balai dusun Sela desa Batu Tering Link: Balai Dusun Sela Desa Batu Tering Lito, Moyohulu, Kabupaten Sumbawa, Nusa Tenggara Bar. 84371 https://maps.google.com/?cid=16661604564718697785 B. Rumah makan hatma batu tering Link:  Warung makan Hatma Lito, Moyohulu, Kabupaten Sumbawa, Nusa Tenggara Bar. 84371 https://maps.google.com/?cid=2901808897...
Read more

Pertemuan IV, V VI VII

-
 Resume mechine learning Pertemuan IV, V VI VII  RESUME Mengenal Boolean value, jenis-jenis operator dan kondisional Cara mengoperasikan isi dari variable misalkan dengan menjumlahkan kedua nilai atau mengurangi kedua nilai,bisa juga membandingkan besaran kedua nilai mana yang lebih besar contohnya nilai 4 dan 2 itu semua bisa dilakukan dengan menggunakan yang namanya operator. Operator sendiri merupakan sebuah symbol atau istilah yang digunakan untuk memanipulasi nilai misalnya 4+2 operatornya yaitu symbol + sedangkan nilai yang dioperasikan disebut operan,operannya itu angka 4 dan 2,operan bukan hanya tipe data integer. Jika nilai-nilai diwakili oleh variebel maka teknis variebel bisa disebut operan . Jenis-jenis operator ada 7: 1. Operator aritmatika 2. Operator perbandingan atau relasi 3. Operator penugasan 4. Operator logika 5. Operator bitwise 6. Operator keanggotaan 7. Operator indentifikasi Operator aritmatika mencakup penjumlahan,pengurangan,pembagian,perkalian, dll. ...
Read more

BAB 3

-
PIRANTI MASUKAN 3.1  Jenis Peranti Masukan 3.2  Peranti Pengetikan 3.3  Peranti Petunjuk (Pointing Device) 3.4  Pengambil Gambar Terformat 3.5  Pengambil Gambar Tidak Terformat  3.6  Suara 3.7  Video 3.8  Gerakan 3.9  Sensor 3.10 Radio Frequency Identification Device (RFID) 3.11 Pembaca Kartu Magnetik 3.12 Pembaca Kartu Cerdas  3.13 Pembaca Kode QR Jenis Peranti Masukan (Input Device)  Merupakan perangkat keras komputer yang memungkinkan pemasukan data ke dalam sistem komputer.   Dalam hal ini dapat berupa huruf, angka, gambar, suara, audio-video dan gerakan.  1. Keyboard    Piranti pemasukan data yang dapat mengubah huruf,angka ataupun kode lain menjadi isyarat yang dapat diproses oleh komputer.  Merupakan piranti masukan yang tidak terlalu banyak mengalami perubahan sejak pengenalannya yang pertama.  Terdiri atas tombol pengetikan, angka, fungsi dan tombol kontrol. 2.  ATM (Aut...
Read more