A. Greedy
Algoritma Dijkstra, (dinamai menurut penemunya, seorang ilmuwan komputer, Edsger Dijkstra), adalah sebuah algoritma rakus (greedy
algorithm) yang dipakai dalam memecahkan permasalahan jarak terpendek (shortest
path problem) untuk sebuah graf berarah
(directed graph) dengan bobot-bobot sisi (edge weights) yang
bernilai tak-negatif.
Misalnya, bila vertices dari sebuah graf melambangkan kota-kota dan
bobot sisi (edge weights) melambangkan jarak antara kota-kota tersebut,
maka algoritma Dijkstra dapat digunakan untuk menemukan jarak terpendek antara
dua kota.
Input algoritma ini adalah sebuah graf berarah yang berbobot (weighted
directed graph) G dan sebuah sumber vertex s dalam G danV adalah himpunan semua vertices dalam graph G.
Setiap sisi dari graf ini adalah pasangan vertices (u,v)
yang melambangkan hubungan dari vertex u ke vertex v. Himpunan semua tepi disebut E.
Bobot (weights) dari semua sisi dihitung dengan fungsi
w: E → [0, ∞)
jadi w(u,v) adalah jarak tak-negatif
dari vertex u ke vertex v.
Ongkos (cost) dari sebuah sisi dapat dianggap sebagai
jarak antara dua vertex, yaitu jumlah jarak semua sisi dalam jalur
tersebut. Untuk sepasang vertex s dan t dalam V, algoritma ini menghitung jarak terpendek dari s ke t.
contoh penggunaan metode greedy :
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).
Kita akan mencoba mencari jalur terpendek juga, dengan menggunakan algoritma
greedy.
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:
Dari gambar di atas, dapat melihat bagaimana
sebuah peta jalur perjalanan dapat direpresentasikan dengan menggunakan grafik, Maka dari itu, untuk
menyelesaikan permasalahan jarak terpendek ini kita akan menggunakan struktur
data graph untuk merepresentasikan peta. Berikut adalah graph yang akan
digunakan:
Grafik Berarah dari
Titik A ke B
Untuk mencari jarak terpendek dari A ke B,
sebuah algoritma greedy akan menjalankan langkah-langkah seperti berikut:
- Kunjungi satu titik pada grafik,
dan ambil seluruh titik yang dapat dikunjungi dari titik sekarang.
- Cari local maximum ke
titik selanjutnya.
- Tandai grafik sekarang sebagai
graph yang telah dikunjungi, dan pindah ke local maximum yang
telah ditentukan.
- Kembali ke langkah 1 sampai
titik tujuan didapatkan.
Jika mengapliikasikan langkah-langkah di atas
pada grafik A ke B sebelumnya maka disini akan mendapatkan pergerakan seperti gambar
di bawah ini
1.
Mulai dari titik awal (A)
kemudian ambil seluruh titik yang akan di kunjungi
Langkah pertama Greedy
1. Local
maximum adalah ke D, karena jarak ke D adalah yang paling dekat.
2. Tandai
A sebagai titik yang telah dikunjungi, dan pindah ke D.
3. Ambil
seluruh titik yang dapat dikunjungi dari D.
Langkah Kedua Greedy
4. Local
maximum adaah ke D, dengan jarak 11.
5. Tandai
C sebagai titik yang telah dikunjungi, dan pindah ke D
Langkah Ketiga Greedy
6. Local
maximum adaah ke F, dengan jarak 6.
7. Tandai
D sebagai titik yang telah dikunjungi, dan pindah ke F
8. Hingga
mencapai titik B maka Greedy telah selesai
B. Divide and Conquer
Di dalam ilmu komputer, algoritma divide and conquer merupakan algoritma yang sangat populer.
Prinsip dari algoritma ini adalah memecah-mecah masalah yang ada menjadi
beberapa bagian kecil sehingga lebih mudah untuk diselesaikan.
Langkah-langkah umum algoritma Divide and Conquer adalah:
Divide : Membagi masalah menjadi beberapa upa-masalah yang memiliki kemiripan dengan masalah semula namun berukuran
lebih kecil (idealnya berukuran hampir sama).
Conquer: Memecahkan (menyelesaikan) masing-masing upa-masalah (secara rekursif).
Combine: Menggabungkan solusi masing-masing masalah
sehingga membentuk solusi masalah semula.
Contoh penggunaan Divide And Conquer
Langkah Kerja Merge Sort
Proses
divide terjadi ketika kotak dan panah berwarna hitam, sementara conquer dan
combine terjadi ketika kotak dan panah diberi warna merah . Proses conquer
merupakan proses di mana kita mengurutkan elemen dalam list, dan combine adalah
ketika kita menggabungkan hasil urutan dari list tersebut.
sumber :
https://id.wikipedia.org/wiki/Algoritma_Dijkstra
https://id.wikipedia.org/wiki/Divide_and_Conquer
0 comments:
Post a Comment