Nama : Dimas Bayu Gumelar
NPM : 11115924
Kelas: 3KA10
Dosen : ESSY MALAYS SARI SAKTI
metoda-metode yang terdapat dalam teknik pencarian yang
berdasarkan pada panduan (Heuristic Search), yaitu Generate and Test, Simple Hill
Climbing, Steepest-Ascent Hill Climbing, Simulated Annealing, Best First Search,
Greedy Search, A Star (A*), Problem Reduction, Constraint Satisfaction, dan MeansEnds
Analysis.
3.1 Generate-and-Test
Metode Generate-and-Test adalah metode yang paling sederhana dalam pencarian
heuristic. Jika pembangkitan possible solution dikerjakan secara sistematis, maka
prosedur akan mencari solusinya, jika ada. Tetapi jika ruang masalahnya sangat luas,
mungkin memerlukan waktu yang sangat lama.
Algoritma Generate-and-Test adalah prosedur DFS karena solusi harus
dibangkitkan secara lengkap sebelum dilakukan test. Algoritma ini berbentuk sistematis,
pencarian sederhana yang mendalam dari ruang permasalahan. Generate & test juga
dapat dilakukan dengan pembangkitan solusi secara acak, tetapi tidak ada jaminan
solusinya akan ditemukan.
Algorithm: Generate-and-Test
1. Generate a possible solution. For some problems, this means generating a particular
point in the problem space. For others, it means generating a path from a start state.
2. Test to see if this is actually a solution by comparing the chosen point or endpoint of
the chosen path to the set of acceptable goal states.
3. If a solution has been found, quit. Otherwise, return to step 1.
Contoh kasus:
Untuk permasalahan sederhana maka tehnik generate & test adalah tehnik yang layak .
Sebagai contoh, pada teka-teki yang terdiri dari empat kubus segi enam, dengan masingmasing
sisi dari setiap kubus dicat dengan 4 warna. Solusi dari teka-teki terdiri dari susunan kubus dalam beberapa baris yang semuanya empat sisi dari satu blok baris yang menunjukkan masing-masing
warna. Masalah ini dapat diselesaikan dengan manusia dalam beberapa menit secara sistematis dan lengkap dengan mencoba semua kemungkinan. Ini bisa diselesaikan dengan lebih cepat menggunakan prosedur generate & test. Pandangan sekilas pada empat blok yang tampak bahwa masih ada lagi, katakanlah bagian merah dari warna-warna lain yang ada. Sehingga ketika menempatkan blok dengan beberapa bagian merah, ini akan menjadi ide yang baik untuk digunakan jika sebagian darinya sebisa mungkin dibagian luar. Sebagian yang lain sebisa mungkin harus ditempatkan pada blok berikutnya. Menggunakan aturan ini, banyak konfigurasi diperlukan tanpa di-explore dan sebuah solusi dapat ditemukan lebih cepat.
3.2 Hill Climbing
Hill Climbing berbeda Generate-and-Test, yaitu pada feedback dari prosedur test
untuk membantu pembangkit menentukan yang langsung dipindahkan dalam ruang
pencarian. Dalam prosedur Generate & test , respon fungsi pengujian hanya ya atau
tidak. Tapi jika pengujian ditambahkan dengan atauran fungsi-fungsi yang menyediakan
estimasi dari bagaimana mendekati state yang diberikan ke state tujuan, prosedur
pembangkit dapat mengeksplorasi ini sebagaimana ditunjukkan di bawah. HC sering
digunakan jika terdapat fungsi heuristic yang baik untuk mengevaluasi state. Sebagai
contoh, anda berada di sebuah kota yang tidak dikenal, tanpa peta dan anda ingin menuju
ke pusat kota. Cara sederhana adalah gedung yang tinggi. Fungsi heuristics-nya adalah
jarak antara lokasi sekarang dengan gedung yang tinggi dan state yang diperlukan adalah
jarak yang terpendek.
3.2.1 Simple HC
Algorithm: Simple HC
1. Evaluate the initial state. If it is also a goal state, then return it and quit. Otherwise,
continue with the initial state as the current state.
2. Loop until a solution is found or until there are no new operators left to be applied in
the current state:
a). Select an operator that has not yet been applied to the current state and apply it to
produce a new state.
b). Evaluate the new state:
(i) If it is a goal state, then return it and quit.
(ii) If it is not a goal state but it is better than the current state, then make it the
current state.
(iii) If it is not better than the current state, then continue in the loop.
Tidak ada komentar:
Posting Komentar