Skripsi

Implementasi algoritma backtracking dengan menggunakan metode DFS (Depth First Search) pada penyelesaian traveling salesman problem suatu digraph / Pipin Mega Ayuning Tyas

Abstrak
Kata kunci Algoritma Backtracking Traveling Salesman Problem. Teori graph merupakan salah satu cabang matematika yang banyak dimanfaatkan dalam memecahkan masalah dalam kehidupan sehari - hari. Salah satu terapannya adalah Traveling Salesman Problem yaitu permasalahan dari salesman yang ingin menyelesaikan perjalanannya dimulai dari kota asal salesman berada lalu berkunjung ke kota-kota yang dituju dan kembali ke kota asal salesman berada tadi dengan rute terpendek. Dengan kata lain permasalahan TSP adalah permasalahan menemukan sikel Hamilton. Persoalan TSP tidak hanya dapat diperlakukan untuk masalah graph tida berarah saja tetapi juga untuk graph berarah dan graph komplit maupun graph tidak komplit. Salah satu teknik yang dapat digunakan untuk mempercepat pencarian solusi adalah dengan teknik pencarian pada pohon ruang status. Teknik ini selalu dapat memecahkan masalah dan jika ada beberapa solusi maka dapat diketahui seluruh solusi yang ada. Algoritma yang menggunakan teknik ini salah satunya adalah Algoritma Backtracking yang dibahas pada skripsi ini. Algoritma Backtracking ini melakukan penelusuran dengan menggunakan metode DFS (Depth First Search). Penelusuran dimulai dari satu simpul awal kemudian membangkitkan simpul berikutnya yang merupakan solusi. Solusi ini ditentukan oleh fungsi pembatas yang telah ditentukan sebelumnya. Apabila bukan solusi maka simpul tersebut tidak diperhitungkan atau akan dimatikan dan akan dilakukan backtrack ke simpul sebelumnya begitu seterusnya hingga semua simpul telah dibangkitkan dan telah ditemukan solusinya. Dari hasil penyelesaian contoh TSP dengan menggunakan metode matriks bentuk normal metode branch and bound dan algoritma baktracking diperoleh sikel hamilton dan bobot minimum yang sama. Algoritma Backtracking juga dapat menemukan lebih banyak solusi daripada algoritma lain tetapi tidak semua yang diselesaikan dengan metode branch and bound dan algoritma backtracking dapat diselesaikan juga dengan metode matriks bentuk normal. Pada matriks bentuk normal berlaku pada jenis digraph tertentu saja. Dengan demikian algoritma baktracking dalam skripsi ini dapat digunakan sebagai alternatif. Untuk lebih mudahnya algoritma backtracking algoritma branch and bound dan metode matriks bentuk normal diimplementasikan ke dalam sebuah program dengan menggunakan bahasa pemrograman Borland Delphi 7.0.

Informasi Detail

DDC

Rs 511.8 TYA i

Prodi

Universitas Negeri Malang. Program Studi Matematika, 2010.

Deskripsi Fisik

vi, 80 lembar : il. , tab. ; 30 cm.

Bahasa

Indonesia

No Reg

04072/KI/10

Edisi

Skripsi (Sarjana)--Universitas Negeri Malang. 2010

Subjek

1. ALOGARITMA - IMPLEMENTASI
2. TEORI GRAPH

Pembimbing

1. Sapti Wahyuningsih 2. Darmawan Satyananda

Lampiran Berkas