19
Terdapat banyak variasi dalam masalah optimasi peletakkan posisi label ini,
seperti linear packing, packing by weight, packing by cost, dan lain sebagainya.
Karena masalah ini termasuk ke dalam NP-Hard, maka algoritma yang diketahui
efisien adalah heuristic. Penggunaan heuristic
bertujuan untuk mendapatkan hasil
yang baik dalam kebanyakan kasus, tetapi mungkin saja buka sebagai optimasi yang
paling optimal. Heurisitic
adalah sebuah algoritma yang mungkin saja menemukan
solusi yang baik, tetapi tidak ada bukti bahwa solusinya tidak bisa menjadi buruk
secara tidak masuk akal dan tidak ada argumen tentang hal ini bahwa hal seperti ini
mungkin saja terjadi.
2.6
NP-Hard
Menurut Wikipedia (2013), 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 dimana
dapat disesuaikan untuk mensimulasi logika dari komputer yang secara mungkin
dapat dikonstruksi.
Hal ini dikemukakan pada tahun 1936 oleh Alan Turing, polynomial time
adalah permasalahan waktu komputasi (ukuran berapa banyak 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.
 |