Pada jaman sekarang ini teknologi satelit sudah semakin maju dan
banyak digunakan dalam kehidupan sehari-hari. Sebagai contoh yakni GPS (Global
Positioning System) atau biasa dikenal sebagai sistem navigasi. Untuk lebih
memahami cara kerja GPS dan tidak hanya sekedar menggunakannya saja maka
dilakukan pendekatan terhadap algoritma dan logika yang digunakan untuk
mengoperasikan sebuah GPS. Pendekatan dengan menggunakan graf berarah dan
berbobot dan juga pohon keputusan merupakan pendekatan yang paling tepat dan
sesuai dengan system ini. Gambar jalan-jalan yang diterima dari satelit diubah
menjadi sebuah graf berarah berbobot dan digunakan Tree atau yang disebut pohon
keputusan, untuk menentukan jalan mana yang harus diambil (jalan yang paling
efektif).
Untuk lebih memahaminya, berikut merupakan
pengertian dan definisi sebenarnya dari GPS, graf, dan tree, yang selanjutnya menghasilkan pengeertian terhadap
pengaplikasian nyata dalam kehidupan nyata. Hal ini penting untuk dibahas dan
diketahui karena sekarang ini jalan-jalan yang terutama terletak di daerah
perkotaan seringkali macet, ada perbaikan dan sebagainya. Contohnya yaitu jalan
di Kota Bandung sekarang ini banyak yang sedang diperbaiki sehingga menyebabkan
macet dan akan menghambat kegiatan penduduk. Dengan teknologi GPS maka kita
akan dapat menggunakan jalan alternatif tanpa harus mengalami macet terlebih
dahulu. Maka pemahaman terhadap cara kerja dan logika pada algoritma GPS
sederhana sangatlah diperlukan agar kita tidak hanya dikendalikan oleh mesin dan
teknologi (menjadi “budak teknologi”) tetapi kita dapat mengendalikan dan
mengembangkan teknologi agar jadi lebih bermanfaat bagi kehidupan manusia
1. Global Positioning System
(GPS)
GPS adalah sebuah sistem
yang menggunakan fasilitas satelit dalam barbagai bidang kehidupan. Umumnya GPS
yang kita kenal digunakan sebagai sistem navigasi, yang pada dasarnya digunakan
untuk keperluan militer dan pertahanan, lalu kemudian berkembang untuk
keperluan navigasi baik untuk di darat maupun di laut dan juga di udara pada
pesawat-pesawat udara (sebagai contoh Boeing 737 sudah ada yang menggunakan GPS
untuk navigasi, menentukan posisi pesawat berada dan berapa jauh jaraknya dari
tempat tujuan atau tempat mendarat terdekat). GPS dikembangkan oleh Departemen
Pertahanan Amerika Serikat dengan nama NAVSTAR GPS. Ada beberapa kegunaan GPS
secara umum, namun ruang lingkup pembahasan ini difokuskan pada GPS sebagai
sistem navigasi.
1.1. GPS
Sebagai Sistem Navigasi
Beberapa
jenis kendaraan telah dilengkapi dengan GPS untuk alat bantu nivigasi, dengan
menambahkan peta, maka bisa digunakan untuk memandu pengendara, sehingga
pengendara bisa mengetahui jalur mana yang lebih cepat dan sebaiknya dipilih
untuk mencapai tujuan yang diinginkan. Perangkat navigasi GPS adalah perangkat
yang dapat mengetahui posisi koordinat bumi secara tepat yang dapat secara
langsung menerima sinyal dari satelit. Perangkat GPS modern menggunakan peta
sehingga merupakan perangkat modern dalam navigasi di darat, kapal di laut,
sungai dan danau serta pesawat udara. Perangkat ini biasa dipasang pada
kendaraan atau telepon seluler untuk menunjukkan posisi kendaraan atau telepon
seluler tersebut berada sehingga tidak akan tersesat adan dapat menunjukkan
jalan terdekat menuju tempat tujuan. Sistem navigasi kendaraan adalah perangkat
navigasi berkendaraan modern yang digunakan untuk memandu perjalanan dari suatu
tempat ke suatu tujuan tertentu, dengan menggunakan perangkat peta digital dan
informasi posisi dengan menggunakan satelit GPS. Untuk penentu posisi di
lapangan, saat ini dilakukan dengan menggunakan alat yang disebut GPS receiver, yang kemudian diolah untuk
mendapatkan posisi koordinat buminya. Dengan menggunakan peta digital yang yang
didownload ke perangkat sistem navigasi kendaraan, sehingga dapat mengetahui
posisi saat ini di peta dan arah lintasan yang akan dilalui dari koordinat awal
menuju tempat tujuan dengan koordinat tertentu pada peta.
Gambar 1: Hasil Gambar yang Diterima Perangkat
Navigasi GPS dari Satelit
Gambar jalan dan tempat-tempat yang menjadi titik acuan pada
peta ini kemudian diubah menjadi graf berarah dan berbobot agar dapat diamati
dan kemudian diolah datanya agar dapat memberikan arah yang tepat dan efektif
untuk dapat sampai ke tempat tujuan. Kita akan membahas fungsi GPS pada
kendaraan bermotor sebagai penunjuk jalan atau pada telepon seluler. Berikut
akan dibahas cara merepresentasikan jalan yang dapat dilalui kendaraan bermotor
dan pengambilan keputusan dalam pemilihan jalan tercepat dan terefektif.
2.
GRAF
Seperti yang sudah dipelajari pada mata kuliah Matematika
Diskrit, graf dapat digunakan untuk merepresentasikan berbagai hal. Graf
terbagi menjadi beberapa bagian yaitu graf berarah dan tak berarah. Dalam
bahasan kali ini yang akan digunakan untuk merepresentasikan jalan dan
tempat-tempat acuannya adalah graf berarah.
2.1. Graf
Berarah
Sebuah graf terarah atau
digraf G terdiri dari suatu himpunan V dari verteks-verteks (atau
simpul-simpul) dan suatu himpunan E dari rusuk-rusuk (atau busur-busur)
sedemikian rupa sehingga setiap rusuk e ∈ E
menghubungkan pasangan verteks terurut.
Gambar 2 : Contoh Graf Berarah
Graf berarah dianggap yang
paling tepat untuk merepresentasikan masalah ini karena jalan-jalan di bumi
memiliki arah dan tidak semua jalan “dua arah” ada juga jalan “satu arah”. Oleh
karena itu dengan graf berarah masalah tersebut dapat terselesaikan. Sehingga
jalan tercepat menuju ke tempat tujuan dapat ditemukan tanpa perlu khawatir
akan jalan “satu arah”.
Tetapi masih ada masalah
selanjutnya yaitu kepadatan jalan-jalan di perkotaan yang sering menimbulkan
kemacetan terutama di saat liburan seperti libur Natal dan tahun baru
menyebabkan jalan macet dan perlu mencari jalan alternatif. Masalah ini dapat
diselesaikan dengan merepresentasikan gambar jalan yang diterima oleh perangkat
navigasi GPS dari satelit dengan graf berbobot.
2.2. Graf
Berbobot
Sebuah graf dengan
bilangan-bilangan pada rusuk-rusuknya disebut graf berbobot (weighted graph).
Dalam sebuah graf berbobot, panjang lintasan adalah jumlah bobot rusuk-rusuk
dalam lintasan. Dalam bahasan ini bobot setiap lintasan tidak hanya
merepresentasikan panjang lintasan saja, tetapi juga merepresentasikan tingkat
kepadatan/ kemacetan jalan/lintasan. Jadi akumulasi dari panjang jalan dari
suatu titik/tempat acuan di jalan yang nyata ke titik berikutnya dan tingkat
kepadatan pada jalan tersebut merupakan bobot untuk setiap lintasan.
Gambar 3 : Contoh
graf berbobot tak berarah.
Semakin besar bobot suatu
lintasan maka akan menghabiskan waktu yang semakin lama untuk melalui lintasan
itu. Jadi bobot pada graf berbanding lurus dengan waktu tempuh dan efektifitas
jalan untuk dilalui.
Untuk merepresentasikan gambar jalan yang diterima dari satelit
pada perangkat navigasi GPS maka kedua bentuk graf yang sudah dibahas di atas
perlu digabung sehingga membentuk graf berbobot dan berarah. Dengan graf
berbobot dan berarah maka kedua masalah utama untuk merepresentasikan lintasan
atau jalan dapat diatasi, yaitu masalah jarak/panjang lintasan dan tingkat
kepadatan jalan. Sekarang masih ada satu masalah yang sangat penting untuk
dicari solusinya yaitu mengambil keputusan jalan mana yang akan dipilih. Hal
tersebut akan dilakukan pendekatan dengan menggunakan tree atau pohon keputusan.
3.
Pohon Keputusan (Tree)
Secara umum pohon keputusan digunakan untuk memodelkan persoalan
yang terdiri dari serangkaian keputusan yang mengarah ke solusi. Tiap simpul
pada pohon keputusan menyatakan keputusan, setiap daun menyatakan solusi dan
seitap cabang menyatakan keputusan yang diambil. Pohon keputusan adalah model
prediksi menggunakan struktur pohon atau struktur berhirarki. Konsep dari pohon
keputusan adalah mengubah data menjadi pohon keputusan dan aturan-aturan
keputusan. Manfaat utama dari penggunaan pohon keputusan adalah kemampuannya
untuk mem-break down proses pengambilan keputusan yang kompleks menjadi lebih
simpel sehingga pengambil keputusan akan lebih menginterpretasikan solusi dari
permasalahan.
Gambar 4 : Contoh pohon keputusan
Gambar di atas adalah contoh pohon keputusan apakah akan pergi
bermain atau tidak dengan cuaca sebagai faktor penentu. Contoh pohon keputusan
di atas sangat sesuai untuk menantukan jalan yang akan dipilih dengan panjang
lintasan dan tingkat kepadatan jalan (bobot lintasan) sebagai faktor penentu,
yang juga menggambarkan tata cara serupa dalam pengambilan keputusan jalan
mana/solusi mana yang terbaik dan akan diinformasikan pada pengguna sistem
navigasi GPS.
Ketika menemui cabang jalan atau simpul pada graf berarah dan
berbobot yang telah dibentuk, kita tidak dapat langsung memilih jalan / lintasan
dengan bobot terkecil begitu saja karena jalan/lintasan dari suatu titik asal
ke titik tempat tujuan belum tentu hanya terdiri dari sebuah lintasan saja,
sehingga lintasan tercepat dan terefektif tidak dapat ditentukan jika hanya
memilih jalan dengan bobot terkecil setiap kali menemui cabang jalan atau
simpul pada graf yang telah terbentuk dari data yang diterima dari satelit pada
sistem navigasi GPS.
Dengan meenggunakan pohon keputusan maka kita dapat menentukan
jalan mana yang terbaik, lintasan yang pada awalnya memiliki bobot yang tinggi
mungkin saja pada pilihan jalan / cabang berikutanya adapat menghantarkan kita
pada tujuan dengan lebih cepat karena jalan selanjutnya memiliki bobot yang
kecil. Sedangkan jalan / lintasan yang bobot awalnya kecil mungkin saja
lintasan-lintasan berikutnya berbobot besar dan akan semakin menghambat jalan
ke titik tujuan. Untuk itu diperlukan pohon keputusan dan algoritma pohon
secara rekusif untuk setiap cabang pohon agar dapat memperoleh solusi terbaik
dengan cara yang efisien. Setiap cabang jalan pada graf atau pada kehidupan
nyata merupakan simpul atau node pada keputusan dimana pada pohon akan
dilakukan perbandingan bobot pada masing-masing cabang jalan / lintasan dan
begitselanjutanya untuk setiap cabang jalan yang ditemui, kita akan dihadapkan
pada pilihan yang harus diambil pada pohon keputusan sampai diperoleh jalan
yang terbaiak lalu diinformasikan pada pengguna sistem navigasi GPS cabang
jalan mana atau arah mana yang harus dipilih.
4.
Contoh Persoalan Representasi untuk GPS
Berikut merupakan contoh soal sederhana dan pembahasannya.
Gambar 5 : Graf Contoh Persoalan Representasi untuk GPS
Graf di atas adalah contoh
data masukkan dalam bentuk graf yang masuk ke dalam Pusat Informasi untuk
kemudian diproses. Kita ingin mencari jalan tercepat dari posisi awal kita
yaitu titik A sampai tiba ke titik D. Dari graf di atas maka pohon keputusan
yang dibentuk untuk mennetukan jalur terbaik adalah sebagai berikut.
Gambar 6 : Contoh Pohon
Keputusan untuk Menyelesaikan Persoalan GPS
Dapat di lihat pada gambar di atas adalah pohon dibentuk hasil
transformasi graf input, titik awal dan titik akhir. Jadi di sini menjadi lebih
jelas bahwa setiap cabang pada simpul adalah semua cabang jalan / jalur yang terdapat
pada simpul / titik tersebut tanpa mengikut sertakan cabang jalur kedatangan.
Pada pohon di atas seharusnya ada simpul C karena dari titik A pada graf juga
terdapat cabang yang menghubungkan titik A dengan titik C, tetapi cabang
tersebut tidak dimasukkan pada pohon karena arahnya. Jadi cabang atau sisi pada
graf yang berlawanan arah tidak dimasukkan ke dalam simpul pohon agar
mempermudah pemrosesan kemudian.
Sekarang kita akan mulai membahas cara penentuan solusi jalur
terbaik dengan menggunakan pohon keputusan tersebut. Bila ditinjau bobot tiap
simpul maka bobot simpul B adalah 7 dan bobot simpul E adalah 8, sedangkana
bobot simpul A adalah 0 karena belum ada jalur yang diambil. Bobot akhir pada
daun BD adalah 22, pada daun ED1 14 dan pada daun ED2 10. Bobot pada daun
adalah akumulasi dari bobot semua lintasan dari akar sampai ke daun tersebut.
Maka jelas bahwa jalur tercepat adalah dari titik A ke titik E lalu ke titik D
melelui sisi yang berbobot 2. Jika kita telusuri jalurnya satu per satu maka kita
akan menamui cabang jalan pertama yaitu dari A ke B atau dari A ke E. Apabila
kita hanya memilih saja secara langsung tentu jalur dari A ke B yang akan
dipilih karena bobotnya lebih kecil, padahal pada sisi selanjutnya yaitu dari B
ke D mempunyai bobot yang sangat besar dan jalur yang dipilih menjadi tidak
efektif jika dibandingkan dengan kita memilih jalur dari A ke E terlebih
dahulu.
Meskipun memiliki bobot yang lebih besar pada percabangan
pertama tetapi pada sisi selanjutnya jalur dari A ke E memiliki akumulasi bobot
yang lebih kecil dari pada jalur A-B-D. Selanjutnya yang jadi masalah adalah
menentukan cabang mana yang akan dipilih pada simpul E, karena kedua cabang
langsung menuju ke D maka dapat langsung dipilih cabang dengan bobot terkecil
yaitu cabang dengan bobot 2. Tetapi kita tidak dapat begitu saja menentukan
jalur dengan mudah seperti kasus pada simpul E ini. Untuk memperoleh jalur
terbaik dari titik A ke titi D maka dalam penelusuran pohon keputusan perlu
digunakan metode rekursif. Pada akar dan setiap simpul dalam fungsi atau
prosedur untuk mencari jalur terbaik dipanggil kembali. Maka pada satiap simpul
pemanggilan prosedur atau fungsi tersebut dilakukan sebanyak n kali, dimana n
adalah jumlah cabang pada masing-masing simpul. Begitu terus proses berlanjut
dengan cara rekursif sampai pada daun atau tempat tujuan sehingga diperoleh
bobot untuk masing-masing daun. Dengan suatu algoritma sederhana kita tentu
dapat memilih solusi terbaik jika bobot untuk masing- masing solusi telah
diperoleh. Hanya dengan mencari bobot minimum maka akan diperoleh solusi tebaik
atau jalur tercepat dari titik awal sampai ke titik tujuan.