Algoritma 3 : Menyelesaikan TSP menggunakan algoritma Greedy

Apa itu Algoritma Greedy?

     Algoritma Greedy (Rakus) adalah suatu metode penyelesaian masalah dengan cara memilih keputusan terbaik (optimal) pada setiap langkah kecil, tanpa mempertimbangkan dampak jangka panjang dari keputusan tersebut.

Prinsip:

• Pada setiap tahap, algoritma akan memilih opsi yang terlihat paling menguntungkan saat itu.
• Dengan selalu mengambil pilihan terbaik lokal (local optimum), hasil akhirnya diharapkan juga menjadi solusi terbaik global (global optimum).

Mengapa disebut "Rakus"?

Disebut rakus karena algoritma ini selalu "serakah", yaitu langsung mengambil pilihan terbaik yang tersedia pada saat itu tanpa menunggu atau memikirkan konsekuensi ke depannya.

• Seperti orang yang rakus: begitu ada sesuatu yang menguntungkan di depan mata, langsung diambil.
• Kadang cara ini berhasil memberikan solusi optimal, tapi ada juga kasus di mana hasilnya hanya mendekati optimal (bukan benar-benar terbaik).

Contoh penyelesaian kasus Traveling Sales Problem(TSP) dengan Algoritma Greedy

Masalah: Ada seorang sales yang harus mengunjungi semua kota (A, B, C, D, E) sekali saja, lalu pulang ke kota awal (A). Dia ingin mencari rute dengan jarak paling pendek.

Data jarak antar kota:

• A ke B = 2 km, A ke C = 9 km, A ke D = 10 km, A ke E = 7 km
• B ke C = 6 km, B ke D = 4 km, B ke E = 3 km
• C ke D = 8 km, C ke E = 5 km
• D ke E = 6 km

Penyelesaian Rute dengan Algoritma Greedy (Nearest-Neighbor)

1. Mulai dari A: tujuan terdekat adalah B (2 km).
   Rute: A → B
   Total Jarak: 2
2. Dari B: kota terdekat adalah E (3 km).
   Rute: A → B → E
   Total Jarak: 5
3. Dari E: pilih C (5 km).
   Rute: A → B → E → C
   Total Jarak: 10
4. Dari C: tersisa D (8 km).
   Rute: A → B → E → C → D
   Total Jarak: 18
5. Kembali ke A: dari D ke A (10 km).
   Rute: A → B → E → C → D → A
   Total Jarak: 28

Hasil Akhir

Jadi, rute yang ditemukan menggunakan algoritma greedy dengan titik awal di A adalah:

A → B → E → C → D → A

Total jarak tempuh untuk rute ini adalah 28 km.

PSEUDOCODE

Algoritma Greedy_TSP

Input     : Graf dengan himpunan kota {A, B, C, D, E} dan jarak antar kota

Output  : Rute perjalanan terpendek menurut algoritma greedy

1. Mulai dari kota awal ( A)
2. Tandai kota awal sebagai "sudah dikunjungi"
3. kota_sekarang ← A
4. total_jarak ← 0
5. rute ← [A]
6. Selama masih ada kota yang belum dikunjungi:
   • Dari kota_sekarang, cari kota terdekat yang belum dikunjungi
   • Pindah ke kota tersebut
   • Tambahkan kota tersebut ke dalam rute
   • Tambahkan jaraknya ke total_jarak
   • Tandai kota tersebut sebagai "sudah dikunjungi"
   • kota_sekarang ← kota terpilih
7. Setelah semua kota dikunjungi:
   • Kembali ke kota awal (A)
   • Tambahkan jaraknya ke total_jarak
   • Tambahkan A ke dalam rute
8. Tampilkan rute dan total_jarak
9. Selesai

CONTOH KODE JAVA

public class TSPGreedy {
    static int jumlahKota= 5; // jumlah kota
    static String[] kota = {"A", "B", "C", "D", "E"};

    public static void main(String[] args) {
        // Matriks jarak antar kota
        int[][] jarak = {
                {0, 2, 9, 10, 7},  // A
                {2, 0, 6, 4, 3},   // B
                {9, 6, 0, 8, 5},   // C
                {10, 4, 8, 0, 6},  // D
                {7, 3, 5, 6, 0}    // E
        };

        int start = 0; // mulai dari kota A (indeks 0)
        boolean[] dikunjungi = new boolean[jumlahKota];
        dikunjungi[start] = true;

        int totalJarak = 0;
        int sekarang= start;

        System.out.print("Rute: " + kota[start]);

        // kunjungi semua kota sekali
        for (int step = 1; step < jumlahKota; step++) {
            int nextKota = -1;
            int minJarak = Integer.MAX_VALUE;

            // cari kota terdekat yang belum dikunjungi
            for (int j = 0; j < jumlahKota; j++) {
                if (!dikunjungi[j] && jarak[sekarang][j] < minJarak) {
                    minJarak = jarak[sekarang][j];
                    nextKota = j;
                }
            }

            // pergi ke kota terdekat
            dikunjungi[nextKota] = true;
            totalJarak += minJarak;
            System.out.print(" → " + kota[nextKota]);
           sekarang = nextKota;
        }

        // kembali ke kota awal
        totalJarak += jarak[sekarang][start];
        System.out.print(" → " + kota[start]);

        // hasil total jarak
        System.out.println("\nTotal jarak: " + totalJarak + " km");
    }
}

HASIL RUN PROGRAM