IMPLEMENTASI DAN ANALISIS ALGORITMA DEPTH-FIRST SEARCH (DFS) DALAM PENCARIAN LINTASAN TERPANJANG SKRIPSI SHEILA EKA PUTRI S

IMPLEMENTASI DAN ANALISIS ALGORITMA DEPTH-FIRST SEARCH (DFS) DALAM PENCARIAN LINTASAN TERPANJANG

SKRIPSI

SHEILA EKA PUTRI S 070803025

DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2011

Universitas Sumatera Utara


SKRIPSI

Diajukan untuk melengkapi tugas dan memenuhi syarat mencapai gelar Sarjana Sains


DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2011


PERSETUJUAN

Judul

Kategori Nama Nomor Induk Mahasiswa Program Studi Departemen Fakultas

: IMPLEMENTASI DAN ANALISIS ALGORITMA DEPTH-FIRST SEARCH (DFS) DALAM PENCARIAN LINTASAN TERPANJANG : SKRIPSI : SHEILA EKA PUTRI S : 070803025 : SARJANA (S1) MATEMATIKA : MATEMATIKA : MATEMATIKA DAN ILMU PENGETAHUAN ALAM (FMIPA) UNIVERSITAS SUMATERA UTARA Diluluskan di Medan, Mei 2011

Komisi Pembimbing

:

Pembimbing 2

Pembimbing 1

Dra. Normalina Napitupulu, M.Sc. NIP : 19630405 198811 2 001

Prof. Dr. Tulus M.Si. NIP : 19620901 198803 1 002

Diketahui/Disetujui oleh Departemen Matematika FMIPA USU Ketua,

Prof. Dr. Tulus M.Si. NIP : 19620901 198803 1 002


PERNYATAAN


SKRIPSI

Saya mengakui bahwa skripsi ini adalah hasil kerja saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.

Medan, Mei 2011



PENGHARGAAN

Puji dan syukur penulis panjatkan kehadirat Allah SWT Yang Maha Pemurah dan Maha Penyayang, dengan limpahan kurnia-Nya skripsi ini berhasil diselesaikan dalam waktu yang telah ditetapkan. Shalawat beriring salam kepada Baginda Rasulullah SAW, sebagai rahmatan lil’alamin. Ucapan terima kasih penulis sampaikan kepada Bapak Prof. Dr. Tulus, M.Si. dan Ibu Dra. Normalina Napitupulu, M.Sc. selaku pembimbing yang telah memberikan panduan dan penuh kepercayaan kepada penulis untuk menyempurnakan kajian ini. Bapak Prof. Dr. Drs. Iryanto, M.Si. dan Bapak Syahril Efendi, S.Si., M.IT. selaku penguji yang telah memberikan kritikan dan saran yang membangun dalam penyempurnaan skripsi ini. Dekan dan Pembantu Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara. Ketua dan Sekretaris Departemen Matematika Bapak Prof. Dr. Tulus, M.Si. dan Ibu Dra. Mardiningsih, M.Si.. Seluruh staf pengajar dan staf administrasi di lingkungan Departemen Matematika, serta seluruh civitas akademika di lingkungan Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara. Ucapan terima kasih juga ditujukan kepada kedua orang tua penulis tercinta, Ayahanda (Alm.) Moch. Sjofian S. dan Ibunda Sri Wita Siregar yang telah memberikan banyak bantuan baik materi, moral maupun spiritual. Kepada saudarasaudara penulis, Adinda Nadhira Dwi Sabrina S dan Adinda Azzahra Tri Najla. Teristimewa untuk Affan H. Siregar, S.H dan Hardi Alamsyah Siregar, S.E sebagai sosok pengganti ayah dan juga tempat untuk berbagi cerita yang tak henti-hentinya memberikan bantuan, semangat dan motivasi kepada penulis dalam menyelesaikan skripsi ini dan menyelesaikan studi di Departemen Matematika FMIPA USU. Tidak terlupakan, ucapan terima kasih kepada sahabat penulis, Sylvia Ria Berlian S, Trinita Hanum, Yazeni Diana Putri, Ika Ayu Kartika Lbs. Khususnya untuk Matematika Komputasi ’07 (Mizwar Arifin dan Harizahayu), Muhammad Furqan, Muhammad Ramzi, Aghni Syahmarani, Muhammad Iqbal Pradipta, Salman Kalista serta rekan-rekan stambuk 2007 Departeman Matematika FMIPA USU, MW Family (Tracy Baumgardner, Károly Kajo Tóth, Pamela Karakula, John Patrick, Sharon Sullivan Delano dan lain-lain). Sahabat-sahabat di Ikatan Mahasiswa Matematika Muslim FMIPA USU, rekan-rekan di Himpunan Mahasiswa Matematika FMIPA USU dan kepada semua pihak yang telah memberikan bantuan dan dorongan yang tidak dapat disebutkan satu per satu. Semoga Allah SWT akan membalasnya.


ABSTRAK

Depth-First Search (DFS) adalah salah satu algoritma pencarian yang menggunakan struktur data Stack saat mencapai suatu simpul atau vertex yang terhubung dalam suatu graph. Kemampuannya dalam menemukan simpul-simpul yang belum dikunjungi memudahkan pencarian solusi optimum dalam suatu persoalan termasuk persoalan lintasan terpanjang (longest path problem). Dalam tulisan ini dibahas tentang implementasi suatu program sederhana dan menganalisis penggunaan algoritma DFS dengan pemrograman Java (penulis menggunakan NetBeans 6.9) yang bertujuan untuk memperoleh solusi optimum dari persoalan lintasan terpanjang pada graph. Hasil yang diperoleh adalah suatu solusi optimum dengan nilai maksimum pada persoalan lintasan terpanjang pada graph yang juga dapat digunakan dalam menyelesaikan permasalahan Hamiltonian Cycle (sirkuit Hamilton) dan Traveling Salesman Problem (Persoalan Pedagang Keliling). Sehingga dapat disimpulkan bahwa Hamiltonian cycle ≤ Longest Path.


IMPLEMENTATION AND ANALYSIS OF DEPTH-FIRST SEARCH (DFS) ALGORITHM FOR FINDING THE LONGEST PATH

ABSTRACT

Depth-First Search (DFS) is one of searching algorithm using data structure Stack when it reaches a node or vertex which connected in a graph. The ability of DFS to find each nodes that have not been visited simplify the searching of optimum solution in some problems include longest path problem. This paper described implementation of a simple program and analyze the use of algorithm DFS by Java programming (used NetBeans 6.9) which aims to obtain the optimum solution of the longest path problem in a graph. The result obtained an optimum solution with maximum value of the longest path problem in a graph which can also be used in solving Hamiltonian Cycle and Traveling Salesman Problem. Thus, it can be concluded that Hamiltonian cycle ≤ Longest Path.


DAFTAR ISI Halaman Persetujuan Pernyataan Penghargaan Abstrak Abstract Daftar Isi Daftar Gambar Daftar Tabel

ii iii iv v vi vii ix x

Bab 1

1

Pendahuluan 1.1 1.2

Latar Belakang Perumusan Masalah

1 2

1.3 1.4 1.5

Batasan Masalah Tinjauan Pustaka Tujuan Penelitian

3 3 5

1.6 1.7

Manfaat Penelitian Metodologi Penelitian

5 5

Bab 2

Landasan Teori 2.1 Teori Graph 2.1.1 Definisi Graph 2.1.2 Jenis Graph 2.1.2.1 Berdasarkan arah dan bobot 2.1.2.2 Berdasarkan sifat keterhubungan 2.1.3 Representasi Graph 2.2 Permasalahan Optimasi 2.2.1 Permasalahan Lintasan Terpanjang 2.3 NP-Complete 2.4 Algoritma DFS (Depth-First Search) 2.5 Kompleksitas Algoritma 2.5.1 Efisiensi Algoritma 2.5.2 Kebutuhan Waktu dan Ruang 2.5.3 Kompleksitas Waktu

7 7 7 8 8 10 11 13 14 15 17 20 21 21 21

Bab 3

Analisis dan Perancangan Aplikasi

23


3.1

Bab 4

Bab 5

Analisis Algoritma DFS Lintasan Terpanjang 3.1.1 Analisis Masukan (Input) 3.1.2 Analisis Process (Process) 3.1.3 Analisis Keluaran (Output) 3.2 Metode Perolehan Solusi Optimum 3.2.1 Dynamic Programming 3.2.2 Approximation 3.2.3 Heuristic 2-opt 3.3 Hubungan Antara Algoritma DFS dengan Metode Perolehan Solusi Optimum 3.4 Diagram Alir (Flowchart)

23 25 26 27 28 28 29 29

Hasil dan Pembahasan 4.1 Perancangan Perangkat Lunak 4.1.1 Kebutuhan Perangkat Lunak (Software) dan Perangkat Keras (Hardware) 4.2 Pengujian Aplikasi 4.2.1 Input Data 4.2.2 Perolehan Solusi Optimum Sebagai Output Data 4.2.3 Pengujian Pertama 4.2.4 Pengujian Kedua 4.2.5 Pengujian Ketiga 4.2.6 Pengujian Keempat 4.3 Tabel Data Perhitungan Jarak 4.4 Tabel Running Time program

34 34

Kesimpulan dan Saran 5.1 Kesimpulan

52 52

5.2 Saran

54

30 32

36 37 38 40 41 43 45 47 50 51

Daftar Pustaka

55

Lampiran A: Main.java Lampiran B: cityXY.java (Package tsp.java) Lampiran C: cityEdge.java (Package tsp.java)

56 67 70


DAFTAR GAMBAR

Halaman Gambar 2.1 Graph Berarah dan Berbobot

8

Gambar 2.2 Graph Berarah dan Tidak Berbobot

9

Gambar 2.3 Graph Tidak Berarah dan Berbobot

9

Gambar 2.4 Graph Tidak Berarah dan Tidak Berbobot

10

Gambar 2.5 Senarai Ketetanggaan Graph Gambar 2.1

13

Gambar 2.6 Senarai Ketetanggaan Graph Gambar 2.4

13

Gambar 2.7 Teknik Pencarian Algoritma Depth-First Search (DFS)

17

Gambar 2.8 Graph Tidak Berarah dan Tidak Berbobot abcde

19

Gambar 3.1 Contoh Graph yang Akan Ditelusuri DFS

31

Gambar 3.2 Flowchart Algoritma DFS untuk Lintasan Terpanjang

33

Gambar 4.1 Tampilan NetBeans 6.9

35

Gambar 4.2 Tampilan Output pada NetBeans 6.9

37

Gambar 4.3 Output dengan input data Random dan metode Dynamic

43

Gambar 4.4 Output dengan input data Manual dan metode Dynamic

45

Gambar 4.5 Output dengan input data Manual dan metode Approximation

47

Gambar 4.6 Output dengan input data Manual dan metode Heuristic 2-opt

49


DAFTAR TABEL

Halaman

Tabel 4.1 Data Perhitungan Jarak program pada aplikasi dalam metode perolehan solusi optimum

50

Tabel 4.2 Data Running Time program pada aplikasi dalam metode perolehan solusi optimum

51


IMPLEMENTASI DAN ANALISIS ALGORITMA DEPTH-FIRST SEARCH (DFS) DALAM PENCARIAN LINTASAN TERPANJANG SKRIPSI SHEILA EKA PUTRI S

Recommend Documents