ANALISIS ALGORITMA A STAR (A*) DAN IMPLEMENTASINYA DALAM PENCARIAN JALUR TERPENDEK PADA JALUR LINTAS SUMATERA DI PROVINSI SUMATERA UTARA
SKRIPSI
DEWI YUSRA AINI 061401053
PROGRAM STUDI S1 ILMU KOMPUTER DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2010
Universitas Sumatera Utara
ANALISIS ALGORITMA A STAR (A*) DAN IMPLEMENTASINYA DALAM PENCARIAN JALUR TERPENDEK PADA JALUR LINTAS SUMATERA DI PROVINSI SUMATERA UTARA
SKRIPSI
Diajukan untuk melengkapi tugas dan memenuhi syarat mencapai gelar Sarjana Komputer
DEWI YUSRA AINI 061401053
PROGRAM STUDI S1 ILMU KOMPUTER DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2010
Universitas Sumatera Utara
PERSETUJUAN
Judul
: ANALISIS ALGORITMA A* DAN IMPLEMENTASINYA DALAM PENCARIAN RUTE TERPENDEK PADA JALUR LINTAS SUMATERA DI PROVINSI SUMATERA UTARA : SKRIPSI : DEWI YUSRA AINI : 061401053 : SARJANA (S1) ILMU KOMPUTER : ILMU KOMPUTER : MATEMATIKA DAN ILMU PENGETAHUAN ALAM (FMIPA) UNIVERSITAS SUMATERA UTARA
Kategori Nama Nomor Induk Mahasiswa Program Studi Departemen Fakultas
Diluluskan di Medan, 21 Desember 2010 Komisi Pembimbing Pembimbing 2
:
Dian Rachmawati, S.Si, M.Kom NIP.198307232009122004
Pembimbing 1
Maya Silvi Lydia, B.Sc, M.Sc NIP. 197401272002122001
Diketahui/Disetujui oleh Program Studi S1 Ilmu Komputer FMIPA USU Ketua,
Prof. Dr. Muhammad Zarlis NIP. 195707011986011003
Universitas Sumatera Utara
PERNYATAAN
ANALISIS ALGORITMA A* DAN IMPLEMENTASINYA DALAM PENCARIAN RUTE TERPENDEK PADA JALUR LINTAS SUMATERA DI PROVINSI SUMATERA UTARA
SKRIPSI
Saya mengakui bahwa skripsi ini adalah hasil kerja saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.
Medan, 19 Desember 2010
DEWI YUSRA AINI 061401053
Universitas Sumatera Utara
PENGHARGAAN
Assalamu’alaikum Wr.Wb Rasa syukur yang tidak terhingga penulis ucapkan kepada Allah SWT, Pencipta alam semesta yang memberikan rahmad dan karunia-Nya kepada Penulis sehingga akhirnya atas izin Allah SWT Penulis dapat menyelesaikan tugas akhir ini dengan baik. Shalawat dan salam kepada Nabi Muhammad SAW yang telah membawa pencerahan bagi umat manusia dalam menjalani hidup dan kehidupan.
Dalam menyelesaikan tugas akhir ini penulis telah banyak menerima bimbingan, arahan, masukan, serta dorongan semangat dari berbagai pihak. Untuk itu penulis mengucapkan terima kasih yang tak terhingga kepada : 1. Buat ayah dan ibu penulis tercinta yang terus memberikan curahan kasih
2.
3.
4.
5.
6. 7.
8. 9.
sayangnya, terus memotivasi penulis dalam menyelasaikan tugas akhir ini, cinta kalian akan terus terpatri dalam jiwa penulis, Terima kasih Ayah dan Ibu penulis. Ibu Maya Silvi Lydia, B.Sc, M.Sc dan Ibu Dian Rachmawati,S.Si,M.Kom sebagai Dosen Pembimbing penulis yang telah banyak memberikan masukan, bimbingan, motivasi dan perhatian kepada penulis sehingga skripsi ini dapat selesai dengan baik. Bapak Prof. Dr. Iryanto,M.Si dan Bapak Drs. H. Agus Salim Harahap,M.Si sebagai Dosen Penguji yang juga telah banyak memberi masukan, kritik maupun saran dalam penulisan skripsi ini Bapak Prof. Dr. Muhammad Zarlis dan Bapak Syahriol Sitorus S.Si, M.IT selaku ketua dan sekretaris Departemen Ilmu Komputer S-1 Universitas Sumatera Utara. Seluruh Dosen dan Asisten lab di lingkungan S1 Ilmu Komputer USU yang telah banyak memberikan ilmu kepada penulis mulai dari penulis menginjakkan kaki di kampus tercinta ini sampai pada penulis menyelesaikan kuliah. Seluruh staf pegawai yang telah banyak membantu selama perkuliahan. Buat teman-teman tersayang, Tuil (Rifnatul), Moly (Asmaina), Jannah, ipeh (iva/shareefah/iva kitty/sarifah/sarivah), pipit (pipyd atau fitri), koko Hadi, makasih atas tawaran dan dorongannya, walau g’ jadi, dan teman-teman lainnya Winda, Riri, Icha, Ara, Alvin, komting kom A (Rifki) dan kom B (Reza) dan teman-teman yang lainnya . Buat anak-anak ’06 semuanya, semoga kebersamaan kita selama 4 tahun menjadi hari-hari yang tak terlupakan. Buat seluruh mahasiswa ilkom, anak-anak musholla Al-Khwarizmi, terima kasih semuanya.
Akhirnya, penulis menyadari bahwa dalam penulisan skripsi ini masih terdapat banyak kekurangan oleh karena itu untuk kesempurnaan penulisan skripsi ini penulis mengharapkan kritik dan saran yang membangun. Semoga Allah SWT selalu bersama kita dalam meraih segala cita-cita dan harapan kita semua, semoga kita dapat
Universitas Sumatera Utara
menjaga nama baik dan mencintai almamater FMIPA USU, Maju terus Ilmu Komputer USU dalam mendidik mahasiswa yang berprestasi dan berbudi pekerti. Wassalmu’alaikum warahmatullahi wabarakatuh Medan, Desember 2010 Penulis,
Dewi Yusra Aini 061401053 .
Universitas Sumatera Utara
ABSTRAK
Adalah hal yang sangat wajar bagi setiap orang, apabila mereka bepergian dari suatu tempat ke tempat lainnya dengan melewati jalur yang mereka anggap sebagai jalur terpendek. Namun akan sangat sulit bagi seseorang untuk memilih jalur mana yang terpendek apabila berpergian ke suatu tempat yang jauh dan memiliki banyak jalan akses untuk menuju ke tempat tujuan tersebut. Karena bisa saja jalur yang mereka pilih bukanlah jalur yang tependek. Dalam tugas akhir ini, akan dibuat sebuah perangkat lunak yang dapat menyelesaikan permasalahan yaitu suatu perangkat lunak yang dapat memberikan rute jarak paling minimum pada sebuah peta dengan menggunakan Algoritma A*. Algoritma A* menggunakan pendekatan heuristik yang memberikan nilai ke tiap-tiap verteks yang direpresentasikan dengan kota. Aplikasi ini dibuat dengan menggunakan bahasa pemrograman MATLAB 7.50. Berdasarkan pengujian, aplikasi dengan menggunakan Algoritma A* ini dapat menunjukkan jalurjalur terpendek antara dua verteks yang diinginkan.
Universitas Sumatera Utara
ANALYSIS A STAR (A*) ALGORITHM AND ITS IMPLEMENTATION IN SHORTEST PATH SEARCHING IN TRANS-SUMATERAN HIGHWAY IN PROVINCE OF NORTH SUMATERA
ABSTRACT
It is a reasonable for people, when they are travel from a place to another palce through a path which they consider as shortest path. However, it would be hard for someone to choose which path that is the shortest path when they travel to somewhere, if the place is far away and it has many access way to the destination place. Because there is a possibility the path that they choose is not the shortest path. In this thesis, it will be made a program that can solve the problem, that is a program which can give us the shortest path in a map using A* Algorithm. A* Algorithm using heuristic approach which give a value to each vertex that represented with a city. This application was build using programming language MATLAB 7.5. Based on testing, this application could show shortest paths between two vertex which is desire.
Universitas Sumatera Utara
Daftar Isi
Persetujuan Pernyataan Penghargaan Abstrak Abstract Daftar Isi Daftar Tabel Daftar Gambar BAB 1
PENDAHULUAN 1.1 1.2 1.3 1.4 1.5 1.6
BAB 2
ii iii iv vi vii viii x xi
Latar Belakang Tujuan Penelitian Rumusan Masalah Batasan Masalah Metode Penelitian Sistematika Penulisan
1 2 2 2 2 3
TINJAUAN PUSTAKA 2.1 Graf 2.1.1 Definisi Graf 2.1.2 Jenis-jenis Graf 2.1.3 Terminologi Dasar 2.1.4 Beberapa Graf Khusus 2.1.5 Representasi Graf 2.2 Lintasan Terpendek (Shortest Path) 2.3 Metode Pencarian 2.3.1 Pencarian Buta(Blind Search/Un-informed Search) 2.3.1.1 Breadth Firs Search (BFS) 2.3.1.2 Depth First Search (DFS) 2.3.2 Pencarian Heuristik 2.3.2.1 Generate and Test (bangkitkan dan uji) 2.3.2.2 Hill Climbing (pendakian Bukit) 2.3.2.3 Best First Search (BFS) 2.3.2.3.1 Greedy Best First Search 2.3.2.3.2 Algoritma A* 2.4 Fungsi Heuristik 2.5 MATLAB (Matrix Laboratory)
BAB 3
5 5 5 8 10 13 15 16 16 16 17 18 19 19 19 20 20 21 22
ANALISIS ALGORITMA 3.1 Analisa Algoritma A* 3.2 Flowchart
24 32
Universitas Sumatera Utara
3.3 Perancangan Antarmuka
BAB 4
34
IMPLEMENTASI DAN PENGUJIAN SISTEM 4.1 Implementasi 4.2 Spesifikasi Perangkat Lunak 4.3 Spesifikasi Perangkat Keras
36 36 36 37 40
4.4 Tampilan Aplikasi Sistem 4.5 Pengujian Sistem
4.5.1 Pengujian Pencarian Rute atau Lintasan Terpendek dari Aplikasi yang Telah Dibuat 4.5.2 Pengujian Kesesuaian Pemilihan Jalur Lintasan Terpendek dengan Jumlah Total Jarak Jalur yang Ditempuh
BAB 5
KESIMPULAN DAN SARAN 5.1 Kesimpulan 5.2 Saran
DAFTAR PUSTAKA
40
41
45 45
46
Universitas Sumatera Utara
DAFTAR TABEL
Halaman Tabel 3.1 Jarak Euclidian masing-masing verteks pada Graf 1
27
Universitas Sumatera Utara
DAFTAR GAMBAR
Halaman Gambar 2.1 Contoh Graf Sederhana Gambar 2.2 Contoh Graf Ganda Gambar 2.3 Contoh Graf Semu Gambar 2.4 Graf Tak Berarah Gambar 2.5 Contoh Graf Berarah Gambar 2.6 Graf Tak Berhingga Gambar 2.7 Graf G1 Gambar 2.8 Contoh Graf Berbobot Gambar 2.9 Sirkuit v1-v2-v3-v1 Gambar 2.10 Contoh Graf Lengkap Gambar 2.11 Contoh Graf Lingkaran Gambar 2.12 Graf teratur derajat 4 dan 2 Gambar 2.13 Contoh Graf Bipartit Gambar 2.14 Contoh Graf yang Isomorfik Gambar 2.15 Contoh Graf Planar K4 Gambar 2.16 Graf G Gambar 2.17 Graf A Gambar 2.18 Tree untuk Breadth First Search Gambar 2.19 Tree untuk Depth First Search Gambar 2.20 Tampilan awal Matlab Gambar 2.21 Tampilan Gui Matlab Gambar 3.1 Graf 1 Gambar 3.2 Graf 1 Gambar 3.3 Graf 1 Gambar 3.4 Graf 1 Gambar 3.5 Graf 1 Gambar 3.6 Graf 1 Gambar 3.7 Graf 1 Gambar 3.8 Flowchart pencarian lintasan terpendek dengan algoritma A* Gambar 3.9 Gambaran sistem antarmuka Gambar 4.1 Tampilan Awal Aplikasi Gambar 4.2 Tampilan Pemilihan Verteks Gambar 4.3 Tampilan Pencarian Lintasan Gambar 4.4 Tampilan Lintasan Terpendek Gambar 4.5 Pesan Peringatan Gambar 4.6 Penginputan/pemilihan verteks awal dan verteks akhir Gambar 4.7 Hasil Proses Pencarian Gambar 4.8 Pemilihan Kota Medan dan Lima Puluh Gambar 4.9 Tampilan Hasil Pencarian
6 6 6 7 7 8 8 10 10 11 11 11 12 12 13 14 15 17 18 23 23 26 27 28 29 30 30 31 33 34 37 38 38 39 40 40 41 42 42
Universitas Sumatera Utara
