Solusi Travelling Salesman Problem dengan metode Brute Force

Travelling Salesman Problem (TSP) merupakan masalah Nondeterministic Polynomial-sulit di dalam optimasi kombinatorial yang dipelajari di dalam riset operasi dan ilmu komputer teoritis. Contoh kasus adalah bandara. Diketahui daftar bandara dan jarak antar bandara, tugasnya adalah untuk mencari kemungkinan tur terpendek yang mengunjungi setiap bandara tepat satu kali kemudian kembali ke bandara awal. Solusi dengan metode brute force adalah dengan memeriksa semua kemungkingan cara untuk mengunjungi seluruh bandara lainnya dari bandara awal dan kemudian kembali ke bandara awal.
Algoritma Travelling Salesman Problem metode brute force berikut memiliki O(n!) (baca: big O sebesar n faktorial):
1. nodes1 = daftar semua nodes (vertex) kecuali nodes / bandara pertama (nodes[0])
2. urutkan nodes1
3. n = jumlah permutasi untuk nodes1 ( = jumlah permutasi siklis untuk nodes )
4. t = tak hingga / unlimited
5. For j=0 to j<n
s=0
length = jarak antara nodes[0] dengan nodes1[0]
for i=0 to j<jumlah nodes-1
length = jarak antara nodes1[i] dengan nodes1[i+1]
next i
end for
length = jarak antara nodes1 index terakhir dengan nodes index 0
s = sum of length above (total length di atas)
if s<t then
t=s
temp index 0 dan terakhir = nodes[0]
selain itu temp = nodes1
end if
permutasikan nodes1
next j
end for
kita dapatkan t adalah jarak total minimum dan temp adalah sirkuit terpendek

Contoh:
Input:
Bandara (x,y)
Juanda (300,200)
Halim (200,200)
Changi (200,90)
King (50,60)
Aust (450,400)

Output:
juanda-aust-changi-halim-king-juanda=1249
juanda-aust-changi-king-halim-juanda=1105
juanda-aust-halim-changi-king-juanda=1118
juanda-aust-halim-king-changi-juanda=1075
juanda-aust-king-changi-halim-juanda=1136
juanda-aust-king-halim-changi-juanda=1237
juanda-changi-aust-halim-king-juanda=1357
juanda-changi-aust-king-halim-juanda=1375
juanda-changi-halim-aust-king-juanda=1388
juanda-changi-halim-king-aust-juanda=1237
juanda-changi-king-aust-halim-juanda=1244
juanda-changi-king-halim-aust-juanda=1075
juanda-halim-aust-changi-king-juanda=1256
juanda-halim-aust-king-changi-juanda=1244
juanda-halim-changi-aust-king-juanda=1418
juanda-halim-changi-king-aust-juanda=1136
juanda-halim-king-aust-changi-juanda=1375
juanda-halim-king-changi-aust-juanda=1105
juanda-king-aust-changi-halim-juanda=1418
juanda-king-aust-halim-changi-juanda=1388
juanda-king-changi-aust-halim-juanda=1256
juanda-king-changi-halim-aust-juanda=1118
juanda-king-halim-aust-changi-juanda=1357
juanda-king-halim-changi-aust-juanda=1249
jarak total minimum = 1075. Sirkuit terpendek adalah -juanda–aust–halim–king–changi–juanda-