ALGORITMA FLEURY UNTUK MENYELESAIKAN PERMASALAHAN TSP (TRAVELING SALESMAN PROBLEM)

Iin Karmila Putri

Sari


Algoritma Fleury sendiri pada dasarnya adalah salah satu metode untuk menemukan suatu jejak Euler pada suatu graf Euler dimana hal ini mirip dengan permasalahan Traveling Salesman Problem (TSP) dimana kita diharuskan menemukan jejak (rute) dari suatu titik tertentu melewati semua titik dan kembali ke titik awal sehingga penulis mencoba mengaplikasikan algoritma Fleury ini pada permasalahan Traveling Salesman Problem (TSP) dan mencoba menganalisa kompleksitas algoritma tersebut. Studi kasus pada penelitian ini berupa permasalahan tukang pos dimana tukang pos tersebut harus mendatangi beberapa tempat tepat sekali dan kembali ke tempat awal.Salah satu cara yang dapat digunakan untuk menyelesaikan permasalahan tukang pos ini adalah dengan mengkaji algoritma Fleury. Tujuan pemilihan algoritma Fleury untuk mengkonstruksi suatu sirkuit euler pada graf euler. Sirkuit euler merupakan sirkuit yang melalui masing-masing sisi tepat satu kali. Dengan demikian seorang tukang pos bisa meminimumkan jarak tempuh yang dilaluinya. Hasil yang didapatkan dengan menggunakan algoritma Fleury memungkinkan untuk mengunjungi semua titik yang ada. Hal ini dikarenakan jika tidak ada sisi yang menghubungkan titik yang akan dikunjungi dengan semua kemungkinan sisi telah dilewati maka kita dapat membuat sisi baru antara dua titik yang belum memiliki sisi. Dari sisi kompleksitas dapat dikatakan bahwa algoritma Fleury ini tidak cukup baik untuk menyelesaikan permasalahan traveling salesman problem (TSP) dikarenakan kompleksitas waktunya adalah .

Teks Lengkap:

Tidak berjudul

Refbacks

  • Saat ini tidak ada refbacks.

Article Metrics

Sari view : 55 times
Tidak berjudul - 31 times