47
2.16
Menurut definisi Kamus Besar Bahasa Indonesia, rute adalah jarak
atau arah dan jalan yang harus ditempuh
atau jalur angkutan yang
menghubungkan dua tempat.
2.17
Menurut Cormen, Leiserson, Rivest & Stein (2009:414-428),
algoritma greedy
merupakan algoritma dengan selalu mengambil solusi lokal
yang optimal dengan harapan pilihan itu mengarah pada solusi optimal
global. Metode greedy membentuk solusi langkah perlangkah:
1.
Pada setiap langkah keputusan
yang diambil merupakan keputusan
terbaik. Keputusan yang sudah diambil tidak dapat diubah pada langkah
selanjutnya.
2.
Pendekatan yang digunakan oleh Greedy adalah membuat optimum local
pada setiap langkah dan diharapkan merupakan solusi optimum global.
Metode
greedy
didasarkan pada pemindahan edge
dan pada setiap
langkah tidak memikirkan konsekuensi ke depan. Greedy tidak selalu berhasil
memberikan
solusi optimal. Tetapi pasti memberikan solusi yang mendekati
nilai optimal.
Menurut Setiadi
(2008:95-97), prinsip-prinsip metode greedy
sebagai berikut :
1.
Metode greedy mengabaikan perhitungan lengkap dalam mencari solusi.
2.
Metode greedy mencari solusi dengan cepat.
3.
Metode
greedy berguna untuk pencarian solusi yang memakan waktu
terlalu lama dengan menggunakan komputer.
Metode
greedy dapat menyelesaikan masalah knapsack problem
dimana
diberi nama sesuai dengan kantong (knapsack) yang dibawa pencuri untuk
menampung hasil curian. Pada prinsipnya masalah ini adalah masalah
optimalisasi metode dengan mencari solusi paling optimal.
a.
Fractional Knapsack problem
Masalah ini memungkinkan untuk membawa barang dalam pecahan.
b.
0-1 Knapsack problem.
Masalah
ini memungkinkan barang hanya tersedia 1 unit, dengan prinsip
take it or leave it.
 |