IMPLEMENTASI METODE EXHAUSTIVE SEARCH UNTUK MENENTUKAN SHORTEST PATH ANTAR PUSAT PERBELANJAAN DI KOTA MEDAN
SKRIPSI
SILVIA NINGSIH PRATIWI 121421082
PROGRAM STUDI EKSTENSI S1 ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2015
Universitas Sumatera Utara
IMPLEMENTASI METODE EXHAUSTIVE SEARCH UNTUK MENENTUKAN SHORTEST PATH ANTAR PUSAT PERBELANJAAN DI KOTA MEDAN
SKRIPSI
Diajukan untuk melengkapi tugas dan memenuhi syarat memperoleh ijazah Sarjana Ilmu Komputer
SILVIA NINGSIH PRATIWI 121421082
PROGRAM STUDI EKSTENSI S1 ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2015
Universitas Sumatera Utara
ii
PERSETUJUAN
Judul
: IMPLEMENTASI METODE EXHAUSTIVE SEARCH UNTUK MENENTUKAN SHORTEST PATH ANTAR PUSAT PERBELANJAAN DI KOTA MEDAN
Kategori
: SKRIPSI
Nama
: SILVIA NINGSIH PRATIWI
Nomor Induk Mahasiswa : 121421082 Program Studi
: EKSTENSI S1 ILMU KOMPUTER
Fakultas
: ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA
Komisi Pembimbing
:
Pembimbing II
Pembimbing I
Ade Candra, ST, M.Kom NIP. 19790904 200912 1 002
Dr. Elviawaty MZ, ST, MT, MM. NIP. 19700716200501 2 002
Diketahui/disetujui oleh Program Studi Ekstensi S1 Ilmu Komputer Ketua,
Dr. Poltak Sihombing, M.Kom NIP. 19620217 199103 1 001
Universitas Sumatera Utara
iii
PERNYATAAN
IMPLEMENTASI METODE EXHAUSTIVE SEARCH UNTUK MENENTUKAN SHORTEST PATH ANTAR PUSAT PERBELANJAAN DI KOTA MEDAN
SKRIPSI
Saya mengakui bahwa skripsi ini adalah hasil kerja saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.
Medan,
Agustus 2015
Silvia Ningsih Pratiwi NIM. 121421082
Universitas Sumatera Utara
iv
PENGHARGAAN
Segala puji dan syukur penulis ucapkan kehadirat Allah SWT yang telah memberikan rahmat dan hidayah-Nya kepada penulis sehingga dapat menyelesaikan skripsi ini tepat waktu sesuai dengan instruksi dan peraturan yang berlaku di Fakultas Ilmu Komputer dan Teknologi Informasi serta shalawat dan salam penulis hadiahkan kepada Nabi Besar Muhammad SAW.
Dalam penyusunan dan penulisan skripsi ini, penulis banyak mendapat bantuan, dukungan, dan bimbingan dari berbagai pihak. Pada kesempatan ini penulis ingin mengucapkan rasa terima kasih dan penghargaan kepada :
1.
Kedua orang tua yang penulis sayangi, ibunda Yuslina dan ayahanda Supriadi yang tidak henti-hentinya memberikan doa, motivasi, dan dukungan yang selalu menjadi sumber semangat penulis.
2.
Bapak Prof. Subhilhar, Ph.D selaku Rektor Universitas Sumatera Utara.
3.
Bapak Prof. Dr. Muhammad Zarlis, M.Kom sebagai Dekan Fakultas Ilmu Komputer dan Teknologi Informasi.
4.
Bapak Dr. Poltak Sihombing, M.Kom sebagai Ketua Program Studi S1 Ilmu Komputer.
5.
Ibu Maya Silvi Lydia, B.Sc, M.Sc selaku Sekretaris Program Studi Ilmu Komputer.
6.
Ibu Dr. Elviawaty MZ, ST, MT, MM.selaku Dosen Pembimbing I dan Bapak Ade Candra, ST, M.Kom
selaku Dosen Pembimbing II
yang telah meluangkan
waktu, tenaga, dan pikiran dalam membimbing, mengarahkan, menasehati, memotivasi, dan menyemangati penulis agar dapat menyelesaikan skripsi ini. 7.
Bapak Drs. Partano Siagian, M.Sc selaku dosen Pembanding I dan Bapak Dr. Syahril Efendi, S.Si, MITselaku dosen Pembanding II yang telah memberikan kritik dan saran terhadap skripsi penulis.
8.
Seluruh staf pengajar dan pegawai Fakultas Ilmu Komputer dan Teknologi Informasi.
Universitas Sumatera Utara
v
9.
Adikdan seorang tersayang Dadang Pratama, Dodi Pramana, dan Herman yang selalu memotivasi penulis dalam menyelesaikan skripsi ini.
10. Sahabat-sahabat luar biasa Nurasma, Novri Sutanti, Reza Mahardi Sidabutar, dan Siti Handayani yang selalu menemani dan memberi motivasi kepada penulis. 11. Teman – teman seperjuangan mahasiswa/i S1 Ekstensi Ilmu Komputer stambuk 2012 yang selalu memberi dukungan. 12. Semua pihak yang terlibat langsung ataupun tidak langsung yang tidak dapat penulis ucapkan satu per satu yang telah membantu menyelesaikan skripsi ini.
Penulis menyadari bahwa skripsi ini masih memiliki banyak kekurangan, 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 skripsi ini. Semoga skripsi ini dapat bermanfaat bagi penulis dan pembaca, khususnya rekan-rekan mahasiswa lainnya yang mengikuti perkuliahan di Universitas Sumatera Utara.
Medan, Penulis
Agustus 2015
Silvia Ningsih Pratiwi
Universitas Sumatera Utara
vi
ABSTRAK
Pusat perbelanjaan di Kota Medan adalah salah satu tempat yang banyak diminati oleh masyarakat maupun wisatawan. Untuk mengunjungi beberapa pusat perbelanjaan kemacetan dan transportasi menjadi suatu masalah yang sering dihadapi. Hal ini dikarenakan banyak masyarakat atau wisatawan yang tidak tahu shortest path antar pusat perbelanjaan di Kota Medan. Selain kemacetan dan masalah transportasi, jarak antar pusat perbelanjaan juga merupakan masalah utama dan shortest path mampu memecahkan masalah tersebut. Aplikasi shortest path menggunakan metode Exhaustive Searchmerupakan metode dengan mencari semua kombinasi dan permutasi dari objek-objek yang ada dan bertujuan untuk mengatasi jarak jauh antar pusat perbelanjaan. Hasil dari aplikasi ini mampu menampilakan shortest path antar pusat perbelanjaan di Kota Medan. Kata Kunci : Exhaustive Search, Shortest Path,Pusat Perbelanjaan, Medan.
Universitas Sumatera Utara
vii
ABSTRACT
Shopping centers in the Medan city was one of the favorite pleaces by the people and tourists. To visit some shopping centers such as traffic jam and transportation are problems often faced. This is happen because many people or tourists whose do not know the shortest path between shopping centers in the Medan city. Besides the traffic jam and transportation problems the distance between the shopping center is the main problem and application of the shortest path can solve this problem.Developed the application of the shortest path using a exhaustive search method is a method which to search all combination and permutation from the object and purpose to solve distance problems. This application can be used to know the shortest path between shopping centers in the Medan city. Keyword : Exhaustive Search , Shortest Path , Shopping Centers, Medan .
Universitas Sumatera Utara
viii
DAFTAR ISI
Persetujuan Pernyataan Penghargaan Abstrak Abstract Daftar Isi Daftar Tabel Daftar Gambar
ii iii iv vi vii viii x xi
Bab 1 Pendahuluan 1.1 Latar Belakang Masalah 1.2 Rumusan Masalah 1.3 Batasan Masalah 1.4 Tujuan Penelitian 1.5 Manfaat Penelitian 1.6 Metodologi Penelitian 1.7 Sistematika Penulisan
1 2 2 3 3 4 5
Bab 2 Landasan Teori 2.1 Shortest path 2.2 Graph 2.2.1 Macam – macam Graph Menurut Arah dan Bobotnya 2.3 Lintasan 2.4 Metode 2.5 Metode Exhaustive Search 2.6 Kecerdasan Exhaustive Search 2.6.1 Backtracking 2.6.2 Branch-and-bound 2.7 Mempercepat Metode Exhaustive Search
6 6 7 9 10 11 13 13 14 14
2.8 Tinjauan Penelitian Terdahulu
17
Bab 3 Analisis dan Perancangan 3.1 Analisis Sistem 3.1.1 Analisis Masalah 3.1.2 Analisis Persyaratan 3.2 Pemodelan Sistem 3.2.1 Use Case Diagram 3.2.2 Activity DiagramPencarian Shortest Path dengan Metode Exhaustive Search 3.2.3 Activity Diagram Sistem yang Diusulkan 3.2.4 Sequence Diagram 3.3 Flowchart 3.4 Perancangan Sistem
18 18 19 20 20 21 22 23 24 25
Universitas Sumatera Utara
ix
Bab 4 Implementasi dan Pengujian 4.1 Implementasi Sistem 4.1.1 Tampilan Halaman Jarak Pusat Belanja 4.1.2 Tampilan Pencarian Jarak Metode Exhaustive Search 4.2 ImplementasiMetode Exhaustive Search 4.2.1 Analisis proses perhitungan shortest path antar pusat perbelanjaan dengan metode exhaustive search. 4.3 Pengujian Sistem 4.4 Pengujian Black Box Testing 4.4.1 Pengujian Black Box (Black Box Testing) Pada Sistem 4.4.2 Kasus dan hasil pengujian
28 29 29 30 30 36 37 37
37
Bab 5 Kesimpulan dan Saran 5.1 Kesimpulan 5.2 Saran
43 43
Daftar Pustaka
44
Lampiran
Universitas Sumatera Utara
x
DAFTAR TABEL
Hal. 2.1 Enumerasikan semua sirkuit Hamilton 4.1 Evaluasi sirkuit Hamilton 4.2 Perhitungan Manual Metode Exhaustive Search 4.3 Rencana Pengujian 4.4 Pengujian Pencarian Shortest Path
12 30 32 37 38
Universitas Sumatera Utara
xi
DAFTAR GAMBAR
Hal. 2.1 Graph dengan 4 verteks dan 5 edges 2.2 Graph berarah dan berbobot 2.3 Graph tidak berarah dan berbobot 2.4 Graph berarah dan tidak berbobot 2.5 Graph tidak berarah dan tidak berbobot 2.6 Penggambaran Graph Hamilton 2.7 Flowchart Metode Exhaustive Search 3.1 Diagram Ishikawa 3.2 Use Case Sistem 3.3 ActivityDiagram Pencarian Shortest path dengan Exhaustive Search 3.4 Pencarian Shortest Path 3.5 Sequence Diagram Metode Exhaustive Search 3.6 Flowchart metode exhaustive search 3.7 Rancangan Tampilan HalamanAwal Web 3.8 Rancangan Tampilan Halaman Peta Kota Medan 4.1 Tampilan Halaman Jarak Pusat Belanja 4.2 Tampilan Pencarian Jarak Metode Exhaustive Search 4.3 Graph Hamilton 4.4 Graph Antar Pusat Perbelanjaan 4.5 Hasil Pengujian Exhaustive Search
7 8 8 8 9 11 16 19 20 21 22 23 24 25 26 29 29 30 31 37
Universitas Sumatera Utara
