SEARCH LANJUTAN

SEARCH LANJUTAN

1. Masalah dan ruang masalah 

Untuk membuat system untuk menyelesaikan masalah terpisah, kita harus melakukan 4 hal sbb : 

1. Mendefinisikan masalah dengan tepat, meliputi definisi yg tepat tentang keadaan awal dan keadaan akhir sebagai solusi yang dapat diterima. 

2. Analisa masalah, beberapa fitur penting akan menentukan kelayakan dari beberapa teknik yang mungkin untuk menyelesaikan masalah. 

3. Membatasi dan menghadirkan pengetahuan yang diperlukan untuk menyelesaikan masalah 

4. Pilih teknik penyelesaian terbaik dan aplikasikan pada masalah.

2. Cara Merepresentasikan masalah 

Untuk membuat deskripsi formal dari permasalahan, harus dilakukan beberapa hal, diantaranya : 

1. Definisikan ruang stata yang memuat semua konfigurasi yg mungkin dari objek yang terkait (dan mungkin  beberapa yg tidak mungkin). Hal ini, tentu saja mungkin  untuk mendefiniskan ruang stata dengan jumlah stata  yang tidak terbatas. 

2. Tentukan satu atau beberapa stata yang menyatakan keadaan awal dari masalah, disebut initial states. 

3. Tentukan satu atau beberapa stata yang dapat diterima sebagai keadaan akhir (solusi), disebut goal states.

3. Konsep Pencarian

Beberapa metode/konsep search yang akan dipelajari :

1. Breadth-First-Search

2. Depth-Fisrt-Search

3. Generate-and-Test

4. Hill-Climbing

5. Best-First-Search 

Pencarian buta (1,2), pencarian heuristic (3,4,5)

4. Metode Pencarian Heuristik 

Teknik pencarian heuristik (heuristic searching) merupakan suatu strategi untuk melakukan proses pencarian ruang keadaan (state space) suatu problema secara selektif, yang memandu proses pencarian yang kita lakukan di sepanjang jalur yang memiliki kemungkinan sukses paling besar, dan mengesampingkan usaha yang bodohdan memboroskan waktu.

a. Generate And Test (Pembangkit dan Pengujian) 

Teknik Generate-and-Test adalah teknik yang paling mudah di bandingkan teknik search yang lain, namun relatif lebih lama dalam mendapatkan solusi.

Algoritma Generate-and-Test :

1. Bentuk solusi yang mungkin. Untuk beberapa masalah, ini berarti membentuk poin terpisah dari area permasalahan. Pada masalah lain, ini berarti membentuk jalur dari stata awal. 

2. Lakukan test untuk melihat apakah poin yang ditemui adalah solusi dengan membandingkan poin yang dipilih atau poin terakhir dari jalur yang dipilih dengan kumpulan stata tujuan 

3. Jika solusi sudah ditemukan, quit. Jika belum kembali ke langkah 1.

b. Hill Climbing (Pendakian Bukit) 

Teknik Hill Climbing adalah pengembangan dari teknik Generate-and-Test, dengan penambahan adanya umpan balik dari prosedur test yang sudah digunakan untuk membantu memilih arah mana yang harus ditelusuri pada setiap area search. Pada prosedur Generate-and-Test yang murni, fungsi test hanya ditanggapi dengan Ya atau Tidak. Tetapi pada Hill￾Climbing fungsi test ditambahkan dengan fungsi heuristic atau fungsi objectif yang memungkinkan perkiraan seberapa dekat simpul yang ditelusuri terhadap goal state.

Hill-climbing sering kali digunakan jika fungsi heuristic yang baik tersedia untuk mengevaluasi stata, tapi ketika tidak ada lagi pengetahuan yang dapat digunakan. Sebagai contoh, anda berada disuatu kota yang belum pernah anda kunjungi tanpa memiliki peta. Tujuannya menuju gedung tertinggi yang terlihat dari tempat anda berada.

 Penyelesaian masalah diatas dimulai dengan meninjau karakteristik masalah, apakah solusi yang pertama ditemukan dapat diterima sebagai solusi yang baik ? (mutlak atau relatif ?) Karena tidak ada peta dan tidak ada pengalaman memilih jalan (tidak ada pengetahuan) maka dipilih saja jalan yang arahnya menuju solusi sampai kita tiba di tujuan tanpa mengulangi atau mencoba lagi jalur yang lain dan kita terima itu sebagai solusi terbaik (dgn mengabaikan kemungkinan lain). Jadi adalah masuk akal menerapkan hill-climbing ketika tidak ada alternatif yang dapat diterima untuk memilih atau menuju pada suatu stata.

c. Best-First-Search 

Teknik Best-First-Search adalah teknik search yang menggabungkan kebaikan yang ada dari teknik Depth-First-Search dan Breadth-First-Search. 

Tujuan menggabungkan dua teknik search ini adalah untuk menelusuri satu jalur saja pada satu saat, tapi dapat berpindah ketika jalur lain terlihat lebih menjanjikan dari jalur yang sedang ditelusuri. Untuk mendapatkan jalur yang menjanjikan adalah dengan memberikan skala prioritas pada setiap stata saat dihasilkan dengan fungsi heuristic.

Untuk menggunakan Best-First-Search, kita memerlukan dua daftar simpul, yaitu : 

1. OPEN

berisi simpul yang dihasilkan dari fungsi heuristic tapi belum dievaluasi, memilki antrian prioritas dimana elemen dengan prioritas tertinggi adalah yang memiliki nilai paling baik yang dihasilkan fungsi heuristic. 

2. CLOSED

berisi simpul yang sudah dievaluasi. Kita perlu tetap menyimpan simpul-simpul ini dalam memori jika kita ingin melakukan search pada Graph, sehingga jika kita menemui suatu simpul kita bisa memeriksa apakah simpul ini sudah pernah dieavaluasi atau belum

SEARCH

Rangkuman materi pertemuan 4 tentang Pencarian yang terdiri dari: 

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

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?

2. Teknik Pencarian dan Penjelasannya 

Pada dasarnya ada dua teknik pencarian yang biasanya digunakan, yaitu:

1. Pencarian buta (Blind Search)

Pencarian buta merupakan sekumpulan prosedur yang 

digunakan dalam melacak ruang keadaan. Pencarian 

berlangsung sampai solusi terakhir ditemukan. Idenya 

adalah menguji seluruh kemungkinan yang ada untuk 

menemukan solusi. 

Pendekatan ini kurang efisien dan merupakan pemaksaan 

(brute force search) .Dalam memecahkan masalah yang 

sangat besar sejumlah keadaan baru muncul, sehingga 

alternatif yang perlu dipertimbangkan pun menjadi lebih 

banyak. Akibatnya diperlukan waktu yang lama untuk 

menemukan satu solusi.

3. Karakteristik Masalah

Pencarian heuristic adalah metode yang sangat umum yang dapat diterapkan dalam begitu banyak masalah, meliputi begitu banyak variasi teknik yang spesifik, dimana masing-masing efektif untuk penyelesaian masalah tertentu yang lebih spesifik. Untuk memilih metode mana (atau kombinasi metode mana) yang akan digunakan untuk menyelesaikan masalah, penting untuk menganalisa masalah pada beberapa dimensi kunci atau karakteristik, sebagai berikut :

•  Dapatkah masalah disederhanakan kedalam kelompok terpisah yang lebih kecil atau subprogram yang lebih mudah? 

•    Dapatkah satu tahap penyelesaian solusi diabaikan atau setidaknya tidak dilakukan jika terbukti tidak layak ? 

•    Apakah ruang lingkup masalah dapat diprediksi ?

•  Dapatkah dinyatakan sebuah solusi yang baik untuk penyelesaian masalah tanpa membandingkannya dengan solusi lain yang mungkin ? 

•  Solusi yang diinginkan adalah sebuah stata atau jalur menuju stata ?

•  Apakah sejumlah pengatahuan mutlak diperlukan untuk menyelesaikan masalah atau pengetahuan hanya diperlukan untuk membatasi pencarian ? 

• Dapatkah komputer yang diberikan permasalahan langsung memberikan solusi atau pemecahan masalah memerlukan interaksi antara komputer dan manusia ?

4. Teknik Search 

• Arah search

Dapat dilakukan :

Maju, bermula dari keadaan awal (start state)

Mundur, diawali dari keadaan tujuan (goal state)

• Topologi proses search

Ada dua macam penggambaran problem, yaitu dalam 

bentuk :

1. Pohon (tree)

2. Graf (graph) :Graf berarah dan Graf tidak berarah

5. Metode Breadth-First-Search 

Algoritma Breadth-First-Search :

1. Bentuk variabel dengan nama NODE-LIST dan jadikan sebagai initial state. 

2. Sampai goal state ditemukan atau NODE-LIST kosong, lakukan : 

a. ambil elemen pertama dari NODE-LIST, sebut E. jika NODE-LIST kosong, quit. 

b. Untuk tiap cara dimana tiap aturan(fungsi) dapat cocok dengan stata di E, lakukan : 

i. Gunakan aturan(fungsi) untuk menuju stata baru

ii. Jika stata baru adalah goal state, quit return stata ini

iii. Jika bukan, tambahkan stata baru di akhir NODE-LIST. 

Kebaikan dan Keburukan Breadth-First-Search

Kebaikan Breadth-First-Search :

• Breadth-First-Search tidak akan terjebak untuk menelusuri satu jalur tertentu saja 

• Jika solusi memang ada, maka dijamin Breadth-First-Search akan menemukannya.  

Keburukan Breadth-First-Search : 

• Memerlukan memori lebih besar karena harus menyimpan semua simpul dari tree yang ditelusuri 

• Harus menelusuri semua bagian tree pada level yang sama sebelum beralih ke level berikutnya.

6. Metode Depth-Fisrt-Search 

Algoritma Depth-Fisrt-Search :

1. Jika initial state adalah goal state, quit dan return success

2. Jika bukan, lakukan dibawah ini sampai dicapai sinyal success atau gagal 

    a. Tentukan successor, E dari initial state. Jika tidak ada lagi successor, maka sinyal gagal 

    b. Jalankan Depth-Fisrt-Search dengan E sebagai initial state

    c. Jika success dihasilkan, sinyal success. Jika tidak maka ulangi langkah 2

Kebaikan dan Keburukan Depth-First-Search

Kebaikan Depth-First-Search :

• Depth-First-Search memerlukan ruang memori lebih kecil karena hanya menyimpan simpul-simpul dari path/jalur yang sedang dikerjakan. 

• Dapat menemukan solusi tanpa menelusuri terlalu banyak ruang search. 

Keburukan Depth-First-Search :

• Ada kemungkinan terjebak pada satu jalur sampai terlalu jauh, bahkan selamanya, sebelum jalur tsb mendapatkan stata yang tidak lagi memiliki successor (buntu). 

• Mungkin menemukan jalur panjang ke solusi pada satu bagian dari tree, sementara jalur terpendek tersedia pada bagian lain tree yang belum ditelusuri

SISTEM KECERDASAN BUATAN

Rangkuman materi pertemuan 3 tentang Masalah dan Pemecahan Masalah yang terdiri dari: Sistem Kecerdasan Buatan 

1. Mendefinisikan Masalah 

   Untuk membuat deskripsi formal dari permasalahan, harus dilakukan beberapa hal, diantaranya :

1. Definisikan ruang stata yang memuat semua konfigurasi yg mungkin dari objek yang terkait (dan mungkin beberapa yg tidak mungkin). Hal ini, tentu saja mungkin
untuk mendefiniskan ruang stata dengan jumlah stata yang tidak terbatas.

2. Tentukan satu atau beberapa stata yang menyatakan keadaan awal dari masalah, disebut initial states

3. Tentukan satu atau beberapa stata yang dapat diterima sebagai keadaan akhir (solusi), disebut goal states

4. Tentukan sejumlah aturan yang menentukan aksi yang diperkenankan, hal ini mencakup beberapa hal sbb :
a. Apa asumsi non stata yang ditampilkan dalam deskripsi masalah non formal ? Akan menentukan yg termasuk dan tidak termasuk stata
b. Seberapa luas aturan harus dibuat ? Dapat menentukan aturan diberlakukan untuk stata mana saja
c. Berapa banyak pekerjaan yang diperlukan untuk menyelesaikan masalah harus disusun dan dimasukkan ke dalam aturan? Akan menentukan jumlah baris aturan

2. Sistem Produksi 

   Sistem produksi terdiri dari :

1. Sejumlah aturan, dimana tiap aturan memiliki sis kiri yang menyatakan bentuk yang dapat digunakan dan sisi kanan yang menyatakan hasil operasi jika aturan diaplikasikan.

2. Satu atau lebih pengetahuan/database yang berisi informasi apapun yang berkaitan dgn tiap masalah. Beberapa bagian database mungkin tetap sedangkan yang lain ditambahkan sesuai dengan masalah yang dihadapi. Informasi dalam database dapat tersusun dalam banyak cara berbeda.

Strategi kendali yang akan menentukan perintah dalam aturan yang mana yang akan dibandingkan dengan database dan cara menyelesaikan konflik yang muncul ketika ada lebih dari satu aturan yang cocok. 

4. Penggunaan aturan

3. Strategi Kendali 

Strategi kendali diperlukan untuk memutuskan aturan mana yang akan digunakan dalam lanjutan proses pencarian untuk mendapatkan penyelesaian masalah, hal ini akan semakin diperlukan jika terdapat lebih dari satu atau semakin banyak aturan yang mungkin untuk digunakan dalam tiap tahap proses. Pada akhirnya bagaimana keputusan dibuat akan mempengaruhi kecepatan dalam mendapatkan penyelesaian masalah. 

Syarat suatu strategi kendali yang baik adalah :

1. Menggerakkan stata (menjalankan proses) menuju solusi

2. Harus sistematik 

Kedua syarat itu akan melahirkan banyak metode pencarian

4. Contoh Kasus

 Contoh Kasus : Bejana Air

Diberikan dua bejana air, dengan kapasitas 4 liter dan 3 liter, yang keduanya tidak memiliki skala/batas ukuran. Ada sejumlah tak terbatas air yang dapat diisikan kedalam
bejana. Bagaimana cara mengisikan tepat 2 liter air ke dalam bejana berukuran 4 liter?

 Definisi ruang stata kasus Bejana Air
Definisi ruang stata untuk kasus bejana air dapat dinyatakan sebagai pasangan bilangan bulat 

  (x,y); x=0,1,2,3 atau 4 dan y=0,1,2 atau 3

Dimana x menyatakan volume air pada bejana 4 liter dan y menyatakan volume air pada bejana 3 liter.

Stataawal (initial state) : (0,0) dmn kedua bejana kosong

Stata akhir (goal state) : (2, n) dmn bejana pertama berisi 2 liter dan bejana kedua bisa berisi berapa saja.

 Sistem Produksi Bejana Air

1. Keadaan (yg mungkin) (x,y) If x <4 = Hasil(yg dilakukan)→ (4,y) = Arti, Penuhi bejana 4 liter

2. Keadaan (x,y) If y<3  = Hasil→ (x,3)  = Arti, Penuhi bejana 3 liter

3. Keadaan  (x,y) If x>0  = Hasil→ (x – d, y)  =  Arti, Tuang air dari bejana4 liter

4. Keadaan (x,y) If y>0  = Hasil→ (x, y – d)  = Arti, Tuang air dari bejana 3 liter

5. Keadaan (x,y) Ifx > 0  = Hasil → (0,y)  =  Arti, Kosongkan bejana 4 liter 

6. Keadaan (x,y) If y > 0  = Hasil→ (x,0)   = Arti, Kosongkan bejana 3 liter 

7. Keadaan (x,y) Ifx+y>4 and y>0  = Hasil→ (4, y-(4-x))  = Arti, Tuang air dari bejana 3 liter ke bejana 4 liter sampai bejana 4 liter penuh 

8. Keadaan (x,y) Ifx+y>3 and x>0  = Hasil→ (x-(3- y),3)   = Arti, Tuang air dari bejana 4 liter ke bejana 3 liter sampai bejana 3 liter penuh

9. Keadaan (x,y) Ifx+y<4 and y>0   = Hasil→ (x+y,0)   = Arti, Tuang semua air dari bejana 3 liter ke bejana 4 liter 

10. Keadaan (x,y) Ifx+y<3 and x>0   = Hasil→ (0,x+y)  = Arti, Tuang semua air dari bejana 4 liter ke bejana 3 liter 

11. Keadaan (0,2)   = Hasil→ (2, 0)   = Arti, Tuang 2 liter air dari bejana 3 liter ke bejana 4 liter 

12. Keadaan (2,y)  = Hasil → (0,y)   = Arti Buang 2 liter air dari bejana 4 liter

Penyelesaian Kasus Bejana Air

Operator => IsiBejana 4 ltr => Isi Bejana 3 ltr

      -           =>             0            =>              0

     2           =>             0            =>              3

     9           =>             3            =>              0

     2           =>             3            =>              3

    7            =>             4            =>              2

5 atau 12 =>             0             =>             2

9 atau 11 =>             2             =>             0

Hasil Analisa Masalah

Permasalahan dapat dipecahkan dengan menggunakan aturan produksi yang dikombinasikan dengan pendekatan strategikendali untuk menelusuri ruang masalah sampai ditemukan jalur dari initial state ke goal state. Sehingga proses pencarian menjadi penting untuk menyelesaikan masalah. Pencarian adalah mekanisme umum yang dapat digunakan ketika tidak ada metode langsung lain yang  diketahui.