33
yang
tidak
akan
memperbaiki batas
tersebut
(lebih
rendah).
Variabel
alpha
(a)
digunakan
sebagai
batas
bawah
node
yang
melakukan maksimasi, sedangkan
variable
(ß)
digunakan
sebagai
batas
atas
bagi
node
yang
melakukan
minimasi.
Pada
node-node yang
melakukan minimasi,
evaluasi
akan
dihentikan jika
sudah
didapat
node
anak
yang
memiliki nilai
lebih
kecil
disbanding
dengan
batas
bawah
(a),
sedangkan pada
node-node yang
melakukan
maksimasi, evaluasi
akan
dihentikan jika
sudah
didapat
node anak
yang
memiliki
nilai
lebih besar
dibanding
dengan batas atas (ß).
Pada akar pohon pencarian,
nilai a diberikan
nilai sebesar
mungkin sedangkan
nilai ß
diberikan nilai sekecil
mungkin. Node-node
yang
melakukan
maksimasi dan
minimasi akan memperbaiki nilai a dan ß nya masing-masing.
2.10
Backtracking
Algoritma
backtracking
mencoba
setiap
kemungkinan
hingga
menemukan
tujuannya.
Algoritma
backtracking
menggunakan Depth-First-Search
dari
serangkaian
solusi-solusi
yang
memungkinkan.
Saat
pencarian,
jika suatu
alternatif tidak berhasil, pencarian kembali (backtrack) ke titik pilih (choice
point),
titik
yang
memiliki alternatif lain, dan
mencoba alternatif berikutnya. Saat
semua alternatif sudah
dicoba semua, pencaran kembali ke
titik pilih sebelumnya
dan
mencoba alternatif dari titik tersebut. Jika tidak ada
lagi titik pilik
yang dapat
dicoba, maka pencarian gagal (fail).
Algortima seperti
ini biasanya dilakukan dalam
fungsi rekursif dimana
setiap
instance
mengambil 1
variabel
lebih dan
secara alternatif
mengatur semua
 |