KECERDASAN BUATAN RANGKUMAN 4,5,6,7

 

Blind (Uninformed) Search

Secara garis besartebagimenjadi:

  • 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

>Perhitunganruangpencarian:

- Faktorpercabangan (b)

- Kedalamansolusi (d)

>Contoh

- 8-Puzzle → b 2.13

- Kubus Rubik → b 13,34

- Rata-rata PermainanCatur b = 35

Breadth-First Search (BFS) Algorithm

>Menjelajahi node tetanggaterlebihdahulu, sebelumpindahketetanggatingkatberikutnya. 

> first-in-first-out

>Ingatsemua node yang dikunjungisebelumnya (status)

Kinerja BFS

>Selesai

- pada akhirnyaakanmenemukan status kambing

> Optimal

>Kompleksitas Waktu = 0 (bd + 1)

>Kompleksitas Ruang = 0 (bd+1)

Algoritma DFS

>Perluas node terdalam yang tidakdiperluas

>terakhir-masuk-pertama-keluar

>Hanyaingatjalur yang dikunjungisaatini

>Penundaanmemeriksaapakah node telahditemukansampai node munculdaritumpukandaripadamemeriksasebelummenambahkan node.

Performa DFS

>TidakLengkap

- mungkintersesat di bagiangrafik yang tidakmemiliki status tujuan dan tidakpernahkembali

>Tidak Optimal

-Mungkinmenemukantujuan yang tidak optimal terlebihdahulu

>Kompleksitas Waktu = O (bm)

>Kompleksitas Ruang = 0 (bm) 

- Dengan m adalahpencariankedalamanmaksimum

Algoritma DLS

> DFS dengan area pencariankedalamanterbatas

>Memperbaikimasalahpohontakterbatasuntuk DFS

>Jelajahisemua node anak - baikdicentangatautidak

Kinerja DLS

>Selesai if d

>Tidak Optimal

>Kompleksitas Waktu = 0 (b)

>Kompleksitas Ruang = 0 (bl)

- Denganadalahpencariankedalamanmaksimum

Iterative-Deepening Search (IDS)

> BFS → lengkap dan optimal

> DFS → kompleksitasruangrendah

> DLS → pertanyaan "seberapadalam?" 

> IDS menggabungkan BFS dengan DFS / DLS

> IDS lengkap, optimal, kompleksitasruangrendah

>Kelemahan: Kompleksitas Waktu meningkat

IDS Algorithm

>Memanggilberulang kali algoritma DLS daridepth = 0 hinggamenemukantujuan

Kinerja IDS

>Selesai

> Optimal

>Kompleksitas Waktu = 0 (bd)

>Kompleksitas Ruang = 0 (bd)

Uniform Cost Search (UCS)

> BFS menggunakanurutan level dari yang terendahhinggatertinggi. 

> UCS menggunakanurutanbiayadari yang terkecilsampai yang terbesar. 

> UCS mencarisolusidenganbiaya total terendah yang dihitungberdasarkanbiaya node asalke node tujuan. 

> G (n) = biaya node asalke node n.

Performa UCS

>Lengkap

> Optimal

>Kompleksitas Waktu = 0 (bd)

>Kompleksitas Ruang = 0 (bd)

Pencarianduaarah (BDS)

>Pencarianmaju (dariawalawalketujuan) dan pencarianmundur (daritujuankeawal). 

> Ketika duapencarianmencapai node yang sama, makasolusinyatelahditemukan. 

>Gabungkanduajalur.

Performa BDS

>Lengkap

> Optimal

>Kompleksitas Waktu = 0 (bd/2)

>Kompleksitas Ruang = 0 (bd/2)

Masalahdengan BDS

>Pencarianduaarahkelihatannyamenarikkarenakinerjanya0 (bd/2), tetapitidaksemudahitu, terutama pada bagianimplementasi. 

- Require Reversal Operator

>Tidaklahmudahuntukmerumuskanmasalahsedemikianrupasehinggasetiap state dapatdibalik, yaituberpindahdari head ke tail sepertiberpindahdari tail ke head.

 - Tidaksemua operator bisadibalik

Masalahdengan BDS

> Harus selalumengujiapakah node yang barudihasilkantelahdimunculkandenganmencari di arah yang berlawanan

>Rentanjikaadabeberapa node tujuan yang berbeda

 

 

 

 

 

 

Komentar

Posting Komentar

Postingan populer dari blog ini

BAB 3 PERANTI MASUKAN (Input Device)

1. 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.  Ragam peranti masukan adalah seperti terlihat di bawah ini :  - Pengetikan :     *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.        *ATM (Automated Teller Machine) :      Disebut juga Anjungan Tunai Mandiri (dalam Perbankan) ATM bekerja sebagai piranti input output sekaligus. Sebagai piranti masukan, ATM memungkinkan pemakai memasukkan nomor  PIN, angka uang, dll Sebag...
Baca selengkapnya

Lirik lagu dan kord gitar pernah singgah-Akbar algifari

Ciptaan :Akbar algifari Vocal     :Akbar algifari  G C Kau pernah singgah D G Didalam hatiku Em Am Menemani hari D G Yang sepi disini G C Inginku coba D G Tuk pergi lagi Em Am Meninggalkan semua D G Sepi yang ku alami G Bm Berat sudah cinta ku lalui C D G saat bersama bayanganmu G Bm inginku coba tuk pergi lagi C D meninggalkan semua cinta ini C D G Em Namun berat sudah cinta ini Am D G Kuinginkan engkau tau G C Kau pernah singgah D G Didalam hatiku Em Am Menemani hari D G Yang sepi disini G C Inginku coba D G Tuk pergi lagi Em C...
Baca selengkapnya

KECERDASAN BUATAN 8,9,10,11

Gambar
  Heuristic (informed) search Secara garis besar terbagi menjadi: Heuristic Function Hill Climbing Simulated Annealing Best-First Search A* Search   Heuristik > Heuriskein Untuk menemukan, menemukan, mencari Proses memperoleh pengetahuan atau hasil yang diinginkan dengan tebakan cerdas daripada dengan mengikuti beberapa rumus yang telah ditetapkan sebelumnya. Fungsi yang memberikan nilai perkiraan (estimasi biaya) dari suatu solusi Heuristik dapat dibandingkan dengan algoritma 1. Fungsi Heuristik > Fungsi heuristik dapat diterima jika perkiraan biaya yang dihasilkan tidak melebihi biaya sebenarnya > Fungsi heuristik yang terlalu tinggi dapat membuat proses pencarian hilang atau mencapai hasil yang tidak optimal.   > Fungsi heuristik yang baik adalah fungsi yang memberikan perkiraan biaya yang mendekati biaya sebenarnya.   > Semakin mendekati biaya sebenarnya, semakin baik fungsi heuristiknya...
Baca selengkapnya