Abstract
Persoalan pedagang keliling merupakan persoalan yang cukup terkenal di dalam teori graf, Implementasinya sangat banyak digunakan di dalam kehidupan sehari-hari, dari masalah yang berhubungan dengan pengiriman barang sampai yang berhubungan dengan industri pabrik Oleh karena itu, saya memilih persoalan ini sebagai tema dari makalah saya. Saya juga membatasi masalah yang ada yaitu pemecahan TSP graf lengkap (Kn) untuk lebih memberikan kejelasan yang dalam. Makalah ini membahas sebuah metode yang dapat digunakan untuk menyelesaikan persoalaan pedagang keliling (TSP) pada graf lengkap. Kita dapat melihat kemampuan dari metode ini dalam memecahkan persoalaan dari segi kompleksitas waktu dan kemudahan dalam penggunaan.
Dalam pengerjaannya, metode Branch And Bound menggunakan Search Tree untuk menyimpan berbagai kemungkinan dari solusi yaitu jumlah bobot dari berbagai lintasan, dari bagian ini kemudian diolah untuk mendapatkan solusinya atau jarak dengan bobot yang minimum. Kita juga dapat melihat studi kasus dari persoalaan yang diberikan yaitu pencarian solusi dari TSP pada graf lengkap dengan derajat 5 (K5). Makalah ini juga membahas mengenai cara dasar yang digunakan untuk pemecahan TSP, yaitu algoritma pemecahan TSP dengan enumerasi secara Brute Force. Tujuannya adalah agar memberikan perbandingan mengenai dua metode tersebut. Dengan begitu kita akan mengetahui bahwa metode Branch And Bound merupakan metode yang lebih baik.
Dalam pengerjaannya, metode Branch And Bound menggunakan Search Tree untuk menyimpan berbagai kemungkinan dari solusi yaitu jumlah bobot dari berbagai lintasan, dari bagian ini kemudian diolah untuk mendapatkan solusinya atau jarak dengan bobot yang minimum. Kita juga dapat melihat studi kasus dari persoalaan yang diberikan yaitu pencarian solusi dari TSP pada graf lengkap dengan derajat 5 (K5). Makalah ini juga membahas mengenai cara dasar yang digunakan untuk pemecahan TSP, yaitu algoritma pemecahan TSP dengan enumerasi secara Brute Force. Tujuannya adalah agar memberikan perbandingan mengenai dua metode tersebut. Dengan begitu kita akan mengetahui bahwa metode Branch And Bound merupakan metode yang lebih baik.
Kata Kunci: Branch, Bound, Tree, Search Tree, Branch And Bound Method, TSP, Pedagang Keliling, Graf, Graf Lengkap.
0 comments:
Post a Comment
Leave your comment here, but not spam