Tyas, Pipin Mega Ayuning (2010) Implementasi algoritma backtracking dengan menggunakan metode DFS (Depth First Search) pada penyelesaian traveling salesman problem suatu digraph / Pipin Mega Ayuning Tyas. Diploma thesis, Universitas Negeri Malang.
Full text not available from this repository.Abstract
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.
| Item Type: | Thesis (Diploma) |
|---|---|
| Subjects: | Q Science > QA Mathematics |
| Divisions: | Fakultas Matematika dan IPA (FMIPA) > Departemen Matematika (MAT) > S1 Matematika |
| Depositing User: | Users 2 not found. |
| Date Deposited: | 05 Nov 2010 04:29 |
| Last Modified: | 09 Sep 2010 03:00 |
| URI: | http://repository.um.ac.id/id/eprint/17907 |
Actions (login required)
 |
View Item |