SIMULASI PENCARIAN JARAK TERDEKAT (SHORTEST PATH) DENGAN MENGGUNAKAN ALGORITMA A* (STUDI KASUS PADA PERPUSTAKAAN POLITEKNIK NEGERI MEDAN)
SKRIPSI
DINA SYAHFITRI 101421030
PROGRAM STUDI EKSTENSI S1 ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2012
Universitas Sumatera Utara
SIMULASI PENCARIAN JARAK TERDEKAT (SHORTEST PATH) DENGAN MENGGUNAKAN ALGORITMA A* (STUDI KASUS PADA PERPUSTAKAAN POLITEKNIK NEGERI MEDAN)
SKRIPSI
Diajukan untuk melengkapi tugas dan memenuhi syarat mencapai gelar Sarjana Komputer
DINA SYAHFITRI 101421030
PROGRAM STUDI S1 EKSTENSI ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2012
Universitas Sumatera Utara
ii
PERSETUJUAN
Judul
Kategori Nama Nomor Induk Mahasiswa Program Studi Departemen Fakultas
: SIMULASI PENCARIAN JARAK TERDEKAT (SHORTEST PATH) DENGAN MENGGUNAKAN ALGORITMA A* (STUDI KASUS PADA PERPUSTAKAAN POLITEKNIK NEGERI MEDAN) : SKRIPSI : DINA SYAHFITRI : 101421030 : S1 EKSTENSI ILMU KOMPUTER : ILMU KOMPUTER : ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA
Diluluskan di Medan, September 2012
Komisi Pembimbing: Pembimbing 2
Pembimbing 1
Drs. Nasir Saleh, M.Si NIP. 19580611 198603 1 002
Drs. Agus Salim Harahap, M.Si NIP. 19540828 198103 1004
Diketahui/Disetujui oleh Departemen Ilmu Komputer Fasilkom-TI USU Ketua,
Dr.Poltak Sihombing, M.Kom NIP 19620317 199103 1 001
Universitas Sumatera Utara
iii
PERNYATAAN
SIMULASI PENCARIAN JARAK TERDEKAT (SHORTEST PATH) DENGAN MENGGUNAKAN ALGORITMA A* (STUDI KASUS PADA PERPUSTAKAAN POLITEKNIK NEGERI MEDAN) SKRIPSI
Penulis mengakui bahwa skripsi ini adalah hasil kerja penulis sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.
Medan, September 2012
DINA SYAHFITRI 101421030
Universitas Sumatera Utara
iv
PENGHARGAAN
Puji dan syukur penulis ucapkan kepada Tuhan Yang Maha Esa yang telah memberikan kesempatan dan kesehatan hingga akhirnya penulis dapat menyelesaikan skripsi ini dan diselesaikan tepat pada waktunya sesuai dengan instruksi dan peraturan yang berlaku di Fakultas Ilmu Komputer dan Teknologi Informasi. Skripsi ini disusun sebagai salah satu syarat untuk menyelesaikan pendidikan S1 Ilmu Komputer Fakultas Ilmu Komputer dan Teknologi Informasi. Selama penulisan skripsi ini, penulis menyadari bahwa banyak terdapat kesalahankesalahan yang mungkin terjadi, baik dari segi teknik, tata penyajian ataupun dari segi tata bahasa. Oleh karena itu penulis bersedia menerima kritik dan saran dari pembaca dalam upaya perbaikan tugas akhir ini. Dalam kesempatan ini penulis ingin menyampaikan ucapan terima kasih kepada: 1. Bapak Drs. Agus Salim Harahap, M.Si, selaku Pembimbing I dan Bapak Drs.James Piter Marbun, M.Kom selaku Pembimbing II dimana saat penyusunan skripsi telah banyak memberikan bimbingan dan pengarahan kepada penulis selama menyusun skripsi ini. Ucapan terima kasih juga penulis ucapkan kepada Bapak Ade Chandra, ST, M.Kom dan Bapak Syurahbil, S.Si,M.CompSc sebagai dosen Pembanding I dan dosen Pembanding II yang telah memberikan banyak masukan terhadap skripsi penulis. 2. Bapak Dr. Poltak Sihombing, M.Kom, selaku Ketua Program Studi S1 Ilmu Komputer, Dekan Fakultas Ilmu Komputer dan Teknologi Informasi Bapak Prof. Muhammad Zarlis, Pembantu Dekan Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara, dan semua dosen pada Departemen Ilmu Komputer Fakultas Ilmu Komputer dan Teknologi Informasi, 3. Kepada kedua orang tua penulis, yaitu Bapak penulis Res Tarigan dan ibunda Rita Sitepu yang telah memberikan dukungan moril dan materil serta doa yang tidak ternilai kepada penulis sehingga dapat menyelesaikan skripsi ini. 4. Adi Pratama Tarigan, Amd (Kakak laki-laki) yang selalu memberikan dukungan dan semangat kepada penulis. 5. Pegawai di Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara serta rekan-rekan kuliah Program Ekstensi S1 Ilmu Komputer Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara. 6. Teman-teman di Aplisit IT Solution Centre Medan yang telah memberikan dukungan dan waktu saat penyelesaian skripsi ini.
Universitas Sumatera Utara
v
ABSTRAK
Komputer banyak digunakan untuk melakukan pencarian lintasan terpendek (shortestpath), yang ditampilkan dalam model simulasi. Simulasi adalah model dari suatu sistem yang nyata, melakukan pengolahan data terhadap model tersebut dan mengevaluasi hasil simulasi tersebut. Simulasi juga merupakan teknik untuk menyelesaikan persoalan melalui pengolahan data yang nyata untuk memperoleh output berupa solusi persoalan ataupun sebagai bahan masukan dalam rangka pengembangan dan perbaikan struktur dan operasi sistem yang nyata. Pada penelitian ini dilakukan studi kasus pencarian rute terpendek antar rak-rak buku pada perpustakaan Politeknik Negeri Medan. Ide dari penelitian ini berawal dari masalah kecepatan pencarian sebuah buku yang diperlukan mahasiswa. Faktor kecepatan pencarian buku pada sebuah perpustakaan adalah sangat penting untuk mencegah antrian mahasiswa yang mencari buku di perpustakaan. Pencarian rute terpendek ini memfokuskan untuk mencari lokasi buku di perpustakaan berdasarkan kategori yang disimbolkan dengan sebuah titik (vertex). Algoritma yang digunakan untuk penceraian jarak terpendek adalah A*. Hasil yang diperoleh dalam pencarian jarak terpendek antar verteks adalah rute-rute yang dilalui serta total jarak. Kata Kunci : Shortest Path, Graf, Algoritma A*
Universitas Sumatera Utara
vi
SIMULATION OF THE NEAREST DISTANCE SEARCH (SHORTEST PATH) BY USING A * ALGORITHM (CASE STUDY IN THE LIBRARY OF STATE POLYTECHNIC OF MEDAN)
ABSTRACT
It is not that existence of computer today used in seeking the shortest path which by displaying them in a simulation model. The Simulation is a truly model for the system as required, there also do data processing on the model itself and also to evaluate the outcome of the simulation. The simulation also known as a technique in order to settle out any problems through the data processing as truly in order to get output well known as solution to the problem or as inputs in order to making an improvement and repairmen to the structure and operation of system available. On this research, it was conducted a case study with seeking a shortest path amongst the book racks available on Politeknik Negeri Medan. The Idea of this research originally from the matter of speed in seeking the book in a library is very important thing, this is in order to avoid any queue for students in looking for any book in a library house. In seeking this shortest path focused on looking for location of books in the library house based on category as symbolized with a vertex. The algorism as used for seeking the shortest path is notated with A*. The outcome as obtained in seeking the shortest path between vertex are the routes that always be passed by and on total distance.
Keywords : Shortest path, Graph. Algorism A*
Universitas Sumatera Utara
vii
DAFTAR ISI
Halaman Persetujuan Pernyataan Penghargaan Abstrak Abstract Daftar Isi Daftar Tabel Daftar Gambar
ii iii iv vi vii viii xi xiii
Bab 1 Pendahuluan 1.1 Latar Belakang ………………………………………………………… 1.2 Perumusan masalah 1.3 Batasan Masalah 1.4 Tujuan Penelitian 1.5 Manfaat Penelitian 1.6 Metodologi Penelitian 1.7 Sistematika Penulisan
1 1 2 2 3 3 3 4
Bab 2 Tinjauan Pustaka 2.1 Pengertian Graf 2.1.1 Jenis – Jenis Graf 2.2 Lintasan Terpendek (Shortest Path) 2.3 Algoritma A* 2.3.1 Fungsi Heuristik untuk A* 2.4 Pengertian Database 2.5 Microsoft Visual Basic 2.6 Flow Chart 2.7 Simulasi 2.7.1 Manfaat Simulasi 2.8.2 Jenis – Jenis Simulasi
5 5 6 10 10 11 12 15 16 17 18 19
Bab 3 Analisis dan Perancangan 3.1 Analisis 3.1.1 Analisis Algoritma A* 3.1.2 Flowchart Algoritma A* 3.1.3 Deskripsi Sistem 3.1.4 Spesifikasi Keperluan Sistem 3.1.5 Fungsi Sistem 3.1.6 Tujuan Sistem
22 22 22 35 36 37 37 37
Universitas Sumatera Utara
viii
3.2
3.1.7 Masukan dan Keluaran Sistem 3.1.8 Batasan Sistem 3.1.9 Data Flow Diagram (DFD) Perancangan 3.2.1 Perancangan Database 3.2.2 Perancangan Relasi Antar Tabel 3.2.3 Perancangan Antarmuka Pengguna (User Interface) 3.2.3.1 Rancangan Login 3.2.3.2 Rancangan Home 3.2.3.3 Rancangan Sortest Path 3.2.3.4 Rancangan Data 3.2.3.5 Rancangan Edit Rute dan Jarak 3.2.3.6 Rancangan Edit Titik 3.2.3.7 Rancangan Data User 3.2.3.8 Rancangan Help 3.2.3.9 Rancangan About
37 38 38 43 43 45 45 46 46 48 48 49 50 50 51 52
Bab 4 Implementasi dan Pengujian 4.1 Implementasi 4.1.1 Tampilan Antarmuka 4.1.1.1 Tampilan Home 4.1.1.2 Tampilan Otorisasi 4.1.1.3 Tampilan Login 4.1.1.4 Tampilan Logout 4.1.1.5 Tampilan Shortest Path 4.1.1.6 Tampilan Menu Data 4.1.1.7 Tampilan Menu Data Jarak & Vertek 4.1.1.8 Tampilan Edit Data Verteks Jarak 4.1.1.9 Tampilan Edit Vertkes 4.1.1.10 Tampilan Data User 4.1.1.11 Laporan Hasil Pengujian 4.1.1.12 Tampilan Help 4.1.1.13 Tampilan About 4.2 Pengujian Sistem 4.2.1 Pengujian Sistem 4.2.2 Laporan Pengujian Sistem
53 53 53 54 55 55 56 56 57 57 57 58 59 59 60 60 61 60 62
Bab 5 Penutup 5.1 Kesimpulan 5.2 Saran
63 63 63
Daftar Pustaka Lampiran
Universitas Sumatera Utara
ix
DAFTAR TABEL
No. Tabel
Nama Tabel
Halaman
2.1
Simbol – Simbol Flowchart Program
17
3.1
Manhattan Distance masing – masing Verteks pada Peta Perpustakaan
26
3.2
Spesifikasi Proses DFD Level 1
40
3.3
Kamus Data Pada DFD Level 1
40
3.4
Spesifikasi Proses DFD Level 2 Proses 1
41
3.5
Kamus Data Pada DFD Level 2
41
3.6
Tabel tUser
43
3.7
Tabel tKategori
43
3.8
Tabel tVertex
44
3.9
Tabel tHasil
44
3.10
Tabel tDetil Hasil
45
Universitas Sumatera Utara
x
DAFTAR GAMBAR
No. Gambar
Nama Gambar
Halaman
2.1
Contoh Graf Sederhana
6
2.2
Contoh Graf Ganda
6
2.3
Contoh Graf Semu
6
2.4
Contoh Graf Tak Berarah
6
2.5
Contoh Graf Berarah
8
2.6
Contoh Graf Berhingga
8
2.7
Contoh Graf Tak Berhingga
9
2.8
Contoh Graf Tidak Berbobot
9
2.9
Contoh Graf Berbobot
9
2.10
Menu Utama pada Visual Basic
16
3.1
Denah Perpustakaan
23
3.2
Peta Perpustakaan
25
3.3
Graf Rute Pencarian Buku Langkah Pertama
27
3.4
Graf Rute Pencarian Buku Langkah Kedua
28
3.5
Graf Rute Pencarian Buku Langkah Ketiga
29
3.6
Graf Rute Pencarian Buku Langkah Keempat
30
3.7
Graf Rute Pencarian Buku Langkah Kelima
31
3.8
Graf Rute Pencarian Buku Langkah Keenam
32
3.9
Graf Rute Pencarian Buku Langkah Ketujuh
33
3.10
Flowchart Algoritma A*
35
3.11
Diagram Konteks SIG Pencarian Rute Terpendek
39
Universitas Sumatera Utara
xi
3.12
DFD Level 1 SIG Pencarian Rute Terpendek
39
3.13
DFD Level 2 Pencarian Rute Terpendek
40
3.14
Flowchart Sistem
42
3.15
Database Relasi
45
3.16
Rancangan Login
46
3.17
Rancangan Home
47
3.18
Rancangan Shortest Path
48
3.19
Rancangan Data
49
3.20
Rancangan Edit Jalan dan Jarak
49
3.21
Rancangan Edit Titik
50
3.22
Rancangan Data User
51
3.23
Rancangan Help
51
3.24
Rancangan About
52
4.1
Tampilan Home
54
4.2
Tampilan Otorisasi
55
4.3
Tampilan Login
55
4.4
Tampilan Logout
56
4.5
Tampilan Shortest Path
56
4.6
Tampilan Menu Data
57
4.7
Tampilan Data Jarak dan Verteks
57
4.8
Tampilan Data Verteks dan Jarak
58
4.9
Tampilan Edit Verteks
58
4.10
Tampilan Data User
59
Universitas Sumatera Utara
xii
4.11
Tampilan Laporan Hasil Pengujian
59
4.12
Tampilan Help
60
4.13
Tampilan About
61
4.14
Tampilan Hasil Pencarian
62
4.15
Tampilan Laporan
Universitas Sumatera Utara
