SEARCH 2


Kali ini saya akan  menulis rangkuman materi pertemuan 5 tentang Search lanjutan yang terdiri dari: 

1. Masalah dan ruang masalah

2. Cara Mempresentasikan masalah. 

3. Konsep Pencarian

4. Metode Pencarian Heuristik :

a. Generate And Test (Pembangkit dan Pengujian) 

b. Hill Climbing (Pendakian Bukit)

 c. Best-First-Search


Masalah dan ruang masalah

Membangun sistem dengan menyelesaikan masalah menggunakan kecerdasan buatan:

1. Mendefinisikan masalah dengan tepat.

-Pendefinisian ini mencakup spesifikasi yang tepat mengenai keadaan awal dan solusi yang  diharapkan.

2. Menganalisis masalah tersebut serta mencari beberapa teknik penyelesaian masalah yang sesuai.

3. Merepresentasikan pengetahuan yang perlu untuk menyelesaikan masalah tersebut.

4. Memilih teknik penyelesaian masalah yang terbaik.

 

Cara mendefinisikan suatu masalah :

  • Mendefinisikan masalah dapat dilakukan dengan cara :
  • Mendefinisikan suatu ruang keadaan (state space)
  • Menetapkan satu atau lebih keadaan awal (initial state)
  • Menetapkan satu atau lebih tujuan (goal state)
  • Menetapkan kumpulan aturan



Cara Merepresentasikan Ruang Masalah

·      1. Graph Keadaan


Node M : awal, node T : tujuan. Ada 4 lintasan dari M ke T :

M-A-B-C-E-T

M-A-B-C-E-H-T

M-D-C-E-T

M-D-C-E-H-T

Lintasan buntu atau lintasan yang tidak sampai ke tujuan :

M-A-B-C-E-F-G

M-A-B-C-E-I-J

M-D-C-E-F-G

M-D-C-E-I-J

M-D-I-J 

·      2.   Pohon Pelacakan


·     3. Pohon AND/OR

 




Konsep Pencarian

  • Hal penting dalam menentukan keberhasilan sistem cerdas adalah kesuksesan dalam pencarian.
  • Pencarian = suatu proses mencari solusi dari suatu permasalahan melalui sekumpulan kemungkinan ruang keadaan (state space).
  • Ruang keadaan = merupakan suatu ruang yang berisi semua keadaan yang mungkin.

Kriteria yang digunakan untuk mengukur performansi metode pencarian adalah :

  • Completeness : apakah metode tersebut menjamin penemuan solusi jika solusinya memang ada?
  • Time complexity : berapa lama waktu yang diperlukan?
  • Space complexity : berapa banyak memori yang diperlukan?
  • Optimality : apakah metode tersebut menjamin menemukan solusi yang terbaik jika terdapat beberapa solusi berbeda?

 Metode Pencarian Heuristik

Dalam pencarian  buta tidak dapat sering diterapkan dengan baik, hal  ini dikarenakan dalam waktu aksesnya cukup lama dan besarnya memori yang dipakai. Kelemahan ini dapat diatasi jika memiliki informasi tambahan dari domain yang bersangkutan. Ada 4 metode dalam pencarian heuristik, antara lain:

  1. Pembangkit dan penggujian (Generate and Test); Metode  ini merupakan  penggabungan  antara  depth-first search dengan pelacakan mundur (backtracking), yaitu bergerak ke belakang menuju suatu keadaan awal. Nilai Pengujian berupa jawaban baik berupa ‘ya’ atau ‘tidak’.
  2. Pendakian bukit (Hill Climbing) ; Pada metode ini hampir sama seperti metode pembangkitan dan pengujian, namun proses pengujian ini dilakukan dengan  fungsi heuristik. Pembangkitan kondisi  yang  berikutnya sangat  tergantung  pada  feedback dari  prosedur pengetesan. Tes  fungsi heuristik  akan menunjukan seberapa baiknya nilai perkiraan yang diambil terhadap kondisi-kondisi lainnya yang mungkin terjadi.
  3. Pencarian terbaik pertama (Best First Search) ; metode best-first search merupakan metode yang  mengambil kelebihan dari kedua metode kombinasi dari metode depth-first search dengan metode breadth-first search. Apabila ada pencarian dengan metode hill climbing tidak dapat untuk balik ke node pada level yang lebih rendah walaupun node pada level yang lebih rendah tersebut memiliki nilai heuristik yang lebih baik, lain halnya dengan metode best-first search ini. Pada metode best-first search, pencarian dapat mengunjungi node yang ada dilevel yang lebih rendah, jika node pada level yang lebih tinggi memiliki nilai heuristik yang lebih buruk.



 

Komentar

Posting Komentar

Postingan populer dari blog ini

Algorithma Klipping (Clipping)

Gambar
Algorithma Clipping Definisi Dalam kehidupan sehari-hari saat kita ingin menggambar sesuatu pada sebuah bidang, tentunya kita tidak akan bisa menggambar melebihi bidang tersebut. Dengan kata lain suatu bidang gambar pasti memiliki batas wilayah maksimum. Seperti halnya komputer, untuk melakukan proses penggambaran suatu objek di monitor, komputer tidak akan bisa menampilkan gambar melebihi batas maksisum yang telah ditentukan. Untuk dapat melakukan hal tersebut, maka digunakanlah proses clipping, Clipping berasal dari kata clip, yang secara umum memiliki arti memotong. Dalam ilmu grafika komputer, clipping merupakan proses pemotongan objek sehingga hanya bagian objek yang berada di dalam area tampil(viewport) yang dapat dilihat oleh user, sedangkan bagian objek yang berada di luar area tampil akan disembunyikan. Hal tersebut dilakukan agar proses perhitungan koordinat pixel pada layar tidak terlalu rumit. Tetapi sebelum melakukan proses clipping terlebih dahulu harus ditentukan bentuk ...
Baca selengkapnya

OpenGL & GLUT

Gambar
Pengertian OpenGL OpenGL (Open Graphics Library) adalah suatu spefikasi grafik yang low-level yang menyediakan fungsi untuk mempermudah pekerjaan atau untuk keperluan – keperluan pemrograman grafis (Graphics Programming / GP), termasuk grafik primitif (titik, garis, dan lingkaran). OpenGL(Open Graphic Library) adalah sebuah library terdiri dari berbagai macam fungsi dan biasanya digunakan untuk menggambar sebuah objek 2D ata 3D. OpenGL bersifat Open-Source, multi-platform dan multi-language. OpenGL juga merupakan suatu antarmuka pemrograman aplikasi (application programming interface (API) yang tidak tergantung pada piranti dan platform yang digunakan, sehingga OpenGL dapat berjalan pada sistem operasi Windows, UNIX,SGI, Linux, frreBSD dan sistem operasi lainnya. OpenGL pada awalnya didesain untuk digunakan pada bahasa pemrograman C/C++, namun dalam perkembangannya OpenGL dapat juga digunakan dalam bahasa pemrograman yang lain seperti Java, Tcl, Ada, Visual Basic, Delphi, maupun Fo...
Baca selengkapnya

SYNTHETIC CAMERA

Gambar
  SYNTHETIC CAMERA SYNTHETIC CAMERA 1 Proyeksi perspektif dengan mata berada di sumbu proyeksi sangat membatasi sudut pandang. 2 Memutar objek agar memperoleh sudut pandang yang berbeda sangat tidak efisien. 3 Pendekatan lain adalah dengan menggunakan synthetic camera. CARA KERJA CAMERA cahaya Citra objek dibawa cahaya menuju lensa sehingga di lensa muncul bayangan objek, oleh cahaya bayangan tersebut kemudian diteruskan ke film (plastik yang dilapisi dengan bahan kimia peka cahaya) sehingga menimbulkan reaksi kimia yang membentuk citra objek SYNTHETIC CAMERA - Synthetic camera adalah metoda memposisikan ‘camera’ untuk melihat benda. - Membutuhkan tiga komponen :  - Bidang proyeks i   - Sistem koordinat viewer - mata. - Cara kerja : objek dipindahkan ke koordinat viewer dan kemudian 'bayangan' objek diproyeksikan perspektif. - Objek perlu dipindahkan ke koordinat viewer agar posisi objek sesuai dengan (align) arah mata. VIEWING COORDINATE - Viewing co...
Baca selengkapnya