Aplikasi Matematika Diskrit Dalam Kehidupan

Mata kuliah : Matematika Diskrit
Dosen : I Putu Agus Eka Pratama ST. MT.
Nama : Daniel - 1413003
ITHB

Aplikasi Matematika Diskrit Pada Kehidupan

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 pohon keputusan untuk menentukan jalan mana yang harus diambil (jalan yang paling efektif).

              Terlebih dahulu satu per satu pengertian dan definisi sebenarnya dari GPS, graf dan juga pohon keputusan lalu aplikasinya 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 tetapi kita dapat mengendalikan dan mengembangkan teknologi agar jadi lebih bermanfaat bagi kehidupan manusia.

1. Apa itu GPS?

            GPS yang merupakan singkatan dari Global Positioning System atau biasa dikenal sebagai sistem navigasi. GPS pada umumnya menggunakan satellite untuk beroperasi. Umumnya GPS yang kita kenal digunakan sebagai sistem navigasi, tetapi sebenarnya tidak hanya itu. GPS dasarnya digunakan untuk keperluan militer dan pertahanan, lalu kemudian berkembang untuk keperluan navigasi baik untuk di darat maupun di laut dan juga d udara pada pesawat-pesawat udara.

2. GRAF

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 1 : 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 hari besar maupun liburan. Selain itu banyaknya jalan-jalan yang rusak akibat cuaca yang tidak menentu sehingga banyak perbaikan jalan yang menyebabkan jalan ditutup atau macet total.

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 2 : 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 pohon keputusan.

3. POHON KEPUTUSAN

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 salah satu metode klasifikasi yang paling populer karena mudah untuk diinterpretasi oleh manusia. 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.

Meskipun memiliki beberapa kekurangan, tetapi metode pengambilan keputusan dengan pohon keputusan ini merupakan pendekatan yang paling simpel, sederhana dan sesuai untuk menentukan jalan mana yang paling cepat, dekat dan efektif yang akan dipilih pada sistem navigasi GPS. Metode pohon keputusan ini melengkapi data yang telah diubah menjadi bentuk graf berarah dan berbobot lalu akan memberikan solusi jalan/ lintasan terbaik pada 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.