 1
BAB 1
PENDAHULUAN
1.1.
Latar Belakang
Pada jaman serba modern ini, peta masih digunakan oleh
kebanyakan orang untuk menuju suatu tempat. Lintasan yang dipilih untuk
menuju tujuan pastilah lintasan yang paling pendek. Namun, pencarian
lintasan terpendek secara manual, akan membutuhkan banyak waktu dan
ketelitian.
Masalah lintasan terpendek berkaitan dengan pencarian lintasan pada
graf berbobot yang menghubungkan dua buah simpul
(edge) sedemikian
sehingga jumlah bobot pada sisi-sisi yang terpilih merupakan bobot
minimum. Terdapat banyak algoritma yang dapat digunakan untuk
pemecahan masalah dalam pencarian lintasan terpendek. Pemilihan
algoritma yang paling optimal seringkali menjadi permasalahan dalam
pencarian lintasan terpendek karena setiap algoritma memiliki kelebihan
dan kekurangannya masing-masing (Hardianto, 2013: 79).
Secara umum, algoritma pencarian dapat dibedakan menjadi dua
metode yaitu, metode uninformed search
dan metode informed search.
Metode uninformed search
merupakan metode matematika biasa dengan
informasi yang jelas, sedangkan metode informed search
merupakan
metode pencarian yang menggunakan metode pendekatan pada proses
pencariannya. Metode informed search
diketahui lebih efisien
dibandingkan dengan metode uninformed search (Russell & Norvig, 2010:
92).
Dalam skripsi
ini, akan dibahas dua buah algoritma pencarian yang
tergolong ke dalam metode informed search
yaitu algoritma A* (Star) dan
algoritma greedy best-first search
yang bekerja dengan mengembangkan
simpul-simpul dalam proses pencarian lintasan terpendek. Simpul yang
dianggap berpotensi menemukan lintasan terpendek akan dikembangkan
sampai pencarian berakhir. Kedua algoritma bekerja dengan menerapkan
prinsip best-first search yang mengembangkan simpul berdasarkan sebuah
fungsi yang disebut fungsi evaluasi
. Pada umumnya, simpul yang
|
|
2
memiliki fungsi evaluasi terkecil akan dikembangkan sampai pencarian
berakhir (Russell & Norvig, 2010: 92).
Algoritma A* dan greedy best-first search akan dibandingkan untuk
mencari lintasan terpendek dari segi panjang lintasan dan waktu berpikir
yang dihasilkan algoritma. Kedua algoritma akan diterapkan dalam peta
dengan menggunakan data dari peta Jawa Tengah. Setelah dibandingkan,
akan ditarik kesimpulan dari hasil perbandingan kedua algoritma tersebut.
1.2.
Rumusan Masalah
Berdasarkan uraian yang telah dikemukakan di atas, masalah yang
akan dikembangkan adalah :
1.
Bagaimana algoritma A*
dan algoritma greedy best-first search
bekerja dalam pencarian lintasan terpendek?
2.
Bagaimana membandingkan
algoritma
A*
dan algoritma greedy
best-first search dalam pencarian lintasan terpendek?
3.
Hal apa yang akan digunakan untuk membandingkan
dan
menentukan algoritma terbaik antara algoritma A* dan algoritma
greedy best-first search?
1.3.
Hipotesis
Pada penelitian sebelumnya yang dilakukan oleh Goyal, Mogha,
Luthra, Sangwan
(2014) menghasilkan panjang lintasan yang dilalui
menggunakan algoritma greedy best-first search
sama dengan panjang
lintasan yang dilalui menggunakan algoritma A*. Kemudian, algoritma A*
memiliki waktu berpikir yang lebih singkat daripada algoritma greedy best-
first search. Namun jika dilihat dari pengertian dan tahapan kedua algoritma,
algoritma A*
seharusnya
memberikan lintasan lebih pendek dan waktu
berpikir yang lebih lama daripada algoritma greedy best-first search. Hal ini
disebabkan karena algoritma A*
menghitung semua kemungkinan lintasan
terpendek yang mungkin dilalui sedangkan algoritma greedy best-first search
hanya melihat kemungkinan lintasan terpendek yang ada di depannya.
|
 3
Hipotesis dalam penelitian ini adalah :
:
algoritma greedy best-first search
memberikan lintasan lebih
pendek daripada algoritma A*
dalam menentukan lintasan
terpendek.
:
algoritma A* memberikan lintasan lebih pendek daripada algoritma
greedy best-first search dalam menentukan lintasan terpendek.
:
algoritma A*
memberikan waktu berpikir lebih cepat daripada
algoritma greedy best-first search
dalam menentukan lintasan
terpendek.
:
algoritma greedy best-first search memberikan waktu berpikir lebih
cepat daripada algoritma A* dalam menentukan lintasan terpendek.
1.4.
Ruang Lingkup
Ruang lingkup pada penelitian ini adalah :
1.
Algoritma yang dibandingkan adalah
algoritma A* dan algoritma
greedy best-first search.
2.
Fungsi heuristic
yang digunakan dalam algoritma A* dan
algoritma greedy best-first search
adalah Straight-line distance
(Euclidean distance).
3.
Perbandingan algoritma hanya dari segi panjang lintasan dan lama
waktu menentukan lintasan.
4.
Data yang digunakan untuk membandingkan algoritma adalah
kota-kota di
provinsi Jawa Tengah yang diubah menjadi bentuk
graf tidak berarah dengan 20 nodes sebagai kota.
5.
Aplikasi pengujian dibuat dengan bahasa pemrograman C#.
6.
Aplikasi pengujian dijalankan pada sistem operasi Windows 7
1.5.
Tujuan dan Manfaat
Tujuan pada penelitian ini adalah :
1.
Mengetahui metode algoritma A* dan algoritma greedy best-first
search dalam menentukan lintasan terpendek.
|
|
4
2.
Membuat perbandingan algoritma A*
dan algoritma greedy best-
first search dalam menentukan lintasan terpendek.
3.
Membuktikan teori yang ada sebelumnya tentang algoritma
greedy best-first search
dan A*
dalam menentukan lintasan
terpendek
Manfaat dibuatnya penelitian ini adalah :
1.
Menambah wawasan dan pengetahuan tentang masalah pencarian
lintasan terpendek.
2.
Lebih mengenal tentang algoritma A* dan algoritma greedy best-
first search dalam masalah penentuan lintasan terpendek.
1.6.
Metode Penelitian
Metode penelitian yang digunakan dalam penelitian ini adalah :
1.
Metode Analisis
Tahapan-tahapan yang dilakukan dalam metode analisis adalah
analisis terhadap berbagai algoritma yang telah dan dapat
diterapkan dalam pencarian lintasan terpendek dari beberapa
sumber seperti jurnal lokal maupun jurnal internasional.
2.
Metode Perancangan
Tahapan-tahapan yang dilakukan dalam metode perancangan
adalah merancang flowchart
dari algoritma A*
dan greedy best-
first search
untuk setiap tahapan pencarian lintasan terpendek
pada peta. Kemudian, tahapan selanjutnya dalam metode
perancangan adalah merancang
peta dengan data dari peta Jawa
Tengah dan user interface untuk aplikasi pengujian algoritma.
3.
Metode Implementasi
Metode implementasi dilakukan dengan menerapkan algoritma
A*
dan greedy best-first search
yang telah dirancang ke dalam
aplikasi pengujian algoritma.
4.
Metode Pengujian
Dalam metode pengujian, algoritma A* dan greedy best-first
search yang telah diterapkan dalam aplikasi akan diuji. Pengujian
akan dilakukan dengan melihat algoritma mana yang memberikan
|
|
5
lintasan lebih pendek dan waktu berpikir yang lebih singkat.
Kemudian, dari hasil pengujian akan dilakukan penarikan
kesimpulan.
1.7.
Sistematika Penulisan
Sistematika penulisan menjelaskan tentang susunan penulisan skripsi
yang telah dibuat secara sistematis. Penulisan skripsi ini dibagi menjadi
lima bab dan beberapa sub-bab. Sistematika penulisan disusun dengan
urutan sebagai berikut :
Bab 1 Pendahuluan
Bab ini berisi tentang latar belakang penulisan skripsi, rumusan
masalah, hipotesis, ruang lingkup yang akan dibahas dalam skripsi, tujuan
dan manfaat, metode penelitian yang digunakan, dan sistematika penulisan
skripsi yang menjelaskan pokok-pokok pembahasan
Bab 2 Tinjauan Pustaka
Bab ini berisi penjelasan mengenai teori-teori yang digunakan sebagai
dasar penulisan skripsi dan pembuatan aplikasi. Teori-teori tersebut
didapatkan melalui studi pustaka, internet, dan berbagai sumber lain yang
mendukung skripsi dan pembuatan aplikasi. Terdapat juga related works
yang menampilkan hasil pencapaian dari penelitian yang terdahulu.
Bab 3 Metodologi
Bab ini menjelaskan inti dari skripsi yang dibuat. Bagaimana
perancangan serta proses kerja dari aplikasi yang dibuat dalam skripsi.
Menampilkan kerangka berpikir dalam bentuk flowchart
dan penjelasan
flowchart tersebut. Terdapat juga tampilan dari rancangan layar yang akan
dibuat.
Bab 4 Hasil dan Pembahasan
Bab ini menampilkan hasil dari pengujian aplikasi yang dibuat dan
pembahasan dari hasil yang dicapai. Menampilkan screenshot dari aplikasi
|
|
6
yang telah dibuat, dan menampilkan hasil evaluasi perbandingan algoritma
yang diuji.
Bab 5 Simpulan dan Saran
Bab ini menjelaskan tentang kesimpulan dari aplikasi yang dibuat dan
saran untuk pengembangan lebih lanjut.
|