BAB 2. PENYELESAIAN MASALAH

 PENGANTAR TEKNOLOGI SISTEM CERDAS

 

 

  DISUSUN OLEH

CLAUDYA TUPAMAHU
11115533

3KA12

  2.1 Agen Pemecah Permasalahan

        •Metode searching adalah metode pemecahan masalah dengan menggunakan aturan yang dikombinasikan dengan strategi kontrol yang bekerja dalam ruang masalah dan berpindah dari kondisi awal (initial state) ke kondisi tujuan (goal state) dalam sebuah alur (path).

        •Ruang masalah umumnya dibentuk dalam bentuk tree atau graf untuk memudahkan pemecahan masalah.

          Proses pencarian mengeksplorasi semua kemungkinan path dari initial state ke goal state

        •Proses pencarian mengeksplorasi semua kemungkinan path dari initial state ke goal state.

        

           Agen Pemecah Permasalahan

         Terbagi menjadi 3 ,antara lain…

                  i. Goal-Based Agent

                    Mempertimbangkan action-action yang akan datang dan hasil yang ingin dicapai.

                  ii. Problem Solving Agent

                   Menemukan sequence action untuk mencapai tujuannya.

                  iii. Algorithm are uninformed

           Tidak ada informasi untuk Problem, hanya deskripsi pada masalah tersebut

 

2.2 Pencarian Sebagai Solusi Pemecahan Masalah 

 Untuk mengukur performansi metode searching digunakan 4 kriteria :

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

•Time Complexity : berapa lama waktu yang dibutuhkan?

•Space Complexity : berapa banyak memori yang diperlukan?

•Optimality : apakah metode tersebut menjamin menemukan solusi yang terbaik jika terdapat beberapa solusi yang berbeda?

2.3 Metode-Metode Pencarian

 

•Uninformed Search : blind, exhaustive atau brute-force search

  Pencarian buta/ tanpa informasi yang dapat membantu proses pencarian; tidak terlalu efisien

•Informed Search : heuristic atau intelligent search.

  proses pencarian dengan informasi mengenai masalah, umumnya menebak jarak ke goal state dan efisien. Namun tidak ada jaminan bahwa solusi dapat tercapai.

*Depth First Search

        •Pencarian dilakukan pada satu node dalam setiap level dari yang paling kiri. Jika pada level yang paling dalam, solusi belum ditemukan, maka pencarian dilanjutkan pada node sebelah kanan. Node yang kiri dapat dihapus dari memori. Jika pada level yang paling dalam tidak ditemukan solusi, maka pencarian dilanjutkan pada level sebelumnya. Demikian seterusnya sampai ditemukan solusi. Jika solusi ditemukan maka tidak diperlukan proses backtracking (penelusuran balik untuk mendapatkan jalur yang dinginkan).

•Kelebihan DFS adalah:

•Pemakain memori hanya sedikit, berbeda jauh dengan BFS yang harus menyimpan semua node yang pernah dibangkitkan.

•Jika solusi yang dicari berada pada level yang dalam dan paling kiri, maka DFS akan menemukannya secara cepat.

•Kelemahan DFS adalah:

•Jika pohon yang dibangkitkan mempunyai level yang dalam (tak terhingga), maka tidak ada jaminan untuk menemukan solusi (Tidak Complete).

•Jika terdapat lebih dari satu solusi yang sama tetapi berada pada level yang berbeda, maka pada DFS tidak ada jaminan untuk menemukan solusi yang paling baik (Tidak Optimal)

*Breadth-First Search (BFS)

           •Pencarian dilakukan pada semua node dalam setiap level secara berurutan dari kiri ke kanan. Jika pada satu level belum ditemukan solusi, maka pencarian dilanjutkan pada level berikutnya. Demikian seterusnya sampai ditemukan solusi. Dengan strategi ini, maka dapat dijamin bahwa solusi yang ditemukan adalah yang paling baik (Optimal). Tetapi BFS harus menyimpan semua node yang pernah dibangkitkan. Hal ini harus dilakukan untuk penelusuran balik jika solusi sudah ditemukan.

 *Depth-Limited Search (DLS)

         •Metode ini berusaha mengatasi kelemahan DFS (tidak complete) dengan membatasi kedalaman maksimum dari suatu jalur solusi.

•Level maksimum dari suatu solusi harus diketahui terlebih dahulu.

•Jika batasan kedalaman terlalu kecil, DLS tidak dapat menemukan solusi yang ada. DLS menjadi tidak complete jika batasan kedalaman lebih kecil dibandingkan dengan level solusinya.

 * Uniform Cost Search (UCS) 

  •Konsepnya hampir sama dengan BFS. Perbedaannya adalah BFS menggunakan urutan level dari yang paling rendah ke paling tinggi sedangkan UCS menggunakan urutan biaya dari yang paling kecil sampai yang terbesar. 

  •UCS berusaha menemukan solusi dengan total biaya yang terendah yang dihitung berdasarkan biaya dari simpul asal menuju ke simpul tujuan. 

  •Biaya dari simpul asal ke suatu simpul n dilambangkan dengan g(n).

  

*  Iterative Deepening Depth-first search

        IDS merupakan metode yang menggabungkan kelebihan BFS (Complete dan Optimal) dengan kelebihan DFS (space complexity rendah atau membutuhkan sedikit memori). Tetapi konsekuensinya yaitu time complexity nya menjadi tinggi.

       Disebut juga sebagai sebuah strategi umum yang biasanya dikombinasikan dengan depth first tree search, yang akan menemukan berapa depth limit terbaik untuk digunakan. Hal ini dilakukan dengan secara menambah limit secara bertahap, mulai dari 0,1, 2, dan seterusnya sampai goal sudah ditemukan.

 

* Bidirectional search

       Pencarian dilakukan dari dua arah : pencarian maju (dari start ke goal) dan pencarian mundur (dari goal ke start). Ketika dua arah pencarian telah membangkitkan simpul yang sama, maka solusi telah ditemukan, yaitu dengan cara menggabungkan kedua jalur yang bertemu.

 

 

Sumber :

-  ocw.upj.ac.id/files/Slide-INF401-KECERDASAN-BUATAN-PERTEMUAN-3.pptx
-  https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=14&ved=0ahUKEwiuzc6omsjWAhUGOY8KHcpQCK8QFghVMA0&url=https%3A%2F%2Faliefteknik.files.wordpress.com%2F2012%2F12%2Fpencarian-dan-strategi-kontrol_pertemuan2.pptx&usg=AFQjCNG8Ju5kuRX_AHSfwwVeqKeZ2WIBDA