Local search, hill climbing, dan annealing

Yang akan kamu pahami

Hitung satu nilai objektif dari konfigurasi, tentukan tetangga, dan jelaskan mengapa perbaikan lokal bisa berhenti terlalu dini.

Konsep inti

Satu state 4-queens menyimpan baris ratu untuk tiap kolom. Dua ratu konflik bila barisnya sama atau selisih baris mutlak sama dengan selisih kolom. Minimalkan jumlah pasangan konflik. Steepest memilih perbaikan terbaik di antara semua tetangga, sedangkan first choice mengambil perbaikan pertama yang ditemukan. Plateau muncul ketika banyak tetangga memiliki nilai sama.

Coba langkahnya

Mulai dari 2,4,1,1. Tiap langkah hanya boleh mengubah posisi satu ratu. Hitung pasangan konflik sekali per pasangan.

Simulated annealing

Untuk minimisasi, ambil selisih $\Delta = h(\text{baru}) - h(\text{lama})$. Bila $\Delta > 0$, peluang menerima kandidat adalah $e^{-\Delta/T}$ untuk suhu $T > 0$. Untuk $\Delta = 2$, peluangnya sekitar 0,61 pada $T=4$ dan 0,14 pada $T=1$. Bagian ini memperluas deck sebagai latihan soal arsip.

Cek pemahaman