Algoritma Greedy
Algoritma Greedy
Algoritma Greedy adalah salah satu teknik penyelesaian masalah dalam pemrograman yang bekerja dengan cara memilih
solusi terbaik secara lokal pada setiap langkah dengan harapan hasil akhirnya akan menjadi solusi optimal secara
global.
Dengan kata lain:
- Setiap langkah → pilih keputusan yang paling menguntungkan saat itu (best choice for now).
- Tidak ada backtracking → keputusan yang sudah diambil tidak diubah lagi.
Algoritma greedy dapat menyelesaikan permasalahan dengan cepat. Namun, perlu digaris bawahi bahwa algoritma greedy tidak selamanya menghasilkan output terbaik. Kali ini penulis akan mencoba menyelesaikan masalah Traveling Salesman Problem(TSP) dengan algoritma greedy. Bahasa pemrograman yang penulis gunakan adalah bahasa java.
Pseudo Code
// Inisialisasi variabel global atau atribut kelas
VARIABLES:
kota (integer) // Jumlah total kota
jarak (2D integer array) // Matriks untuk menyimpan jarak antar kota
// Fungsi utama program
MAIN:
jumlahKota = 5
sales = CREATE new greedy object with jumlahKota
// Mengisi matriks jarak dengan data
CALL sales.kotaDanJarak(0, 1, 2) // A ke B
CALL sales.kotaDanJarak(0, 2, 9) // A ke C
... (dan seterusnya untuk semua jarak)
// Memulai pencarian rute dari kota A (indeks 0)
CALL sales.mencariJarakTerpendek(0)
END MAIN
// Fungsi untuk membuat objek dan inisialisasi
CONSTRUCTOR greedy(jumlahKota):
this.kota = jumlahKota
this.jarak = CREATE new 2D integer array of size [jumlahKota][jumlahKota]
END CONSTRUCTOR
// Fungsi untuk mencatat jarak antara dua kota
FUNCTION kotaDanJarak(kotaAwal, kotaTujuan, jarakKota):
jarak[kotaAwal][kotaTujuan] = jarakKota
jarak[kotaTujuan][kotaAwal] = jarakKota
END FUNCTION
// Fungsi utama untuk menjalankan algoritma greedy
FUNCTION mencariJarakTerpendek(kotaAwal):
// Persiapan
cekKota = CREATE new boolean array of size [kota], all values false
jalan = CREATE new empty Stack
totalJarak = 0
lokasiSaatIni = kotaAwal
// Langkah awal
PUSH lokasiSaatIni TO jalan
cekKota[lokasiSaatIni] = true
// Loop utama untuk mengunjungi semua kota
WHILE size of jalan < kota:
tetanggaTerdekat = -1
jarakTerdekat = a very large number (infinity)
// Cari tetangga terdekat yang belum dikunjungi
FOR tetangga FROM 0 TO kota-1:
IF cekKota[tetangga] is false AND jarak[lokasiSaatIni][tetangga] < jarakTerdekat:
jarakTerdekat = jarak[lokasiSaatIni][tetangga]
tetanggaTerdekat = tetangga
END IF
END FOR
// Pindah ke tetangga terdekat jika ditemukan
IF tetanggaTerdekat is not -1:
cekKota[tetanggaTerdekat] = true
PUSH tetanggaTerdekat TO jalan
totalJarak = totalJarak + jarakTerdekat
lokasiSaatIni = tetanggaTerdekat
END IF
END WHILE
// Kembali ke kota awal
kotaTerakhir = PEEK from jalan
totalJarak = totalJarak + jarak[kotaTerakhir][kotaAwal]
PUSH kotaAwal TO jalan
// Tampilkan hasil
CALL hasil(jalan, totalJarak)
END FUNCTION
// Fungsi untuk mencetak hasil akhir
FUNCTION hasil(jalan, totalJarak):
PRINT "Rute yang ditemukan "
rute = CREATE new empty List of Strings
FOR EACH namaKota IN jalan:
// Ubah indeks (0, 1, 2...) menjadi huruf ('A', 'B', 'C'...)
hurufKota = CONVERT (character('A') + namaKota) TO String
ADD hurufKota TO rute
END FOR
PRINT rute joined with "->"
PRINT "total jarak tempuh " + totalJarak + "Km"
END FUNCTION
Code Java
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class greedy {
private int kota;
private int jarak[][];
public static void main(String[] args) {
int jumlahkota = 5;
greedy sales = new greedy(jumlahkota);
sales.kotaDanJarak(0, 1, 2); // A ke B
sales.kotaDanJarak(0, 2, 9); // A ke C
sales.kotaDanJarak(0, 3, 10); // A ke D
sales.kotaDanJarak(0, 4, 7); // A ke E
sales.kotaDanJarak(1, 2, 6); // B ke C
sales.kotaDanJarak(1, 3, 4); // B ke D
sales.kotaDanJarak(1, 4, 3); // B ke E
sales.kotaDanJarak(2, 3, 8); // C ke D
sales.kotaDanJarak(2, 4, 5); // C ke E
sales.kotaDanJarak(3, 4, 6); // D ke E
sales.mencariJarakTerpendek(0);
}
public greedy(int kota) {
this.kota = kota;
jarak = new int[kota][kota];
}
public void kotaDanJarak(int kotaAwal, int kotaTujuan, int jarakKota) {
jarak[kotaAwal][kotaTujuan] = jarakKota;
jarak[kotaTujuan][kotaAwal] = jarakKota;
}
public void mencariJarakTerpendek(int kotaAwal) {
boolean[] cekKota = new boolean[kota];
Stack jalan = new Stack<>();
int totalJarak = 0;
int lokasiSaatIni = kotaAwal;
jalan.push(lokasiSaatIni);
cekKota[lokasiSaatIni] = true;
while (jalan.size() < kota) {
int tetanggaTerdekat = -1;
int jarakTerdekat = Integer.MAX_VALUE;
for (int tetangga = 0; tetangga < kota; tetangga++) {
if (!cekKota[tetangga] && jarak[lokasiSaatIni][tetangga] < jarakTerdekat) {
jarakTerdekat = jarak[lokasiSaatIni][tetangga];
tetanggaTerdekat = tetangga;
}
}
if (tetanggaTerdekat != -1) {
cekKota[tetanggaTerdekat] = true;
jalan.push(tetanggaTerdekat);
totalJarak += jarakTerdekat;
lokasiSaatIni = tetanggaTerdekat;
}
}
int kotaTerakhir = jalan.peek();
totalJarak += jarak[kotaTerakhir][kotaAwal];
jalan.push(kotaAwal);
hasil(jalan, totalJarak);
}
void hasil(Stack jalan, int totalJarak) {
System.out.print("Rute yang ditemukan ");
List rute = new ArrayList<>();
for (Integer namaKota : jalan) {
rute.add(String.valueOf((char) ('A' + namaKota)));
}
System.out.println(String.join("->", rute));
System.out.println("total jarak tempuh " + totalJarak + "Km");
}
}
Dari kode di atas, penulis menyimpulkan bahwa cara kerja algoritma greedy untuk TSP adalah sebagai berikut.
- Mulai dari Kota A: Ini adalah titik awal kita.
- Dari A, Cari Kota Terdekat:
- A ke B = 2 km <-- Pilihan termurah
- A ke C = 9 km
- A ke D = 10 km
- A ke E = 7 km
- Rute sementara: A → B (Jarak: 2)
- Dari B, Cari Kota Terdekat (yang belum dikunjungi):
- B ke C = 6 km
- B ke D = 4 km
- B ke E = 3 km <-- Pilihan termurah
- Rute sementara: A → B → E (Jarak: 2 + 3 = 5)
- Dari E, Cari Kota Terdekat (yang belum dikunjungi):
- E ke C = 5 km <-- Pilihan termurah
- E ke D = 6 km
- Rute sementara: A → B → E → C (Jarak: 5 + 5 = 10)
- Dari C, Kota Terakhir yang Tersisa:
- Satu-satunya kota yang belum dikunjungi adalah D.
- Rute sementara: A → B → E → C → D (Jarak: 10 + 8 = 18)
- Kembali ke Kota Awal:
- Dari D, kembali ke A. Jaraknya adalah 10 km.
- Rute final: A → B → E → C → D → A
- Total Jarak: 18 + 10 = 28 km
Setelah melewati proses tersebut, penulis mendapatkan hasil sebagai berikut.
Rute yang ditemukan A->B->E->C->D->A
total jarak tempuh 28Km
Process finished with exit code 0
Sebelumnya penulis juga pernah menyelesaikan masalah TSP yang sama dengan menggunakan algoritma brute force. Output yang dihasilkan adalah:
Rute terpendek: A -> B -> D -> C -> E -> A
Total jarak: 26 km
Process finished with exit code 0
Dari perbedaan, diatas penulis mengambil kesimpulan bahwa algoritma brute force lebih efektif untuk mencari rute terpendek dalam masalah TSP tersebut. Penulis menyimpulkan bahwa hal ini disebabkan karena algoritma greedy mencari solusi optimal dengan memecah masalah lalu mencari solusi optimal untuk setiap pecahan masalah(sub-optimal). Hal ini memang merupakan resiko dari menggunakan algoritma greedy. Perlu diketahui bahwa seluruh algoritma diciptakan untuk penyelesaian masalah yang berbeda. Untuk masalah TPS ini, algoritma greedy tidak menyelesaikan masalah secara optimal. Namun untuk masalah yang berbeda mungkin algoritma greedy bisa lebih optimal dari algoritma lainnya.
Komentar
Posting Komentar