ALGORITMA 2 :Menyelesaikan Masalah Sales keliling 5 kota (TSP) dengan Algoritma Brute Force_(Penjelasan mudah)

 #Apa itu TSP?

  Traveling Salesman Problem atau disingkat TSP adalah masalah klasik yang digunakan untuk menemukan Rute terpendek untuk mengunjungi lokasi yang ditentukan. 

  Masalah ini sangat relevan untuk perencanaan rute pengiriman, layanan lapangan, dan penjualan kanvas, serta solusi TSP membantu mengurangi biaya dan waktu perjalanan dengan menggunakan algoritma canggih.

 

#Apa itu Algoritma Brute Force?

  Algoritma brute force adalah pendekatan pemecahan masalah lugas yang secara sistematis memeriksa setiap kemungkinan solusi hingga solusi yang tepat ditemukan. Algoritma ini beroperasi berdasarkan prinsip pencarian menyeluruh, menjelajahi seluruh ruang solusi tanpa menggunakan optimasi, heuristik, atau jalan pintas yang cerdik.

 Brute = Kasar,menggunakan tenaga semata,tanpa kecerdikan. 

 Force = kekuatan,paksaan.

 Intinya Brute force itu jika dihubungkan dengan TSP artinya,kita coba semua keungkinan rute ,lalu pilih yang jaraknya paling kecil.

            

  #Kasus Pilihan (Kasus 1: TSP )

1) Kasus: Sales keliling 5 kota (TSP) 

 Cerita: 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 

 Tujuan: Temukan urutan kota yang harus dikunjungi agar jarak total paling kecil.  


Penyelesaian:

A. Untuk 5 kota (A sudah tetap jadi start), sisanya tinggal diacak: B, C, D, E.

Jumlah kemungkinan = 4! = 24 rute.

B. Langkah brute force

1. Buat semua kemungkinan urutan kota (B, C, D, E).

2. Hitung jarak total tiap rute (ingat: mulai dari A dan kembali ke A).

3. Bandingkan semuanya, ambil yang paling kecil.
   
   
   

 C. contoh perhitungan

Rute :Pertama 

A – B – C – D – E – A:

• A–B = 2

• B–C = 6

• C–D = 8

• D–E = 6

• E–A = 7

Total = 2 + 6 + 8 + 6 + 7 = 29

Rute: Kedua

 A – B – E – D – C – A:

• A–B = 2

• B–E = 3

• E–D = 6

• D–C = 8

• C–A = 9
     

Total = 28

Rute:ketiga

 A – B – D – C – E – A

• A–B = 2

• B–D = 4

• D–C = 8

• C–E = 5

• E–A = 7

Total = 2 + 4 + 8 + 5 + 7 = 26 (terbaik)

Nanti semua kemungkinan dihitung, hasil terkecilnya itulah solusi.

#Contoh Kodingan

#PSEUDOCODE

ALGORITMA TSP_BruteForce

DEKLARASI:

    wahyuni1 : matriks jarak antar kota

    wahyuni2 : daftar nama kota

    wahyuni3 : daftar kota yang akan dipermutasi (selain kota awal A)

    wahyuni4 : jarak minimum (isi awal = tak hingga)

    wahyuni5 : rute terbaik

    wahyuni6 : semua permutasi kota

LANGKAH:

1. Inisialisasi matriks jarak wahyuni1

2. Inisialisasi daftar nama kota wahyuni2 = {A, B, C, D, E}

3. Inisialisasi wahyuni3 = {1, 2, 3, 4}   // kota selain A

4. Set wahyuni4 = ∞ (tak hingga)

5. Set wahyuni5 = kosong

6. Bangkitkan semua permutasi dari wahyuni3 → simpan ke wahyuni6

7. UNTUK setiap rute (wahyuni8) dalam wahyuni6 LAKUKAN:

       a. Set total_jarak (wahyuni9) = 0

       b. Set posisi_awal (wahyuni10) = 0   // mulai dari kota A

       c. UNTUK setiap kota (wahyuni11) dalam rute:

             total_jarak = total_jarak + wahyuni1[posisi_awal][wahyuni11]

             posisi_awal = wahyuni11

       d. Tambahkan jarak kembali ke A:

             total_jarak = total_jarak + wahyuni1[posisi_awal][0]

       e. JIKA total_jarak < wahyuni4:

             wahyuni4 = total_jarak

             wahyuni5 = rute (wahyuni8)

8. CETAK "Rute terbaik: A -> (isi wahyuni5) -> A"

9. CETAK "Total jarak: " + wahyuni4

SELESAI