Masalah,Ruang Keadaan,Pencarian

Masalah:

Untuk membangun sistem yang mampu menyelesaikan masalah, perlu dipertimbangkan 4 hal:
– Mendefinisikan masalah dengan tepat

  • Spesifikasi yang tepat mengenai keadaan awal
  • Solusi yang diharapkan

– Menganalisis masalah serta mencari beberapa
teknik penyelesaian masalah yang sesuai
– Merepresentasikan pengetahuan yang perlu untuk
menyelesaikan masalah
– Memilih teknik penyelesaian masalah yang terbaik

Masalah Sebagai Ruang Keadaan

  • Misalkan permasalahan yang dihadapi adalah Permainan Catur
  • Maka harus ditentukan

– Posisi awal pada papan catur
– Aturan-aturan untuk melakukan gerakan secara legal
– Tujuan (goal)

Ruang Keadaan (State Space)

  • Suatu ruang yang berisi semua keadaan yang mungkin
  • Sehingga secara umum, untuk mendeskripsikan masalah dengan baik, harus:

– Mendefinisikan suatu ruang keadaan
– Menetapkan satu atau lebih keadaan awal
– Menetapkan satu atau lebih tujuan
– Menetapkan kupulan aturan

Ada beberapa cara untuk merepresentasikan Ruang KeadaanGraph Keadaan

  • Terdiri dari node-node yang menunjukkan keadaan yaitu keadaan awal dan keadaan baru yang akan dicapai dengan menggunakan operator
  • Node-node saling dihubungkan dengan menggunakan arc (busur) yang diberi panah untuk menunjukkan arah

Pohon Pelacakan

  • Struktur pohon digunakan untuk menggambarkan keadaan secara hirarkis
  • Terdiri dari beberapa node, level 0 disebut akar atau keadaan awal
  • Node akar : menunjukkan keadaan awal & memiliki beberapa percabangan yang terdiri atas beberapa node yg disebut ’anak’ .
  • Node-node yg tidak memiliki anak disebut ’daun’menunjukkan akhir dari suatu pencarian, dapat berupa tujuan yang diharapkan (goal) atau jalan buntu (deadend).

Penyelesaian masalah secara umum

  • Mendefinisikan suatu ruang keadaan;
  • Menetapkan satu atau lebih keadaan awal;
  • Menetapkan satu atau lebih tujuan;
  • Menetapkan kumpulan aturan.

Metode Pencarian dan Pelacakan

  • 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
  • Untuk mengukur perfomansi metode pencarian, terdapat empat kriteria yang dapat digunakan :
    – 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?
  • Dua teknik pencarian dan pelacakan
    – Pencarian buta (blind search)
    Pencarian melebar pertama (Breadth – First Search)
    Pencarian mendalam pertama (Depth – First Search)
    – Pencarian terbimbing (heuristic search)
    Pendakian Bukit (Hill Climbing)
    Pencarian Terbaik Pertama (Best First Search)

Pencarian Melebar Pertama (Breadth-First Search)

  • Semua node pada level n akan dikunjungi terlebih dahulu sebelum level n+1
  • Mulai dari akar terus ke level 1 dari kiri ke kanan
  • Kemudian ke level selanjutnya hingga solusi ditemukan
  • Keuntungan :
    – Tidak akan menemui jalan buntu
    – Menjamin ditemukannya solusi (jika solusinya memang ada) dan solusi yang ditemukan pasti yang paling baik
    – Jika ada satu solusi maka bread-first search akan menemukannya
  • Kelemahannya
    – Membutuhkan memori yang cukup banyak
    – Membutuhkan waktu yang cukup lama

Pencarian mendalam pertama (Depth-First Search)

  • Proses pencarian dilakukan pada semua anaknya sebelum dilakukan pencarian ke node-node yang selevel
  • Keuntungan :

– Memori yang relatif kecil

– Secara kebetulan, akan menemukan solusi tanpa harus menguji lebih banyak lagi

Pencarian buta (blind search)

  • Kekurangan

– Memungkinkan tidak ditemukannya tujuan yang diharapkan
– Hanya akan mendapatkan 1 solusi pada setiap pencarian

2 thoughts on “Masalah,Ruang Keadaan,Pencarian”

  1. Pingback: Web Science 4 | My Blog
  2. Trackback: Web Science 4 | My Blog
  3. Pingback: zakyafdika | Web Science 4
  4. Trackback: zakyafdika | Web Science 4

Leave a Reply

Your email address will not be published. Required fields are marked *