MATEMATIKA DISKRIT - LINTASAN TERPENDEK (SHORTEST PATH)

KATA PENGANTAR

Puji syukur kehadirat allah swt dengan segala kerahmatan nya saya masih diberikan kesehatan serta kesempatan dalam menyusun tugas makalah matematika diskrit. Dalam hal ini saya sangat puas dengan hasil dan bahan yang sudah saya siapkan sebelumnya.
Makalah ini membahas tentang materi matematika diskrit yaitu graf. Graf sangat erat kaitannya dengan kehidupan sehari-hari kita. Misalnya pada sebuah jalan, ataupun pada rambu-rambu lalu lintas. Graf sendiri mempunyai persoalan yang unik, salah satunya pada lintasan terpendek (shortest path). Graf yang digunakan dalam pencarian lintasan terpendek adalah graf berbobot (weight graph). Disini juga saya menyajikan algoritma dalam graf dan pembahasannya. Semoga tugas ini dapat menambah wawasan saya serta pembacanya juga sekaligus menambah nilai pada perkuliaan saya.
Matematika diskrit merupakan mata kuliah yang fundamental dalam pendidikan ilmu komputer atau teknik informatika. Saat ini matematika diskrit merupakan mata kuliah wajib pada program pendidikan yang termasuk ke dalam kelompok teknologi informasi.



BAB I LATAR BELAKANG

Matematika merupakan suatu bidang ilmu yang banyak digunakan untuk menyelesaikan berbagai permasalahan yang muncul dalam kehidupansehari-hari. Berbagai permasalahan tersebut ada yang dapat di modelkan kedalam suatu model matematika namun ada pula beberapa permasalahan yang tidak dapat dimodelkan ke dalam model matematika.
Masalah di luar bidang matematika biasanya akan dibawa ke dalam penyelesaian matematika, yaitu dengan mencari model matematikanya. Suatu permasalahan akan semakin mudah dipelajari, dipahami dan diselesaikan jika dapat dimodelkan ke dalam suatu model matematika .
Setelah diperoleh model matematika dari suatu masalah, maka masalah tersebut akan dibawa ke dalam cabang-cabang ilmu matematika untuk menentukan penyelesaiannya. Salah satu cabang ilmu matematika yang dapat digunakan untuk menyelesaikan permasalahan tersebut adalah teori graph.Graph G terdiri dari himpunan tak kosong dari elemen-elemen yang disebut titik (vertex) dan daftar pasangan berurutan dari elemen-elemen yang disebut sisi (edge).
Himpunan titik dari graph G disebut himpunan titik dari G dinyatakan dengan V(G) dan daftar sisi dari G dinyatakan dengan E(G). SuatuGraph G = (V,E) menyatakan graph G dengan himpunan titik-titik V(G) dan himpunan sisi E(G).Terdapat banyak konsep dalam graph, salah satunya adalah lintasan terpendek (Shortest Path) yang merupakan salah satu topik yang mampu mendukung penerapan graph dalam berbagai bidang ilmu.


BAB II KAJIAN TEORI 2.1

Konsep Dasar Graph
Teori Graph merupakan salah satu cabang ilmu matematika yang sering diterpakan dan dimanfaatkan dalam kehidupan sehari-hari, ada beberapa contoh permasalahan yang bisa diselesaikan dengan menggunakan teori Graph. Contohnya pembahasan ini menyangkut pada LINTASAN TERPENDEK (SHORTEST PATH). Permasalahan di atas dapat dibentuk sebagai graph yang digambarkan dengan titik dan garis. Garis yang menghubungkan titik pada graph tersebut disebut titik.

Lintasan terpendek merupakan salah satu masalah yang dapat diselesaikan dengan menggunakan graph. Jika diberikan sebuah graph berbobot, masalah lintasan terpendek adalah bagaimana kita mencarisebuah jalur pada graph yang meminimumkan jumlah bobot sisi pembentuk jalur tersebut. Terdapat bermacam persoalan lintasan terpendek antara lain:

1. Lintasan terpendek antara dua buah simpul tertentu (a pair shortestpath).
2. Lintasan terpendek antara semua pasanggan simpul (all pairs shortestpath)
3. Lintasan terpendek dari simpul tertentu ke semua simpul yang lain(single-source shortest path).
4. Lintasan terpendek antara dua buah simpul yang melalui beberapasimpul tertentu (intermediate shortest path).

BAB III PEMBAHASAN 3.1
Algoritma-Algoritma Lintasan terpendek(shortest path)
1.Algoritma Greedy
Algoritma Greedy adalah algoritma yang memecahkan masalah langkah demi langkah, pada setiap langkah dilakukan dengan cara:
oMengambil pilihan yang terbaik yang dapat diperoleh saat itu
oBerharap bahwa dengan memilih optimum local pada setiaplangkah akan mencapai optimum global.
Langkah-langkah algoritma greedy:

1. Menentukan titik awal dan titik tujuan, misalnya titik awal a.
2. Periksa semua sisi yang langsung bersisian dengan titik a. Pilih sisi yang bobotnya terkecil. Sisi ini menjadi lintasan terpendek pertama, sebut saja L(1).
3. Tentukan lintasan terpendek kedua dengan cara berikut:
4. Hitung: d(i) = panjang L(1) + bobot sisi dari simpul akhir L(1) kesimpul i yang lain.
5. Pilih d(i) yang terkecil.
6. Bandingkan d(i) dengan bobot sisi (a, i). Jika bobot sisi (a, i) lebihkecil daripada d(i), maka L(2) = L(1) U (sisi dari simpul akhir L(i)ke simpul i)
7. Dengan cara yang sama, ulangi langkah 2 untuk menentukanlintasan terpendek berikutnya.

Kelebihan algoritma Greedy:
Prinsip pencarian lintasan terpendek memakai fungsi ” Seleksi” dan itu berguna untuk menentukan jalan tersingkat untuk menuju suatu tempat. Sehingga, kita dapat sampai tepat waktu menuju tempat tujuan. Hasil analisis berdasarkan bobot-bobot yang berbeda, menunjukkan bahwa semakin banyak bobot yang diberikan, maka semakin akurat pula data yang dihasilkan. Sehingga menghasilkan waktu yang efisien.

Kekurangan algoritma Greedy:
Algoritma greedy tidak beroperasi secara menyeluruh terhadap semua alternatif solusi yang ada (sebagaimana pada metode exhaustive search).
oPemilihan fungsi Seleksi: Mungkin saja terdapat beberapa fungsi Seleksi yang berbeda, sehingga kita harus memilih fungsi yang tepat jika kita ingin algoritma bekerja dengan benar dan menghasilkan solusiyang benar-benar optimum. Karena itu, pada sebagian masalah algoritma greedy tidak selalu berhasil memberikan solusi yang benar-benar optimum.

Contoh :Permasalahan :
“Carilah jalur terpendek dari titik kuning ke titik biru”
Pilihan awal yang dipilih algoritma adalah a karena a lebih pendek daripada d. Pilihan selanjutnya hanya satu sehingga tidak ada pilihan lain selain b. Lalu ke c dan ke tujuan akhir. Maka jaraknya adalah 10,5. Padahal jika menggunakan jalur satu lagi sebesar 7. Begitu seterusnya Jika jarak a ke b adalah 1000. Algoritma ini tidak bisa mundur, sehingga memilih b.
Padahal nilainya sangat besar. Disanalah kelemahan algoritma ini. Tetapi dengan tidak pernah mundur ke tempat awal untuk mencari jalan alternatif. Algoritma ini cepat dalam menyelesain pencarian lintasan tercepat.

2. Algoritma Djikstra
Strategi ini merupakan strategi yang paling terkenal untuk mencari lintasan terpendek. Algoritma Dijkstra diterapkan pada graf berarah, tetapi selalu benar untuk graf tak-berarah. Strategi ini menggunakan strategi Greedy sebagai berikut: “Pada setiap langkah, ambil sisi yang berbobot minimumyang menghubungkan sebuah simpul yang sudah terpilih dengan sebuah simpul lain yang belum terpilih. Lintasan dari simpul asal ke simpul yang baru haruslah merupakan lintasan yang terpendek diantara semua lintasannya ke simpul simpul yang belum terpilih.

Langkah-langkah dalam menentukan lintasan terpendek pada algoritma Dijkstra yaitu:

1. Pada awalnya pilih titik dengan bobot yang terendah dari titik yang belum terpilih, diinisialisasikan dengan „0‟ dan yang sudah terpilih diinisialisasikan dengan „1‟.
2. Bentuk tabel yang terdiri dari titik, status, bobot dan redecessor. Lengkapi kolom bobot yang diperoleh dari jarak titik sumber kesemua titik yang langsung terhubung dengan titik sumber tersebut.
3. Jika titik sumber ditemukan maka tetapkan sebagai titik terpilih.
4. Tetapkan titik terpilih dengan label permanen dan perbarui titik yang langsung terhubung.
5. Tentukan titik sementara yang terubung pada titik yang sudahterpilih sebelumnya dan merupakan bobot terkecil dilihat dari tabeldan tentukan sebagai titik terpilih berikutnya.
6. Apakah titik yang tepilih merupakan titik tujuan? Jika ya, makakumpulan titik terpilih atau predecessor merupakan rangkaian yangmenunjukkan lintasan terpendek.
7. Begitu seterusnya sampai semua titik terpilih.

Contoh :

Dari graph diatas tenetukan lintasan terpendek dari titik A ke titik F.
Dengan menggunakan program, diperoleh lintasan terpendek dari titk A ketitik F sebagai berikut .Diperoleh lintasan terpendek yaitu A-E-D-F dengan bobot total sebesar 22.
(Mencari lintasan terpendek dari simpul a ke semua simpul lain }
Langkah 0 (inisialisasi):
- inisialisasi si = 0 dan di = mai untuk i = 1, 2, ..., n

Langkah 1:
- isi sa dengan 1 (karena simpul a adalah simpul asal lintasan terpendek, jadi sudah pasti terpilih)
- isi da dengan ¥ (tidak ada lintasan terpendek dari simpul a ke a)

Langkah 2, 3, ..., n-1:
- cari j sedemikian sehingga sj = 0 dan dj = min{d1, d2, ..., dn}
- isi sj dengan 1
- perbarui di, untuk i = 1, 2, 3, …, n dengan:
di (baru) = min{di (lama), dj + mji }.

Tentukan lintasan terpendek dari simpul 1 ke semua simpul lain.

Jadi, lintasan terpendek dari:

• 1 ke 3 adalah 1, 3 dengan panjang = 10
• 1 ke 4 adalah 1, 3, 4 dengan jarak = 25
• 1 ke 2 adalah 1, 3, 4, 2 dengan jarak = 45
• 1 ke 5 adalah 1, 5 dengan jarak = 45
• 1 ke 6 tidak ada

Contoh 6.34. Tinjau graf berarah pada Gambar 6.50 yang menyatakan jarak beberapa kota di Amerika Serikat.

Tentukan lintasan terpendek dari simpul 5 ke semua simpul lain.

Jadi, lintasan terpendek dari:

• 5 ke 6 adalah 5, 6 dengan panjang = 250
• 5 ke 7 adalah 5, 6, 7 dengan jarak = 1150
• 5 ke 4 adalah 5, 6, 4 dengan jarak = 1250
• 5 ke 8 adalah 5, 6, 8 dengan jarak = 1650
• 5 ke 3 adalah 5, 6, 4, 3 dengan jarak = 2450
• 5 ke 2 adalah 5, 6, 4, 3, 2 dengan jarak = 3250
• 5 ke 1 adalah 5, 6, 8, 1 dengan jarak = 3350

3. Algoritma Bellman-Ford
Algoritma Bellman-Ford merupakan algoritma untuk mencari shortest path, dengan menghitung jarak terpendek pada sebuah graf berbobot, atau menghitung semua jarak terpendek yang berawal dari satu titik node. Langkah-langkah:

1. Tentukan vertex source dan daftar seluruh vertices maupun edges.
2. Assign nilai untuk distance dari vertex source = 0, dan yang lain infinite
3. Mulailah iterasi terhadap semua vertices yang dimulai dari Vertexsource
4. Untuk menentukan distance dari semua vertices yang berhubungandengan vertex source dengan formula seperti berikut ini :- U = vertex asal- V = vertex tujuan- UV = Edges yang menghubungkan U dan V- Jika distance V, lebih kecil dari distance U + weight UV maka distance V, diisi dengan distance U + weight UV- Lakukan hingga semua vertex terjelajahi
5. Untuk mengecek apakah ada negative cycle dalam graf tersebut lakukan iterasi untuk semua edges yang ada, kemudia lakukan penge-cek-an seperti dibawah ini :
6. Untuk semua edges UV, jika ada distance vertex U + weight edges UVkurang dari distance vertex V maka sudah jelas bahwa graf tersebutmemiliki negative cycle.

Contoh:Dari graph di atas tentukan lintasan terpendek dari titik 1 ke titik 4. Langkah-langkah:

1. Tahap pertama adalah tahap inisialisasi yaitu dengan melabeli titik awal atau titik asal yaitu titik 1 dengan 0 dan titik-titik lainnya dengan ∞.d(1,1)< 0 untuk masing-masing v anggota V – {s} maka d(s,v)< ∞
2. Tahap kedua yaitu tahap proses iterasiUntuk masing-masing sisi (1,2) anggota E makaJika d(1,2) > d(1,2)+w(2,3) makad(1,2) diganti dengan d(1,2)+w(2,3)Akhirnya diperoleh d(1,4)=5+4+4=13.

  KESIMPULAN 4.1

1. Algoritma Greedy
Dengan menggunakan algoritma greedy didapatkan bobot total sebesar13,38 km, tetapi hasil ini tidak optimal karena dengan menggunakan algoritma yang lain didapatkan hasil dengan jarak yang lebih pendek.Algoritma ini memiliki kelebihan yaitu cepat dalam proses pencarianlintasan terpendeknya. Sedangkan kekurangannya yaitu tidak optimal danada kemungkinan gagal dalam pencarian dan mungkin lintasan yang diperoleh bukanlah yang terpendek.
2. Algoritma Dijkstra
Dalam algoritma dijkstra juga menggunakan prinsip greedy yang menyatakan bahwa pada setiap langkah kita memilih sisi yang berbobot minimum dan memasukannya kedalam himpunan solusi. Selain itu algoritma dijkstra paling terkenal dari algoritma lainnya karena dijkstra diterapkan mencari lintasan terpendek pada graf berarah. Namun, juga benar untuk graf tidak berarah.

DAFTAR PUSTAKA

• Ilmu diskrit revisi 5, rinaldi munir. 2010
• Teori graph, santoso. 1993
• Michael, J. D., Rosen, K.H. 1991.
• Application of Discrete Mathematics.

Semoga bermanfaat....,

ARTIKEL TERKAIT :