Skripsi

Penelusuran breadth first search dan depth firs search untuk travelling salesman problem / Amalia Dwi Prihatiningat

Abstrak
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

Informasi Detail

DDC

Rs 511.5 PRI p

Prodi

Universitas Negeri Malang. Program Studi Matematika, 2011.

Deskripsi Fisik

viii, 84 + [3] lembar : il., tab. ; 30 cm.

Bahasa

Indonesia

No Reg

00819/KI/12

Edisi

Skripsi (Sarjana)--Universitas Negeri Malang, 2011

Subjek

1. TEORI GRAF
2. TRAVELLING SALESMAN

Pembimbing

1. SAPTI WAHYUNINGSIH ; 2. DARMAWAN SATYANANDA

Lampiran Berkas