12
Berdasarkan
pengertian
problem (masalah) di atas, tidak semua
masalah dapat dipecahkan, dengan kata
lain
mempunyai
algoritma solusi.
Ada
dua
buah
klasifikasi
permasalahan
(Leahy,
Billy.,
2000,
pp21-24),
yaitu sebagai berikut:
1. Permasalahan yang dapat dipecahkan (decidable / solvable problem)
Permasalahan
yang
termasuk
klasifikasi
ini
adalah
semua
jenis
permasalahan
yang
mempunyai algoritma solusi, walaupun kadang kala
tidak
praktis.
Dari
segi
komputasi,
permasalahan
dalam klasifikasi
ini
dapat
dibedakan menjadi tiga kategori yaitu:
1. Permasalahan Tractable (mudah dari segi komputasi)
Suatu
masalah
dikatakan tractable jika
masalah
tersebut
dapat
dipecahkan oleh suatu algoritma yang eflsien. Contoh permasalahan
trackable antara
lain
adalah
masalah
penentuan
bilangan
terbesar
di
antara
n bilangan,
pengurutan n bilangan,
penentuan
lintasan
terpendek
antara
dua
buah
vertex
di
dalam sebuah
graph
dan
lain
sebagainya.
2.
Permasalahan Intractable (sukar dari segi komputasi)
Suatu masalah dikatakan intractable jika tidak ada algoritma yang
eflsien untuk memecahkan masalah tersebut.
3.
Permasalahan
NP-Complete
(NP
singkatan
dari
Non-Deterministik
Polinomial)
Suatu masalah dikatakan NP-Complete apabila
masalah
itu
telah
berhasil
dibuktikan
termasuk
dalam
masalah
intractable. Contohnya
adalah permasalahan pewarnaan graf.
 |