Minggu, 16 Oktober 2016

Home » » METODE PENCARIAN DAN PELACAKAN

METODE PENCARIAN DAN PELACAKAN

By  07.52  No comments
METODE PENCARIAN DAN PELACAKAN 

 Metode Pencarian 
Metode pencarianadalah bagian dari kesimpulan, dimana setiap state menggambarkan hipotesis dalam sebuah rangkaian deduktif


Pohon Pelacakan
Untukan menghindari kemungkinan adanya proses pelacakan suatu node secara berulang, maka digunakan struktur pohon. Struktur pohon digunakan untuk menggambarkan keadaan secara hirarkis.

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 sampai ditemukannya solusi.


Algoritma
  1. buat sebuah antrian, inisialisasi node pertama dengan Root dari tree
  2. bila node pertama, jika ≠ GOAL, diganti dengan anak-anaknya dan diletakkan di belakang PER LEVEL
  3. bila node pertam = GOAL, selesai

Lintasan yang didapat : S-B-C-E-Z

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 akan ditemukan

Kelemahan
  • membutukan memori yang cukup banyak, karena menyimpan semua node dalam satu pohon.
  • kemungkinan ditemukan optimal lokal.

Depth-First Search
Pada Depth First Search, proses pencarian akan dilaksanakan pada semua anak anaknya sebelum dilakukan pencarian ke node-node yang selevel. Pencarian dimulai dari node akar ke level yang lebih tinggi. Proses ini diulangi terus hingga ditemukan solusi


Algoritma
  1. buat sebuah antrian, inialisasi node pertama dengan root dari tree
  2. bila node pertama, jika ≠ GOAL, node dihapus diganti denga anak-anaknya dengan urutan LChild
  3. Bila node pertama = GOAL, selesai

Lintasan yang didapat : S-A-B-C-E-Z

Keuntungan
  • Membutukan memori yang relative kecil, karena hanya node-node pada lintasan yang aktif saja yang disimpan.
  • Menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan

Kelemahan
  • Kemungkinan terjebak pada optimal lokal
  • Hanya akan mendapatkan 1 solusi pada setiap pencarian

Pencarian Heuristik
Metode heuristic search diharapkan bisa menyelesaikan permasalahan yang lebih besar. Metode heuristic search menggunakan suatu fungsi yang menghitung biaya perkiraan (estimasi) dari suatu simpul tertentu menuju ke simpul tujuan disebut fungsi heuristic

Pembangkit & Pengujian (Generate and Test)
Pada prinsipnya metode ini merupakan penggabungan antara depth-first search dengan pelacakan mundur (backtracking), yaitu bergerak ke belakang menuju pada suatu keadaan awal.

Algoritma:
  1. Bangkitkan suatu kemungkinan solusi (membangkitkan suatu titik tertentu atau lintasan tertentu dari keadaan awal).
  2. Uji untuk melihat apakah node tersebut benar-benar merupakan solusinya dengan cara membandingkan node tersebut atau node akhir dari suatu lintasan yang dipilih dengan kumpulan tujuan yang diharapkan.
  3. Jika solusi ditemukan, keluar. Jika tidak, ulangi kembali langkah yang pertama.
Contoh : Traveling Salesman Problem (TSP)
Seorang salesman ingin mengunjungi n kota. Jarak antara tiap-tiap kota sudah diketahui. Ingin diketahui rute terpendek dimana setiap kota hanya boleh dikunjungi tepat 1 kali.

Contoh : Traveling Salesman Problem (TSP)
Generate & test akan membangkitkan semua solusi yang mungkin:
  • A – B – C – D
  • A – B – D – C
  • A – C – B – D
  • A – C – D – B, dll
Kelemahan dari Pembangkit & Pengujian (Generate and Test) yaitu ;
  • Perlu membangkitkan semua kemungkinan sebelum dilakukan pengujian
  • Membutuhkan waktu yang cukup lama dalam pencariannya

Pendakian Bukit (Hill Climbing)
  • Metode ini hampir sama dengan metode pembangkitan & pengujian, hanya saja proses pengujian dilakukan dengan menggunakan fungsi heuristik.
  • Pembangkitan keadaan berikutnya sangat tergantung pada feedback dari prosedur pengetesan.
  • Tes yang berupa fungsi heuristic ini akan menunjukkan seberapa baiknya nilai terkaan yang diambil terhadap keadaan-keadaan lainnya yang mungkin.
Simple Hill Climbing

Algoritma
  1. Mulai dari keadaan awal, lakukan pengujian: jika merupakan tujuan, maka berhenti; dan jika tidak, lanjutkan dengan keadaan sekarang sebagai keadaan awal.
  2. Kerjakan langkah-langkah berikut sampai solusinya ditemukan, atau sampai tidak ada operator baru yang akan diaplikasikan pada keadaan sekarang:
    • Cari operator yang belum pernah digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru.
    • Evaluasi keadaan baru tersebut.
    • Jika keadaan baru merupakan tujuan, keluar.
    • Jika bukan tujuan, namun nilainya lebih baik daripada keadaan sekarang, maka jadikan keadaan baru tersebut menjadi keadaan sekarang.
    • Jika keadaan baru tidak lebih baik daripada keadaan sekarang, maka lanjutkan iterasi.
Categories: 

0 komentar:

Posting Komentar