20
yang
disebut
priority
queue.
Prioritas
yang
diberikan
ke
sebuah
jalur
x
ditentukan oleh fungsi
f(x) = g(x) + h(x)
Di
sini,
g(x)
adalah
nilai
cost
dari path
yang
telah
ditemukan,
yaitu berat atau bobot dari jalur antar
node
yang telah dilalui. h(x) adalah
estimasi heuristik dari nilai cost paling minimal yang digunakan atau
didapat
untuk
mencapai goal
dari
x.
sebagai
contoh
,
jika
“
cost”
adalah
jarak yang telah ditempuh, jarak lurus antara dua titik pada sebuah peta
adalah estimasi heuristik dari jarak yang akan ditempuh. Semakin kecil
nilai f(x), semakin besar prioritasnya.
Untuk
kasus
2
dimensi
cutting
box,
fungsi
f(x)
=
g(x)
+
h(x)
didefinisikan sebagai berikut :
•
g(x) adalah heuristic luas.
g(x) = Panjang cut x Lebar cut
Perhitungan
ini
digunakan
untuk
menentukan
barang
mana
yang
pertama kali akan diletakan.
•
h(x) adalah heuristic sisi.
Sk = (( KB – JK) + ( Kb – JK))
h(x) = (Sk - JKB) + Nt
Jika nilai h(x)1.1 < nilai h(x)1.2, maka ambil nilai h(x)1.2 , lalu
bandingkan dengan nilai h(x) berikutnya sampai ditemukan nilai
h(x) yang paling kecil.
Æ
Sk = Sisa Keliling
Æ
KB = keliling box
 |