Algoritma Brute Force

Brute = Kasar,menggunakan tenaga semata,tanpa kecerdikan.
Force = kekuatan,paksaan.
Algoritma brute force adalah metode penyelesaian masalah dengan mencoba semua kemungkinan solusi yang ada secara sistematis sampai menemukan solusi yang benar.

Contoh Kasus

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

PSEUDOCODE

Berikut adalah pseudocode dengan algoritma Brute Force.

/*
// Fungsi utama untuk memulai pencarian rute
FUNGSI SolveTSP_BruteForce(daftar_kota, kota_awal)

// 1. INISIALISASI
// Buat daftar kota yang perlu dikunjungi (semua kecuali kota awal)
kota_untuk_dikunjungi = daftar_kota DIKURANGI kota_awal

        // Hasilkan semua kemungkinan urutan (permutasi) dari kota-kota yang akan dikunjungi
        semua_permutasi = HasilkanSemuaUrutan(kota_untuk_dikunjungi)

// Siapkan variabel untuk menyimpan hasil terbaik
rute_terbaik = KOSONG
        jarak_terpendek = INFINITY // Atur ke angka yang sangat besar sebagai nilai awal

// 2. PROSES ITERASI
// Loop melalui setiap kemungkinan permutasi rute
UNTUK SETIAP permutasi DALAM semua_permutasi:

// Bentuk rute perjalanan yang lengkap:
// Dimulai dari kota_awal, melewati setiap kota dalam permutasi, dan kembali ke kota_awal
rute_saat_ini = [kota_awal] + permutasi + [kota_awal]

// Hitung total jarak dari rute saat ini
jarak_saat_ini = 0
UNTUK i DARI 0 SAMPAI (panjang(rute_saat_ini) - 2):
kota_dari = rute_saat_ini[i]
kota_ke = rute_saat_ini[i+1]
jarak_saat_ini = jarak_saat_ini + AmbilJarak(kota_dari, kota_ke)

// 3. BANDINGKAN HASIL
// Jika jarak rute saat ini lebih pendek dari jarak terpendek yang pernah ditemukan
JIKA jarak_saat_ini < jarak_terpendek MAKA:
// Perbarui nilai jarak terpendek dan simpan rutenya
jarak_terpendek = jarak_saat_ini
        rute_terbaik = rute_saat_ini

// 4. KEMBALIKAN HASIL
// Setelah semua permutasi diperiksa, kembalikan rute dan jarak terbaik yang ditemukan
KEMBALIKAN rute_terbaik, jarak_terpendek

AKHIR FUNGSI

// --- CONTOH PENGGUNAAN ---

// Data berdasarkan gambar Anda
daftar_semua_kota = ["A", "B", "C", "D", "E"]
kota_mulai = "A"

// Panggil fungsi utama untuk mendapatkan hasilnya
hasil_rute, hasil_jarak = SolveTSP_BruteForce(daftar_semua_kota, kota_mulai)

// Tampilkan output
CETAK "Rute terpendek yang ditemukan adalah: ", hasil_rute
CETAK "Total jarak: ", hasil_jarak, " km"
*/
            

CODE JAVA

Berikut adalah kode java.

    import java.util.*;

public class salesMan {
    static int[][] jarak = {
            //A  B  C  D  E
            { 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
    };

    static int n = 5;
    static List kota = Arrays.asList(1, 2, 3, 4); // Kota selain A (index 0)

    static int jarakMinimal = Integer.MAX_VALUE;
    static List jalurTerbaik = new ArrayList<>();

    public static void main(String[] args) {
        permutasi(kota, 0);
        System.out.println("Rute terbaik: A -> " + konversiIndeks(jalurTerbaik) + " -> A");
        System.out.println("Total jarak minimum: " + jarakMinimal + " km");
    }
    
    static void permutasi(List arr, int k) {
        if (k == arr.size()) {
            hitungTotalJarak(arr);
        } else {
            for (int i = k; i < arr.size(); i++) {
                Collections.swap(arr, i, k);
                permutasi(arr, k + 1);
                Collections.swap(arr, k, i); 
            }
        }
    }
    
    static void hitungTotalJarak(List route) {
        int total = 0;
        int kotaTerkini = 0;

        for (int kotaSelanjutnya : route) {
            total += jarak[kotaTerkini][kotaSelanjutnya];
            kotaTerkini = kotaSelanjutnya;
        }

        total += jarak[kotaTerkini][0];

        if (total < jarakMinimal) {
            jarakMinimal = total;
            jalurTerbaik = new ArrayList<>(route);
        }
    }
    
    static String konversiIndeks(List route) {
        char[] names = {'A', 'B', 'C', 'D', 'E'};
        StringBuilder sb = new StringBuilder();
        for (int i : route) {
            sb.append(names[i]).append(" -> ");
        }
        return sb.substring(0, sb.length() - 4); 
    }
}

    

OUTPUT

dari kode di atas kami berhasil mendapatkan output.

Rute terbaik: A -> B -> D -> C -> E -> A
Total jarak minimum: 26 km

Process finished with exit code 0