Menggunakan Algoritma Untuk Menentukan Jalur Terpendek 

dalam menyelesaikan Suatu Permasalahan

I.      I.  Pendahuluan

         Pada awal diciptakan, komputer hanya di fungsikan sebagai alat hitung saja. Namun seiring dengan perkembangan jaman, maka peran komputer semakin mendominasi kehidupan. Lebih dari itu, komputer diharapkan dapat digunakan untuk mengerjakan segala sesuatu yang bisa dikerjakan oleh manusia baik dalam bidang pendidikan, kesehatan, industri, dan kehidupan sehari-hari sehingga peran komputer dan manusia akan saling melengkapi. Beberapa hal yang menjadi kekurangan manusia diharapkan dapat digantikan oleh komputer. Begitu juga dengan komputer yang tak akan berguna tanpa sentuhan manusia.Untuk menggunakan atau memfungsikan sebuah komputer maka harus terdapat program yang terdistribusi di dalamnya, tanpa program tersebut komputer  hanyalah menjadi sebuah kotak yang tak berguna. Program yang terdapat pada komputer sangat bervariasi dan setiap program tersebut pasti menggunakan algoritma.

Pencarian jalur terpendek merupakan suatu  masalah yang paling banyak dibahas dan dipelajari  sejak akhir tahun 1950. Pencarian jalur terpendek ini telah diterapkan di berbagai bidang untuk mengoptimasi kinerja suatu sistem, baik untuk meminimalkan biaya atau mempercepat jalannya suatu proses. Salah satu aplikasi pencarian jalur terpendek yang paling menarik untuk dibahas adalah  pada masalah transportasi.

Algoritma greedy merupakan jenis algoritma yang menggunakan pendekatan penyelesaian masalah dengan mencari nilai maksimum sementara pada setiap langkahnya. Nilai maksimum sementara ini dikenal dengan istilah local maximum. Pada kebanyakan kasus, algoritma greedy tidak akan menghasilkan solusi paling optimal, Sebagai contoh dari penyelesaian masalah dengan algoritma greedy, mari kita lihat sebuah masalah klasik yang sering dijumpai dalam kehidupan sehari-hari: mencari jarak terpendek dari peta. Misalkan kita ingin bergerak dari titik A ke titik B, dan kita telah menemukan beberapa jalur dari peta

II. Dasar Teori

A.      

   A.  Teori Graf

a.    Definisi Graf

     Graf adalah struktur diskrit yang terdiri dari simpul dan  busur, yang mengubungkan simpul-simpul tersebut. Notasinya adalah G=(V,E), dengan keterangan V adalah himpunan yang tidak kosong dari simpul-simpul. V={vi,v2,v3, ,,, ,Vn}, sedangkan E adalah himpunan sisi-sisi yang menghubungan sepasang simpul. E={e1,e2,e3, ,,, ,en}.

Secara geometri, graf digambarkan sebagai kumpulan noktah (simpul) di dalam bidang dwimatra yang dihubungkan dengan sekumpulan garis (sisi)

 

                 Gambar1. Graf Sederhana
Rinaldi Munir/IF2120 Matematika Diskrit

                   Gambar2. Graf ganda
Rinaldi Munir/IF2120 Matematika Diskrit

                  Gambar3. Graf semu
Rinaldi Munir/IF2120 Matematika Diskrit

  

b.       b. Terminologi Dasar

terminologi dasar graf yang digunakan:

1. Bertetangga (Adjacent)

Suatu simpul dikatakan bertetangga dengan simpul lainnya jika keduanya terhubung secara langsung oleh suatu sisi.

2. Bersisian (Incident)

Suatu sisi disebut bersisian dengan simpul tertentu apabila sisi tersebut terbentuk dari simpul tersebut.

3. Derajat (Degree

Derajat suatu simpul graf (takberarah) adalah jumlah sisi yang bersisian dengan simpul tersebut. Pada graf berarah, derajat simpul dihitung dari derajat-masuk (jumlah busur yang masuk ke simpul v) dan derajat-keluar (jumlah busur yang keluar dari simpul v).

4. Lintasan (Path)

Lintasan yang panjangnya n dari simpul awal v0 ke simpul tujuan vn di dalam graf G ialah barisan berselang-seling simpulsimpul dan sisi-sisi yang berbentuk v0, e1, v1,e2, … ,vn-1,en, vn. sedemikian sehingga e1 = (v0, v1), e2 = (v1, v2) adalah sisi-sisi dari G.

5. Sirkuit (Circuit)

Sirkuit pada graf adalah lintasan yang memilki titik awal dan titik akhir pada simpul yang sama.

   B.   Algoritma Greedy

Adalah algoritma yang memecahkan masalah langkah demi langkah dan merupakan salah satu metode dalam masalah optimasi. Prinsip dari algoritma greedy adalah “take what you can get now” yaitu mengambil pilihan yang terbaik yang dapat diperoleh pada saat itu tanpa memperhatikan konsekuensi kedepan. 

Algoritma greedy membentuk solusi langkah per langkah sebagai berikut:

1. Terdapat banyak pilihan yang perlu diekspolarasi pada setiap langkah solusi. Oleh karena itu, pada setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilhan. Keputusan yang telah diambil pada suatu langkah tidak dapat diubah lagi pada langkah selanjutnya.

2. Pendekatan yang digunakan di dalam algoritma greedy adalah membuat pilihan yang terlihat memberikan perolehan terbaik, yaitu dengan  membuat pilihan optimum lokal pada setiap langkah dan diharapkan akan mendapatkan solusi optimum global.

Algoritma greedy didasarkan pada pemindahan edge per edge dan pada setiap langkah yang diambil tidak memikirkan konsekuensi ke depan, greedy tidak beroperasi secara menyeluruh terhadap semua alternatif solusi yang ada serta sebagian masalah greedy tidak selalu berhasil memberikan solusi yang benar- benar oprimum tapi pasti memberikan solusi yang mendekati nilai optimum.

Algoritma greedy disusun oleh elemen-elemen sebagai berikut :

1.Himpunan Kandidat

   Himpunan ini berisi elemen-elemen yang memiliki peluang pembentuk solusi.

2.Himpunan Solusi

  Himpunan ini berisi kandidat-kandidat yang terpilih sebagai solusi persoalan. Elemennya terdiri dari elemen dalam himpunan kandidat, namun tidak semuanya dengan kata lain himpunan solusi ini adalah bagian dari himpunan kandidat.

3.Fungsi seleksi

   Fungsi yang pada setiap langkah memilih kandidat yang paling mungkin untuk menghasilkan solusi optimal.

Kandidat yang sudah dipilih pada suatu langkah tidak pernah dipertimbangkan lagi pada langkah  selanjutnya.

4.Fungsi kelayakan

  Fungsi yang memeriksa apakah suatu kandidat yang telah dipilih (diseleksi) dapat memberikan solusi yang layak.

5.Fungsi obyektif

  Fungsi yang memaksimumkan atau meminimumkan nilai solusi. Tujuannya adalah memilih satu saja solusi terbaik dari masing-masing anggota himpunan solusi.

III. Penerapan Algoritma Greedy Untuk Menentukan

      A. Lintasan Terpendek

Proses pencarian jalur terpendek akan penulis jelaskan pada gambar-gambar dan table-tabel di bawah ini.

Gambar4. Peta lintasan

Dari peta yang ditampilkan di atas, dapat dilihat bahwa terdapat beberapa jalur dari titik A ke titik B. Sistem peta pada gambar secara otomatis telah memilih jalur terpendek (berwarna biru). Penulis akan mencoba mencari jalur terpendek juga, dengan menggunakan algoritma greedy.

Dari gambar di atas, kita dapat melihat bagaimana sebuah peta jalur perjalanan dapat direpresentasikan dengan menggunakan graph, spesifiknya Directed Graph (graph berarah). Maka dari itu, untuk menyelesaikan permasalahan jarak terpendek ini kita akan menggunakan struktur data graph untuk merepresentasikan peta. Berikut adalah graph yang akan digunakan:

   

Langkah pertama yang harus kita lakukan tentunya adalah memilih struktur data yang tepat untuk digunakan dalam merepresentasikan peta. Jika dilihat kembali, sebuah peta seperti pada gambar di atas pada dasarnya hanya menunjukkan titik-titik yang saling berhubungan, dengan jarak tertentu pada masing-masing titik tersebut. Misalnya, peta di atas dapat direpresentasikan dengan titik-titik penghubung seperti berikut:

Gambar6. Graf Berarah dari titik A ke titik B

Untuk mencari jarak terpendek dari A ke B, sebuah algoritma greedy akan menjalankan langkah-langkah seperti berikut:

1.     Kunjungi satu titik pada graph, dan ambil seluruh titik yang dapat dikunjungi dari titik sekarang.

2.     Cari local maximum ke titik selanjutnya.

3.     Tandai graph sekarang sebagai graph yang telah dikunjungi, dan pindah ke local maximum yang          telah ditentukan.

4.     Kembali ke langkah 1 sampai titik tujuan didapatkan.

  Jika mengaplikasikan langkah-langkah di atas pada graph A ke B sebelumnya maka kita akan              mendapatkan pergerakan seperti berikut:

1.       Mulai dari titik awal (A). Ambil seluruh titik yang dapat dikunjungi.

·         Local maximum adalah ke C, karena jarak ke C adalah yang paling dekat. Tandai A sebagai titik yang telah dikunjungi, dan pindah ke C. Ambil seluruh titik yang dapat dikunjungi dari C.

   

  

Dengan menggunakan algoritma greedy pada graph di atas, hasil akhir yang akan didapatkan sebagai jarak terpendek adalah A-C-D-I-B. Hasi jarak terpendek yang didapatkan ini tidak tepat dengan jarak terpendek yang di sarankan oleh aplikasi google maps yaitu  (A-G-E-F-B).Walaupun jika di lihat dari jarak jika kita mengikuti lintasan berdasarkan penerapan algoritma greedy maka jaraknya lebih dekat yaitu 10.5km, sedangkan yang di sarankan oleh aplikasi google masps yaitu 11.7km. walaupun banyak pertimbangan untuk menentukan rute lintasan tersebut, salah satunya tingkat kemacetan di jalan raya, Algoritma greedy memang tidak selamanya memberikan solusi yang optimal, dikarenakan pencarian local maximum pada setiap langkahnya, tanpa memperhatikan solusi secara keseluruhan. Gambar berikut memperlihatkan bagaimana algoritma greedy dapat memberikan solusi.

IV.   Kesimpulan

        Penggunaan algoritma greedy dapat diterapkan dalam berbagai hal dalam kehidupan terutama yang berhubungan dalam penerapan mencari lintasan terpendek dengan hasil optimum .walaupun masih bias menggunakan kombinasi dengan algoritma atau metode lainnya untuk mendapatkan hasil yang lebih optimal tentunya.

By: blog basori alawi On November 21, 2018

Continue Reading