BAB 2 PENYELESAIAN MASALAH

PENGANTAR TEKNOLOGI SISTEM CERDAS

BAB 2 PENYELESAIAN MASALAH

DISUSUN OLEH

RIZKA ANDRIANI MUHAMMAD

16115120

3KA12

UNIVERSITAS GUNADARMA

PTA 2017-2018

STRATEGI PENCARIAN YANG TIDAK BERBENTUK/UNIFORMED SEARCH STRATEGY

a.       Breadth-first search

Breadth First Search (BFS) merupakan metode pencarian yang bertujuan untuk memperluas dan memeriksa semua simpul pada graph atau urutan kombinasi dengan pencarian secara sistematis melalui setiap solusi.

BFS melakukan pencarian secara mendalam pada keseluruhan graph atau urutan tanpa memperhatikan tujuan sehingga menemukan tujuan tersebut. Dan juga,ia tidak menggunakan algoritma heuristik

Karakteristik BFS,antara lain…

-          Jika ada solusi, BFS akan menemukannya.

-          BFS akan menemukan solusi dengan jalur terpendek.

-          BFS tidak akan terjebak dalam “looping”.

-          BFS membutuhkan space untuk menyimpan node list antrian dan space yang dibutuhkan dan mungkin space yang dibutuhkan itu cukup besar.

-          Asumsi : 

                1. Ada solusi dalam pohon

                2. Pencarian tree adalah secara terurut.

Contoh BFS 

Keterangan :

1. Pada metode breadth-first search, semua node pada level n akan dikunjungi terlebih dahulu sebelum mengunjungi node-node pada level n+1.

 2. Pencarian dimulai dari node akar terus ke level ke-1 dari kiri ke kanan, kemudian berpindah ke level berikutnya, demikian pula dari kiri ke kanan hingga ditemukannya solusi.

 3. Urutan proses searching BFS ditunjukkan dalam Gambar 1.6 adalah: A,B,C,D,E,F,

Keuntungan BFS :

-          Tidak akan menemui jalan buntu

-          Jika ada satu solusi, maka breadth-first search akan menemukannya. Dan, jika ada lebih dari satu solusi, maka solusi minimum akan ditemukan.

Kelemahan BFS :

-          Membutuhkan memori yang cukup banyak, karena menyimpan semua node dalam satu pohon.

-          Membutuhkan waktu yang cukup lama, karena akan menguji n level untuk mendapatkan solusi pada level yang ke-(n+1).

b.      Uniform-cost search

Konsepnya hampir sama dengan BFS, bedanya adalah bahwa BFS menggunakan urutan level yang paling rendah sampai yang paling tinggi, sedangkan UCS menggunakan urutan biaya dari yang paling kecil sampai yang terbesar.

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

c.       Depth-first search

Proses searching sistematis buta yang melakukan ekpansi sebuah path (jalur) menuju penyelesaian masalah sebelum melakukan ekplorasi terhadap path yang lain. Proses searching mengikuti sebuah path tunggal sampai menemukan goal atau dead end.

Apabila proses searching menemukan dead-end, DFS akan melakukan penelusuran balik ke node terakhir untuk melihat apakah node tersebut memiliki path cabang yang belum dieksplorasi.  Apabila cabang ditemukan, DFS akan melakukan cabang tersebut. Apabila sudah tidak ada lagi cabang yang dapat dieksplorasi, DFS akan kembali ke node parent dan melakukan proses searching terhadap cabang yang belum dieksplorasi dari node parent sampai menemukan penyelesaian masalah.

Kelebihan DFS ,antara lain..

-          Pemakaian 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,antara lain…

-          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).

Urutan proses searching DFS ditunjukkan dalam Gambar 1.5 adalah: A, B, E, F, G, C, ...

d.      Depth-limited search

Metode ini berusaha mengatasi kelemahan DFS (tidak complete) dengan membatasi kelemahan maksimum dari suatu jalur solusi. Tetapi, sebelum menggunakan DLS, kita harus tahu berapa level maksimum dari suatu solusi.

e.      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.

f.        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.

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

Pencarian sebagai solusi pemecahan masalah

Didefinisikan sebagai suatu teknik penyelesaian masalah dengan cara merepresentasikan masalah ke dalam state dan ruang masalah serta menggunakan strategi pencarian untuk menemukan solusi. 

Langkah-langkah dalam teknik searching,antara lain…

 1. Mendefinisikan ruang masalah/ruang keadaan untuk suatu masalah yg dihadapi.

2. Mendefinisikan aturan produksi yang digunakan untuk mengubah suatu “state” ke “state” lainnya.      Aturan produksi adalah  operasi yg mengubah suatu state ke state lainnya.

3.  Memilih metode pencarian yg tepat sehingga dapat menemukan solusi terbaik dengan usaha yang minimal. 

Untuk mengukur performansi metode pencarian, terdapat 4 kriteria yang 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 yang berbeda ?

Proses searching ini berupa jalur yang menggambarkan keadaan awal sebuah masalah menuju kepada penyelesaian masalah yang diinginkan (i.e., the solved problem)

Metoda searching pada kecerdasan buatan merupakan searching terhadap problem space bukan searching data (e.g., angka, karakter, string) tertentu

Sumber :

http://socs.binus.ac.id/2013/04/23/uninformed-search-dan-informed-search/

viska.web.id/wp-content/uploads/2012/03/Modul-Pertemuan-2-7.pdf

ocw.upj.ac.id/files/Slide-INF401-KECERDASAN-BUATAN-PERTEMUAN-3.pptx

https://pakeklinux.files.wordpress.com/2010/.../pertemuan-3-masalah-ruang-masalah.ppt