Algoritma Greedy serta Divide and Conquer

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:

1. Kunjungi satu titik pada grafik, dan ambil seluruh titik yang dapat dikunjungi dari titik sekarang.
2. Cari local maximum ke titik selanjutnya.
3. Tandai grafik sekarang sebagai graph yang telah dikunjungi, dan pindah ke local maximum yang telah ditentukan.
4. 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

Read More

Seberapa dewasa diri ini dalam menghadapi suatu masalah dan Bagaimana cara mengatasinya

Namaku Ahmad Hari Ramadhan , aku anak lelaki terkahir dari 3 bersaudara dimana kedua kakak aku bergender perempuan serta kedua orang tuaku berwirausaha di bidang Kayu Madura bisa di bilang Material Kayu namun di selingi berjualan barang mabel seperti lemari , meja , dan lain – lain . singkat cerita .

Menjadi anak lelaki satu – satunya dalam keluarga itu  memang begitu berat karena begitu banyak yang di tanggung jawabkan terhadap keluarga terlebih lagi menjadi anak lelaki satu – satunya terakhir dalam keluarga itu benar – benar membuat diri ini seakan tiada henti berpikir bagaimana kedepannya aku melangkah ? , bagaimana aku bisa membahagiakannya “kedua orang tua” ? , bagaimana aku bisa membantunya dalam hal pekerjaan ? yang sementara ini aku hanya seorang lelaki anak terakhir yang baru beranjak dari bangku sekolah menengah akhir serta  mempunyai kedua kakak perempuan , aku selalu bertanya kepada dia “umi”

aku : “mi saya ingin kerja ?”

Umi : “jangan dulu kamu kuliah aja dulu de “

Kalimat itu yang selalu umi nyatakan . tetapi di satu sisi umi selalu berkata

Umi : “gimana udah ngerti belum de sama harga – harga kayu ?

Nah ini salah satunya kalimat yang selalu membuat diri ini merasa geilsah seakan tah henti – hentinya mulai memikirkan “Bagaimana kalau aku tak mengeti apa – apa tentang harga – harga kayu yang selalu umi tanyakan kepadaku” di satu sisi kedua kakakku hanya berpikir iya udah itu urusan anak laki – laki . Seberat ini kah yang harus di tanggung diri ini . dahulu memang tak pernah terpikir sama sekali akan hal – hal seperti ini , aku selalu berpikir orang tua ku akan selalu dalam keadaan sehat di satu sisi aku tak pernah berpikir bahwa mereka nanti akan mengalami proses penuaan yang juga di selingi sakit . entah mengapa betapa polosnya diri ini saat itu , sehingga saat melihat mereka “kedua orang tua” mulai mengalami sakit – sakitan di karenakan usianya yang mulai memasuki kepala 5  ini langsung terlintas di pikiranku “mengapa takpernah sadar akan hal yang akan terjadi seperti ini” sehingga aku bisa memperlajari segalanya agar disaat masalah datang seperti ini diriku siap menghadapi.

Namun dimana ada masalah pasti ada cara mengatasinya ?

Nah disini aku mengatasi masalah seperti yang aku sudah paparkan diatas yaitu dengan:

1.      Gita belajar agar kelak bisa membuat mereka tersenyum bahagia melihat anak lelaki satu – satunya meraih gelar sarjana teknik aminn

2.      Membantu mereka dalam hal bekerja seperti :

a.      Mengantarkan kayu bila seseorang membeli beberapa kayu di material ini

b.      Ikut serta dalam hal membeli kayu serta dalam memilih barang-barang mabel

3.      Berlari pagi di pagi hari karena dengan berlari pagi dapat menyegarkan pikiran serta dapat membuat tubuh ini menjadi lebih sehat agar dalam membantu mereka tubuh ini selalu dalam keadaan yang maksimal .

Read More