Metode Pencarian (Blind Search) (Tugas 2 Softskill Pengenalan teknologi sistem cerdas )

 TEKNIKPENCARIAN/PENELUSURAN (SEARCHING)


·       Pada umumnya manusia mempertimbangkan sejumlah alternatif strategi dalam menyelesaikan suatu problema. 

·       Dalam permainan catur misalnya, seorang pemain mempertimbangkan sejumlah kemungkinan tentang langkah-langkah berikutnya, memilih yang terbaik menurut kriteria tertentu seperti kemungkinan respon lawannya.

·       Aspek tingkahlaku cerdas yang mendasari teknik penyelesaian problema seperti dalam permainan catur tersebut dinamakan proses pencarian ruang keadaan (space state search).

·       Exhaustive search – adalah proses pencarian terhadap seluruh ruang keadaan serangakaian langkah yang paling dimungkinkan untuk menghasilkan kemenangan. 

·       Walaupun metode ini dapat diterapkan pada setiap ruang keadaan, namum ukuran ruang keadaan yang sangat besar membuat pendekatan ini secara praktis tidak dimungkinkan (dalam permainan catur terdapat 10120 keadaan )

·       Bila kasus ini diimplementasikan ke dalam sisten komputer, maka akan membutuhkan memori yang sangat besar, dan waktu pencarian yang sangat lama. Dengan kata lain metode exhaustive search ini tidak efisien dan tidak efektif, sehingga tidak praktis untuk diimplementasikan.

·       Untuk mengatasi kendala tersebut di atas, ada beberapa cara yang dapat dilakukan, diantaranya: pertama teknik pencarian parsial (Blind Search) dan yang kedua teknik pencarian heuristic (Heuristik Search).


Pencarian Parsial (Blind Search)

A. PENCARIAN MELEBAR PERTAMA 
       (Breadth-First Search)

·       Pada metode breadth-first search, semua node pada level n akan dikunjungi terlebih dahulu sebelum mengunjungi node-node pada level n+1.
·       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 (lihat gambar di bawah ini).







Prosedur breadth_first_search
    Inisialisasi : open = [start]; closed [ ]
    While open  =  [ ] do
    Begin
Hapuskan keadaan paling kiri dari keadaan open,  
   sebutlah keadaan itu dengan X;
Jika X merupakan tujuan then return (sukses);
Buatlah semua child dari X;
Ambillah X dan masukkan pada closed;
Eliminasilah setiap child X yang telah berada pada 
   open atau closed, yang akan menyebabkan loop 
   dalam search;
Ambillah turunan di ujung kanan open sesuai urutan 
   penemuan-nya;
    End;

·       Keuntungan :
Ø 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 :
Ø 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. PENCARIAN KEDALAM PERTAMA

     (Depth-First Search)


·       Pada Depth-First Search, proses pencarian akan dilakukanpada semua anaknya sebelum dilakukan pencarian ke node-node yang selevel. Pencarian dimulai dari node akar ke level yang lebih tinggi. Proses ini diulangi terus hingga ditemukannya solusi (lihat gambar di bawah).


sprosedur depth_first_search
inisialisasi: open = [Start]; closed = []
while open x [] do
begin
hapuskan keadaan berikutnya dari sebelah kiri open, sebutlah keadaan itu dengan X;
jika X merupakan tujuan then return(sukses);
buatlah semua child yang dimungkinkan dari X;
ambilah X dan masukkan pada closed;
eliminasilah setiap child X yang telah berada pada  
   open atau closed, yang akan menyebabkan loop
   dalam search;
ambilah child X yang tersisa di ujung kanan open
   sesuai urutan penemuannya;
end.


·       Keuntungan :
Ø Membutuhkan memori yang relative kecil, karena hanya node-node pada lintasan yang aktif saja yang disimpan.
Ø Secara kebetulan, metode depth-first search akan menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan.
·       Kelemahan :
Ø Memungkinkan tidak ditemukannya tujuan yang diharapakan
Ø Hanya akan menemukan 1 solusi pada setiap pencarian

Contoh penerapan nya :

Implementasi Breadth First Search pada Java

untuk mengimplementasikan java pada BFS, saya menukil kodingannya Mark Watson dalam buku beliau Programming AI with Java. Beliau memberikan dua contoh penerapan BFS untuk pencarian jalur terpendek. 
1. Pencarian jalur terpendek pada game Maze 
2. Pencarian jalur terpendek pada simpul Graph

Pencarian Jalur terpendek pada game Maze





Game maze adalah game yang mengharuskan user untuk menemukan jalan keluar dan melewati banyak halangan (obstacle) dari sebuah ruang yang mirip labirin. Titik awalnya dimulai dari huruf S (Start) dan diakhiri pada kotak bertuliskan G (Goal). Ketika program dijalankan, sistem akan otomatis mencari rute terpendek dari kotak S menuju kotak G menggunakan metode BFS. Panjang rute hasil pencarian dituliskan dalam bentuk angka disetiap kotak.






Pencarian Jalur Terpendek pada Graph 



Titik awal adalah simpul 0 dan titik akhir adalah simpul 9, program secara otomatis akan mencari jalur terpendek dari simpul 0 menuju simpul 9 menggunakan metode BFS.


  • STUDI KASUS :
    Pada suatu hari ada seorang petani yang mempunyai seekor kambing dan srigala.Pada saat itu ia baru saja panen sayuran. Karena membutuhkan uang, petani tersebut hendak menjual kambing, serigala, dan sayurannya ke pasar Johar. Untuk sampai di pasar Johar, ia harus menyeberangi sebuah sungai.
Permasalahannya adalah di sungai itu hanya tersedia satu perahu saja yang bisa memuat petani dan satu penumpang lainnya (kambing, srigala, atau sayuran). Jika ditinggalkan oleh petani tersebut, maka sayuran akan dimakan oleh kambing dan kambing akan dimakan oleh serigala
  • DESKRIPSI:
P = Petani
Sy = Sayuran
K = Kambing
Sg = Serigala
  • RUANG KEADAAN
    Untuk daerah asal dan daerah seberang
    digambarkan.
    (P, Sy, K, Sg)
  • KEADAAN AWAL
    Daerah Asal = (P, Sy, K, Sg)
    Daerah seberang = (0, 0, 0, 0)
  • TUJUAN
    Daerah Asal = (0, 0, 0, 0)
    Daerah seberang = (P, Sy, K, Sg)
  • METODE PENYELESAIAN :
Terdapat dua metode penyelesaian yang akan dibahas pada postingan kali ini. Metode pertama adalah metode breadth first search (BFS), dan metode kedua adalah metode Depth First Search (DFS). Berikut ini akan dijelaskan penyelesaian studi kasus diatas dengan kedua metode tersebut.
  • BFS (Breadth First Search)
adalah sebuah algoritma pencarian solusi yang digambarkan dengan struktur pohon. Dimana penyelesaiannya dilakukan dimulai dari simpul akar kemudian melebar sesuai dengan tingkatan yang ada di dalam pohon. Berikut ini adalah algoritma BFS :
1.  Masukkan simpul akar ke dalam antrian Q. Jika simpul akar = simpul solusi (goal node), maka stop.
2.  Jika Q kosong, tidak ada solusi. Stop.
3.  Ambil simpul v dari kepala (head) antrian, bangkitkan semua anak-anaknya. Jika v tidak mempunyai anak lagi, kembali ke langkah 2. Tempatkan semua anak dari v di belakang antrian.
4.  Jika suatu simpul anak dari v adalah simpul solusi, maka solusi telah ditemukan, kalau tidak kembali lagi ke langkah 2.
  • GAMBAR BFS :

  • DFS (Depth First Search)
adalah sebuah algoritma pencarian yang digambarkan dengan struktur pohon seperti pada BFS. Penyelesaiannya dilakukan dengan mendalam. Pencarian solusi dilakukan secara menurun sesuai urutan yang ditentukan.
1.  Masukkan simpul akar ke dalam antrian Q. Jika simpul akar = simpul solusi, maka stop.
2.  Jika Q kosong, tidak ada solusi. Stop.
3.  Ambil simpul v dari kepala (head) antrian. Jika kedalaman simpul v sama dengan batas kedalaman maksimum, kembali ke langkah 2
4.  .Bangkitkan semua anak dari simpul v. Jika v tidak mempunyai anak lagi, kembali ke langkah 2. Tempatkan semua anak dari v di awal antrian Q. Jika anak dari simpul v adalah simpul tujuan, berarti solusi telah ditemukan, kalau tidak, kembali lagi ke langkah 2.


  • GAMBAR DFS :


Sumber :
https://creactiveit.wordpress.com/2015/05/08/halo-dunia/
http://www.elangsakti.com/2013/03/bahasan-fundamental-tentang-blind.html
karmila.staff.gunadarma.ac.id/Downloads/folder/0.0

Komentar

Posting Komentar

Postingan populer dari blog ini

PENDAPAT KALIAN TENTANG BUDAYA INDONESIA SAAT INI ?

           Menurut Saya , Memiliki budaya yang beragam dan berbeda bukan hanya untuk dibanggakan. Budaya yang beragam sudah menjadi tugas kita untuk melestarikannya. Walaupun  Pendapat Saya , keberanekaragaman budaya yang ada pada bangsa kita ada kekurangannya juga. Masyarakat akan bekerja dalam kelompok-kelompok, ras atau golongan tertentu. Padahal, suatu masalah akan lebih mudah jika dibicarakan dengan berserikat/berorganisasi. Kekurangan yang lain juga mendasar pada faktor dari luar, Seperti negara-negara luar yang sering mengompori dan menjadi pelopor perpecahan di Indonesia. Seperti negara Malaysia yang pernah mencantumkan beberapa budaya Indonesia seperti beberapa budaya yang berasal dari Batak dan Melayu sebagai budaya mereka. Padahal, tindak yang mereka lakukan tidak salah. Karena, orang Batak dan Melayu terdapat juga di Malaysia. Lalu jangan lupakan, Pulau Papua yang hampir lepas karena pengaruh dari negara luar termasuk Amerika Serikat.           Keberanekaragaman se
Baca selengkapnya

perbedaan budaya dan ilmu budaya dasar

Perbedaan Antara Pengetahuan Budaya Dan Ilmu Budaya Dasar Pengetahuan budaya yaitu sesuatu yang mempengaruhi tingkat pengetahuan yang meliputi sistem ide,cara pandang atau gagasan atau juga berupa kesimpulan yang muncul dalam pikiran kita tentang budaya dasar yang kita pelajari. Ilmu Budaya Dasar adalah ilmu yang mempelajari dasar-dasar kebudayaan, seperti mencakup : kesenian,bahasa,adat-istiadat,budaya daerah, budaya nasional. Pokok bahasan yang akan dikembangkan adalah : Manusia dengan cinta kasih Manusia dan keindahan Manusia dan penderitaan Manusia dan keadilan Manusia dan pandangan hidup Manusia dan tanggung jawab serta pengabdian Manusia dan kegelisahan Manusia dan harapan Kedelapan pokok bahasan itu termasuk dalam karya-karya yang tercakup dalam pengetahuan budaya. Perwujudan mengenai cinta, misalnya, terdapat dalam karya sastra, tarian, musik, filsafat, lukisan, patung dan sebagainya. Masing-masing pokok bahasan dapat didekati dengan baik menggunakan ca
Baca selengkapnya

Software Maintenance

  SOFTWARE MAINTENANCE Pengertian Software komputer adalah sekumpulan data elektronik yang disimpan dan diatur oleh komputer, data elektronik yang disimpan oleh komputer itu dapat berupa program atau instruksi yang akan menjalankan suatu perintah. Melalui sofware atau perangkat lunak inilah suatu komputer dapat menjalankan suatu perintah. Nama lain dari Software adalah perangkat lunak. Karena disebut juga sebagai perangkat lunak, maka sifatnya pun berbeda dengan hardware atau perangkat keras, jika perangkat keras adalah komponen yang nyata yang dapat diliat dan disentuh oleh secara langsung manusia, maka software atau Perangkat lunak tidak dapat disentuh dan dilihat secara fisik, software memang tidak tampak secara fisik dan tidak berwujud benda namun  bisa untuk dioperasikan. Pengertian maintenance sendiri adalah suatu kegiatan yang di lakukan manusia untuk menjaga atau merawat sebuah benda atau perangkat (keras atau pun lunak) agar dapat terus di gunakan. Pengertian software
Baca selengkapnya