Catatan si Zains

5. HASIL DAN PEMBAHASAN

Untuk memahami cara kerja dan aplikasi graf berbobot berarah dan pohon keputusan yang telah dibahas sebelumnya pada sistem navigasi GPS, maka terlebih dahulu akan dibahas cara kerja dan jalur data yang dilalui mulai dari GPS, satelit sampai memberikan arah dan solusi bagi pengguna sistem navigasi GPS. Serta proses penentuan jalur atau solusi terbaik dalam menentukan jalan yang dipilih di Pusat Informasi dengan menggunakan algoritma sederhana dan metode graf dan pohon yang sudah dibahas. Dengan mengetahui hal-hal tersebut akan lebih mudah bagi kita untuk memahami aplikasi dari metode ini.

Pokok bahasan kita terletak pada bagian saat data atau informasi sampai ke Pusat Informasi dan mulai diolah. Dan yang menjadi masalah adalah bagaimana cara mengolah data tersebut dengan cepat, tepat dan efisien untuk mendapatkan solusi yang terbaik bagi pengguna sistem navigasi GPS. Masalah tersebut dapat diatasi dengan sebuah program yang dibentuk menggunakan pendekatan metode graf berbobot berarah dan pohon keputusan. Input pada program ini adalah koordinat awal posisi perangkat GPS dan koordinat tujuan serta lintasan / jalan-jalan yang terdapat pada peta dari koordinat awal menuju koordinat akhir yang sudah diproses dan diubah menjadi graf berbobot berarah dengan bobot sebagai hambatan, panjang lintasan dan kepadatan jalan seperti yang sudah dibahas pada upabab Graf. Data berupa graf tersebut kemudian diterima dan dianggap sebagai input pada program yang akan ditelusuri satu per satu di setiap simpul. Dengan menggunakan metode pohon keputusan maka setiap cabang jalan ditelusuri dan dipilih mana yang memeiliki total bobot terkecil sampai ke tempat tujuan maka itulah solusi dan pilihan jalan terbaik. Dalam program ini pasti ada sebuah algoritma yang membuat program ini berfungsi dan dapat menghasilkan sebuah solusi. Sekarang kita akan melakukan pendekatan terhadap algoritma sistem navigasi GPS dengan metode yang sudah kita bahas sebalumnya yaitu pohon keputusan. Akar dari pohon tersebut menyatakan pilihan pada simpul awal graf, dan anak-anak dari akar tersebut merupakan keputusan yang diambil. Lalu daun dari pohon keputusan tersebut adalah solusi-solusi untuk masalah yang dihadapi, dalam hal ini yaitu penentuan rute/ jalur terbaik menuju tempat tujuan. Setiap simpul pada pohon keputusan menyatakan perhentian pada setiap titik acuan pada graf dan kita kembali dihadapkan pada pilihan akan jalan mana yang akan dipilih lalu anak-naka dari simpul tersebut menyatakan pilihan yang diambil dan kembali dihadapkan pada pilihan akan cabang jalan berikutnya, begiru seterusnya proses algoritma akan berlanjut sampai tiba di tempat tujuan. Oleh karena terjadi pengulangan proses yang sama pada setiap simpul maka algoritma yang menggunakan rekursif mungkin dapat menjadi solusi yang baik. Dengan basis tertentu dan pengulangan (loop) maka setiap kemungkinan pilihan jalan pada graf dari tempat awal ke tempat tujuan dapat ditelusuri sehingga diperoleh bobot untuk setiap lintasan. Solusi dari setiap lintasan kemudian akan diambil sebagai input untuk algoritma berikutnya yang akan mencari lintasan dengan bobot terkecil sehingga masalah dapat teratasi dengan solusi terbaik. Lalu data tersebut akan dikirimkan kembali pada perangkat GPS dan mengubah solusi tersebut menjadi jalur / lintasan pada peta dari posisi awal menuju tempat tujuan. Perangkat GPS kemudian akan mengubah data lintasan yang sudah diterimanya menjadi komando untuk menginformasikan pada pengguna saat yang tepat untuk berbelok, lurus, berputar dan sebagainya serta memberikan informasi berapa jauh lagi jarak yang harus ditempuh untuk sampai ke titik acuan berikutnya atau untuk tiba di tempat tujuan.

Pendekatan dengan menggunakan graf berbobot berarah dan pohon keputusan merupakan salah satu cara untuk merepresentasikan persoalan GPS ini dan algoritma untuk memperoleh solusi terbaiknya. Meskipun dari segi kompleksitas algoritma cara pendekatan ini kurang efektif, yaitu memiliki orde T(N) = O(nh) dimana n adalah jumlaha maksimum cabang dari sutu simpul dan h adalah maksimum kedalaman/ tinggi pohon keputusan yang terbentuk. Orde eksponensial untuk kompleksitas algoritma tersebut adalah kasus waktu terburuk dimana semua simpul mempunyai cabang maksimal n dan semua solusi tercapai pada kedalamn maksimal dari pohon. Jadi cara pendekatan dengan pohon keputusan ini mungkin bukan yang paling efektif karena algoritmanya yang kompleks tetapi cara pendekatan ini mudah dipahami. Dan cara ini juga cukup sistematis dengan penelusuran pada setiap jalur sahingga bobot untuk masing-masing jalur yang ada untuk mencapai tempat tujuan dapat diketahui pada setiap daun. Jadi sebagai sarana atau metode untuk menjelaskan persoalan dalam mencari jalur terbaik metode ini adalah jalan paling baik dan efektif karena setiap jalan yang ditelusuri diperoleh bobot akhirnya sehingga ada perbandingan yang jelas antara setiap kemungkinan jalur yang diambil.

Berikut akan diberikan contoh soal sederhana dan pembahasannya.

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.

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. Apa bila 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.

6. KESIMPULAN

Metode graf dan pohon keputusan dapat menjadi suatu kunci menuju solusi dari suatu permasalahan apabila kita dapat memanfaatkannya dengan cermat dan pada tempat yang tepat.

Graf berarah dan berbobot serta pohon keputusan merupakan salah satu bahasan dalam mata kuliah Struktur Diskrit. Algoritma sederhana dalam mengambil keputusan serta solusi akhir dan metode pengulangan dengan rekursif juga merupaka salah satu bahasan dalam mata kuliah Struktur Diskrit serta Algoritma dan Struktur Data. Hal ini menunjukkan bahwa dalam membuat sistem navigasi GPS yang berfungsi sempurna perlu perpaduan yang harmonis dan tepat antara satu bidang ilmu dengan bidang ilmu yang lain.

Peran manusia sebagai penemu, pengendali dan yang dapat mengembangkan teknologi dan algoritma penyusun sistem navigasi GPS ini sebaiknya paham dan mengerti bagaimana cara kerja sistem yang dibuatnya. Tidak hanya sebagai pengguna yang dikendalikan oleh teknologi yang dibuatnya, tetapi manusia cerdas yang dapat memnfaatkan sarana dan teknologi yang dibuatnya secara maksimal dan bertanggung jawab.

Jadi, suatu masalah dapat terpecahkan apabila suatu ilmu dan ilmu-ilmu yang lain saling melengkapi untuk membuat suatu solusi. Suatu bidang ilmu tidak dapat berdiri sendiri tanpa bantuan bidang ilmu yang lain dalam aplikasinya di kehidupan nyata untuk berfungsi secara sempurna. Oleh karena itu diperlukan kerjasama antar bidang ilmu tersebut dan hal tersebut tidak mungkin terwujud tanpa peran manusia di dalamnya.