Home > Journal > Penggunaan Metode Branch And Bound With Search Tree Untuk Menyelesaikan Persoalan Pedagang Keliling Pada Graf Lengkap Sebagai Pengganti Metode Exhaustive Enumeration

Penggunaan Metode Branch And Bound With Search Tree Untuk Menyelesaikan Persoalan Pedagang Keliling Pada Graf Lengkap Sebagai Pengganti Metode Exhaustive Enumeration

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.


Kata Kunci: Branch, Bound, Tree, Search Tree, Branch And Bound Method, TSP, Pedagang Keliling, Graf, Graf Lengkap.
Categories: Journal
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: