15
Elemen
: sebuah item (barang) yang ditempatkan di dalam bin
yang mempunyai tinggi yang pasti (element height).
Ada
banyak
variasi
dari
masalah ini,
seperti
linear
packing,
packing by weight, packing by cost, dan lain-lain. Karena termasuk ke dalam NP-
Hard,
maka
algoritma
yang
diketahui paling efisien adalah heuristic,
untuk
mendapatkan hasil yang baik dalam kebanyakan
kasus,
di
mana
mungkin
saja
bukan sebagai solusi yang optimal. Heuristic adalah sebuah algoritma mungkin
saja menemukan solusi yang baik tetapi
tidak ada bukti bahwa solusinya tidak
bisa menjadi buruk secara tidak masuk akal, tidak ada argumen tentang hal ini
bahwa ini mungkin saja terjadi.
2.3.1
NP- Hard
Dalam teori
“computational
complexity”,
NP
(“Non-deterministic
Polynomial
time") adalah sekumpulan permasalahan yang dapat dipecahkan
menggunakan polynomial
time -
non-deterministic Turing
machine. Turing
machines
merupakan
symbol
abstrak
dasar
yang
memanipulasi
alat
di
mana,
dapat disesuaikan untuk mensimulasi logika dari computer yang secara mungkin
dapat dikonstruksi. Hal ini dikemukakan pada tahun 1936 oleh Alan Turing.
Polynomial time
adalah permasalahan waktu komputasi (ukuran berapa
banyaknya
langkah
yang digunakan perangkat keras atau sistem perangkat
lunak
dalam pengkomputasi-pemrosesan
informasi).
Polynomial
adalah
sebuah
pernyataan yang terbentuk dari satu atau lebih variable dan konstanta, dan hanya
menggunakan penjumlahan, pengurangan serta perkalian.
 |