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

ABDI KITA TERHADAP NEGARA

Bentuk pengabdian terhadap Negara yang dilakukan oleh setiap orang berbeda-beda. Tidak harus menjadi orang yang menekuni atau bekerja pada lingkup pemerintahan seperti polisi dan TNI, namun orang-orang yang telah mengharumkan nama Negara Indonesia dimata dunia pun merupakan salah satu bentuk pengabdian yang dilakukan terhadap Negara. Hal tersebut berarti mereka telah menunjukan kepada Negara lain bahwa Indonesia mampu bersaing pada persaingan global baik itu dalam hal SAINS, seni, maupun olahraga. So? Bentuk pengabdian apa yang telah saya lakukan untuk Negara? Jawabannya mungkin tidak sehebat anak-anak muda lainnya yang telah memberikan kebanggaan kepada Negara Indonesia di luar sana, namun tidak apa karena waktu masih terus berjalan saya yakin saya dapat melakukan hal yang luar biasa untuk Negari tercinta ini. Pengabdian yang telah saya lakukan adalah menaati peraturan yang berlaku di Negara ini, seperti apa bentuknya? Menaati peraturan lalu lintas, karena kebetulan saya seorang pengendara kendaraan pribadi, tidak menggunakan narkoba atau sejenisny yang dianggap akan merusak generasi muda, tidak membuang sampah disembarang tempat, menjalani perkuliahan sesuai aturan yang ada, tidak mengikuti tawuran pelajar, tidak mencuri, tidak pernah merusak fasilitas umum dan hal-hal kecil lainnya yang saya anggap sebagai bentuk pengabdian terhadap aturan negara. Sederhana bukan? Ya memang sangat sederhana, tetapi saya yakin apabila seluruh masyarakat Indonesia melakukan hal yang sama maka Negeri tercinta ini akan lebih maju.

Read More

Sinopsis dari lagu "Pesona Potretmu"

Pesona Potretmu

Intro:
Letih terlihat diwajah yang tua itu 
Tertidur pulas dalam alunan gelap malam
Dibalik senyummu teduhkanku 

Terbayang potret kala engkau masih muda
Ajarkan sebuah kata cinta dalam hidup 
Kekuatan kasihmu nyata pulihkan jiwaku yang kadang goyah
  
Waktu cepat bergulir
Sisakan banyak kisah
Dia yang kau cintai tlah lama meninggalkan dirimu sendiri 
Namun tetap kau berdiri tegak pada dunia




Reff :
Pesonamu masih jelas kurasa hingga kini 
Menemani hingga ku dewasa 
Derai airmata dan pengorbananmu takkan tergantikan 
Terima kasih ibu..


Sinopsis

Sinopsis dari lagu ini mengggambarkan sosok  ibu yang dimana pengorbanannya serta dedikasinya yang  begitu  amat besar dari sosok atau parasnya  yang masih muda hingga saat di masa tuanya begitu banyak mengajarkan arti dari sebuah kasih sayang dan kehidupan. dikala gundah selalu ada sosok ibu yang menenangkan hati.waktupun takterasa hingga saat dimana sosok seorang ibu telah tiada namun menyisakan banyak kenangan yang sangat melekat di hati ini. hingga dewasa ini  sosok seorang ibu masih terasa ada di benak ini , pengorbanannya takkan tergantikan oleh siapapun. Terima kasih ibu...

sumber  : http://lirik.kapanlagi.com/artis/ada_band/pesona_potretmu
 

Read More