Teknik Pemecahan Masalah AI

Penyelesaian Masalah berdasarkan teknik AI

Empat hal untuk membangun sistem atau memecahkan masalah tertentu :

–        Definisikan masalah dengan jelas

–        Analisis masalah

–        Kumpulkan dan representasikan knowledge

–        Pilih teknik pemecah masalah terbaik dan gunakan untuk masalah tertentu

Pendefinisian Masalah Sebagai Pencarian Ruang Keadaan atau “State Space Search” (SSS)

Masalah utama dalam membangun sistem berbasis AI adalah bagaimana mengkonversikan situasi yang diberikan ke dalam situasi lain yang diinginkan menggunakan sekumpulan operasi tertentu.

• Graph

• Pohon Pelacakan

• Pohon AND/ OR
  
  
  Graph
  Terdiri dari node (titik) yang menunjukkan keadaan, keadaan awal dan keadaan baru untuk mencapai keadaan yang diinginkan. Node-node tersebut terhubung dengan menggunakan busur yang diberi panah untuk menunjukkan arah dari suatu keadaan ke keadaan berikutnya.
  
  
  Pohon Pelacakan
  Untuk menghindari adanya kemungkinan proses pelacakan suatu node secara berulang maka digunakan struktur pohon.
  
  
  Pohon AND/ OR
  Untuk menyelesaikan suatu masalah menggunakan 3 kemungkinan, misalnya a,b,c, yang artinya masalah bisa diselesaikan jika salah satu dari kemungkinan tersebut tidak terpecahkan.
  
  
  Mendefinisikan Masalah sebagai “State Space Search” (SSS)
  Misalnya permainan catur , maka SSS nya adalah :
  –        Menspesifikasikan posisi awal dari papan catur
  –        Peraturan (rules) yang mendefinisikan langkah-langkah yang legal
  –        Posisi papan yang merepresentasikan pemenang dari satu sisi atau sisi lainnya.
  –        Tujuan (Goal) dari permainan adalah : memenangkan permainan.
   
  Contoh Kasus:
  A Water Jug Problem
  Anda diberi dua buah gelas, yang satu ukuran 4 galon dan yang lain 3 galon. Kedua gelas tidak memiliki skala ukuran. Terdapat pompa yang dapat digunakan untuk mengisi gelas dengan air. Bagaimana anda mendapatkan tepat 2 galon air di dalam gelas 4 ukuran galon?
  
  
  Penyelesaian :
  • Ruang masalah untuk masalah di atas dapat digambarkan sebagai himpunan pasangan bilangan bulat (x,y) yang terurut, sedemikian hingga
  –        x = 0, 1, 2, 3, atau 4 dan
  –        y = 0, 1, 2, atau 3;
  x menyatakan jumlah air dalam gelas ukuran 4 galon, dan
  y menyatakan jumlah air dalam gelas ukuran 3 galon.
  •  Keadaan mula-mula adalah (0,0).
  • State tujuan adalah (2,n) untuk setiap nilai n.
  
  
  Sistem Produksi
  Sistem produksi terdiri dari:
  •  Himpunan aturan, masing-masing terdiri dari sisi kiri (pola) yang menentukan kemampuan aplikasi dari aturan tersebut dan sisi kanan yang menggambarkan operasi yang dilalukan jika aturan dilaksanakan.
  
  
  • Satu atau lebih pengetahuan atau basis data yang berisi informasi apapun untuk tugas tertentu. Beberapa bagian basis data bisa permanen, dan bagian yang lain bisa hanya merupakan solusi untuk masalah saat ini. Informasi dalam basis data ini disusun secara tepat.
  • Strategi kontrol yang menspesifikasikan urutan dimana aturan akan dibandingkan dengan basis data dan menspesifikasikan cara pemecahan masalah yang timbul ketika beberapa aturan sesuai sekaligus pada waktu yang sama.
  •  A rule applier (pengaplikasi aturan
  
  
  
  
   Aturan produksi  
• Operator-operator (aturan produksi) yang digunakan untuk memecahkan masalah tersebut diatas terlihat seperti pada tabel berikut:       

  

Tabel Aturan Produksi Untuk A Water Jug Problem

Solusi Untuk A Water Jug Problem

Strategi Kontrol

Syarat-syarat strategi kontrol:

• cause motion. Perhatikan kembali water jug problem. Jika kita mengimplementasikan strategi kontrol sederhana dengan selalu memilih aturan pertama pada daftar 12 aturan yang telah dibuat, maka kita tidak akan pernah memecahkan masalah. Strategi kontrol yang tidak menyebabkan motion tidak akan pernah mencapai solusi.

• Systematic. Strategi kontrol sederhana yang lain untuk water jug problem: pada setiap siklus, pilih secara random aturan-aturan yang dapat diaplikasikan. Strategi ini lebih baik dari yang pertama, karena menyebabkan motion. Pada akhirnya strategi tersebut akan mencapai solusi. Tetapi mungkin kita akan mengunjungi beberapa state yang sama selama proses tersebut dan mungkin menggunakan lebih banyak langkah dari jumlah langkah yang diperlukan. Hal ini disebabkan strategi kontrol tersebut tidak sistematik. Beberapa strategi kontrol yang sistematik telah diusulkan, yang biasa disebut sebagai metoda-metoda dalam teknik searching. Di bab ini, akan dibahas enam metoda, yaitu Breadth First Search, Uniform Cost Search, Depth First Search, Depth-Limited Search, Iterative-Deepening Depth-First Search, dan Bi-directional search. Masing-masing metoda tersebut mempunyai karakteristik yang berbeda.

Strategi Pencarian

 Terdapat empat kriteria dalam strategi pencarian, yaitu:

• Completeness: Apakah strategi tersebut menjamin penemuan solusi jika solusinya memang ada?

• Time complexity: Berapa lama waktu yang diperlukan?

• Space complexity: Berapa banyak memori yang diperlukan?

• Optimality: Apakah strategi tersebut menemukan solusi yang paling baik jika terdapat beberapa solusi berbeda pada permasalahan yang ada?