Prihatiningati, Amalia Dwi (2012) Penelusuran breadth first search dan depth firs search untuk travelling salesman problem / Amalia Dwi Prihatiningat. Diploma thesis, Universitas Negeri Malang.
Full text not available from this repository.Abstract
Kata kunci Breadth First Search Depth First Search Travelling Salesman Problem. Dalam matematika terdapat banyak cabang ilmu salah satunya adalah teori graph. Salah satu contoh terapan dari teori graph adalah persoalan Travelling Salesman Problem (TSP) yaitu suatu persoalan untuk mencari sikel Hamilton dengan jumlah bobot minimum. Ada beberapa metode dalam menemukan sikel Hamilton antara lain adalah Metode Matriks Bentuk Normal dan Metode Branch and Bound. Selain itu dengan Metode Breadth First Search (BFS) dan Metode Depth First Search (DFS). Metode Breadth First Search pencarian dilakukan dengan cara menelusuri semua anak yang dibangkitkan dari simpul awal dalam setiap level secara berurutan dari kiri ke kanan.Sedangkan Metode Depth First Search pencarian dilakukan dengan cara menelusuri setiap anak pertama yang dibangkitkan dari simpul awal dari yang paling kiri hingga pada level yang paling dalam Dari hasil penyelesaian contoh TSP tidak semua persoalan TSP dapat diselesaikan dengan metode Matriks Bentuk Normal karena apabila matriks bebannya tidak dapat diubah ke dalam bentuk normal maka tidak akan diperoleh sikel Hamiltonnya. Keuntungan dari Metode BFS dan DFS dapat menghasilkan sikel Hamilton yang optimal dengan lebih dari satu sikel tetapi hanya dibalik urutannya daripada metode Mariks Bentuk Normal dan Branch and Bound. Kelemahan dari metode Matriks Bentuk Normal dan metode DFS adalah dalam pencarian solusi jumlah iterasi yang dilakukan dibutuhkan waktu yang lama. Sedangkan dengan metode Branch and Bound dan metode BFS dalam pencarian solusi jumlah iterasi yang dilakukan lebih cepat
| Item Type: | Thesis (Diploma) |
|---|---|
| Subjects: | Q Science > QA Mathematics |
| Divisions: | Fakultas Matematika dan IPA (FMIPA) > Departemen Matematika (MAT) > S1 Matematika |
| Depositing User: | library UM |
| Date Deposited: | 13 Mar 2012 04:29 |
| Last Modified: | 09 Sep 2012 03:00 |
| URI: | http://repository.um.ac.id/id/eprint/17096 |
Actions (login required)
 |
View Item |