Home
Login.
Artikelilmiahs
24351
Update
RENITA NURHAYANI
NIM
Judul Artikel
PENGGUNAAN METODE SIMPLE HILL CLIMBING DAN INDUKSI MATEMATIKA UNTUK MEMBUKTIKAN SIRKUIT TERPENDEK PERMASALAHAN TRAVELLING SALESMAN PROBLEM (TSP) PADA GRAF LENGKAP SEGI-N
Abstrak (Bhs. Indonesia)
Travelling Salesman Problem (TSP) merupakan permasalahan untuk mencari sirkuit terpendek saat mengujungi sekumpulan kota tepat satu kali dan kembali ke kota asal. Permasalahan TSP sering disebut dengan permasalahan yang Nondeterministic Polynomial-time Complete (NP-Complete) karena waktu komputasi bergantung pada banyaknya kota. Pencarian sirkuit terpendek tersebut dapat dicari dengan menggunakan metode Simple Hill Climbing. Penelitian ini membahas permasalahan TSP berbentuk graf lengkap dengan n simpul (Kn), untuk n=4,5,6,7. Jarak antar kota pada setiap graf dicari dengan menggunakan aturan cosinus. Hasil dari penelitian ini menunjukkan bahwa sirkuit terpendek pada graf lengkap dengan n simpul (Kn), untuk n=4,5,6,7, adalah sirkuit terluar dari graf. Selanjutnya, dengan menggunakan Induksi Matematika, terbukti bahwa hasil tersebut benar untuk setiap n. Hal ini dapat disimpulkan bahwa untuk memperoleh jarak sirkuit terpendek dari permasalahan TSP berbentuk graf lengkap (Kn), dapat dicari dengan menjumlahkan semua jarak pada sisi terluar dari graf.
Abtrak (Bhs. Inggris)
Traveling Salesman Problem (TSP) is a problem to find a shortest circuit while visiting a set of cities exactly once and come back to their orgin. TSP is often called as Nondeterministic Polynomial-time Complete (NP-Complete) because the computational time is dependent on the number of cities. The shortest circuit can be found by Simple Hill Climbing Method. This study discuss the TSP of a complete graph on n vertices (Kn), for n = 4, 5, 6, 7. The distance between cities in every graph is calculated by the cosine rules. The results of the study shows that the shortest circuit of complete graph on n vertice (Kn), for n = 4, 5, 6, 7, are on the outer of the graph. Furthemore, by using Mathematical Induction it is proven to be true for any n. It can be concluded that to find the distances of the shortest circuit from the TSP of complete graph (Kn), can be found by suming up the distances of all outer sides of the graph.
Kata kunci
Pembimbing 1
Pembimbing 2
Pembimbing 3
Tahun
Jumlah Halaman
Save