Algoritma Greedy dan Algoritma Prim

BAB I

PENDAHULUAN

        latar Belakang

Graf adalah salah satu metode yang sering digunakan untuk mencari solusi dari permasalahan diskrit dalam dunia nyata. Dalam kehidupan sehari-hari, graf digunakan untuk menggambarkan struktur yang ada. Tujuannya adalah sebagai visualisasi objek-objek agar lebih mudah dimengerti. Graf mempunyai banyak konsep, salah satunya adalah konsep pohon. Konsep ini mampu mendukung penerapan graf dalam berbagai bidang ilmu. Aplikasi yang menggunakan konsep pohon ini adalah pembangunan jalan dan rel kereta api, pembuatan jaringan computer, mencari jalur pemeliharaan dengan bobot biaya yang minimum. Masalah ini dapat dipecahkan dengan menggunakan pohon merentang minimum (minimum spanning tree). Dan algoritma algoritma greedy merupakan metode paling sesuai untuk memecahkan persoalan optimasi. Algoritma greedy adalah algoritma yang memecahkan maslah langkah perlangkah dimana pada setiap langkah dibuat pilihan optimum (local optimum) dengan harapan bahwa langkah berikutnya mengarah ke solusi optimum global (global optimum). Algoritma greedy membuat keputusan berdasarkan pilihan yang ada sekarang, tidak melihat pilihan yang akan muncul kemudian. Terkadang algoritma greedy mengambil keputusan yang diambil terlalu dini tanpa melihat yang akan ditemui berikutnya sehingga menimbulkan apa yang disebut ³good next move, bad overall move´.

Melihat kelemahan yang dimiliki, solusi optimum global yang didapatkan belum tentu merupakan solusi optimum (terbaik) karena algoritma greedy tidak beroperasi secara menyeluruh terhadap semua alternatif solusi yang ada. Namun begitu algoritma ini tetap merupakan pilihan utama untuk memecahkan permasalahan sederhana karena metode ini yang paling cepat dibandingkan dengan metode yang lainnya. Metode ini juga dapat memberikan solusi hampiran atau aproksimasi terhadap nilai optimum yang diinginkan dan hasil yang diberikan masih merupakan solusi yang layak (feasible solution). Algoritma yang termasuk ke dalam algoritma greedy antara lain kode Huffman, algoritma Djikstra, algoritama Prim dan algoritma Kruskal yang digunakan dalam menyelesaikan permasalahan optimasi pada graf. Karena kasus yang dipakai untuk memecahkan permasalahan dalam membangun pohon merentang minimum, maka algoritma yang ada dan dapat digunakan adalah algoritma Prim dan algoritma Kruskal.

  Rumusan Masalah

.     1. Apa yang dimaksud dengan algoritma greedy?

      2. Apa yang dimaksud algoritma prim?

  tujuan

      1. untuk mengetahui algoritma greedy

     2. untuk mengetahui algoritma prim

BAB II

PEMBAHASAN

      1. Algoritma Greedy

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, begitupun algoritma greedy biasanya memberikan solusi yang mendekati nilai optimum dalam waktu yang cukup cepat.

Algoritma greedy memecahkan masalah dengan cara step by step, dengan langkahnya sebagai berikut :

1.      Memilih langkah yang terbaik pada saat itu tanpa memprediksi kedepannya.

2.      Memilih optimum lokan dan berakhir optimum global.

Secara umum algoritma greedy disusun oleh elemen-elemen berikut :

a.       Himpunan kandidat

b.      Himpunan solusi

c.       Fungsi seleksi (selection function)

d.      Fungsi kelayakan (feasible)

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:

Jalur dari Titik A ke B

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:

Graph Sederhana dari Titik A ke B

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:

Graph 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 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 mengapliikasikan langkah-langkah di atas pada graph A ke B sebelumnya maka kita akan mendapatkan pergerakan seperti berikut:

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

Langkah Pertama Greedy

ü  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.

Langkah Kedua Greedy

1.                  Local maximum adaah ke D, dengan jarak 6.

2.                  Tandai C sebagai titik yang telah dikunjungi, dan pindah ke D.

Langkah Ketiga Greedy

3.                  (Langkah selanjutnya diserahkan kepada pembaca sebagai latihan).

Dengan menggunakan algoritma greedy pada graph di atas, hasil akhir yang akan didapatkan sebagai jarak terpendek adalah A-C-D-E-F-B. Hasil jarak terpendek yang didapatkan ini tidak tepat dengan jarak terpendek yang sebenarnya (A-G-E-F-B). Algoritma greedy memang tidak selamanya memberikan solusi yang optimal, dikarenakan pencarian local maximum pada setiap langkahnya, tanpa memperhatikan solusi secara keseluruhan.

b.      Minimum Spanning Tree

Pencarian biaya yang minimum dari suatu graph sehingga membentuk pohon.

Syarat graph yang didapat dicari minimum spanning treenya :

a.       Graph harus terhubung

b.      Kuasnya punya bobot

c.       Grap tidak berarah

Algoritma yang dipakai untuk menentukan minimum spanning tree :a.

a.       Algoritma kruskal

b.      Algoritma solin

c.       Algoritma prim

a   2.  Algoritma Prim

Algoritma Prim adalah sebuah algoritma dalam graph theory untuk mencari pohon rentang minimum untuk sebuah graf terhubung berbobot. Mudahnya, Algoritma Prims adalah salah satu aplikasi yang digunakan untuk mencari rentang minimum. Untuk lebih jelas akan saya berikan contoh dengan gambar 

Terdapat sebuah rangkaian seperti pada gambar di atas. Setiap titik disebut dengan vertex. Terdapat 6 vertex yaitu A, B, C, D, E, dan F.Yang ingin dilakukan di sini adalah menghubungkan semua vertex yang ada dengan melalui jalur yang menghabiskan cost paling minimal. Dengan menggunakan algoritma prim kita dapat menentukan jalur tersebut.

Adapun langkah-langkah penyelesainnya adalah sebagai berikut :

1. Tentukan titik start. Dalam kasus ini saya tentukan titik startnya adalah vertex B.

2. Kemudian buatlah dua buah himpunan. Misalkan himpunan T dan S. Dimana elemen dari T adalah vertex-vertex yang sudah saling terhubung dan elemen himpunan S adalah vertex-vertex yang belum terhubung. Pada akhir proses, seluruh elemen F akan berpindah menjadi elemen T dan F menjadi himpunan kosong.

3. Pada awal proses elemen T hanyalah vertex yang menjadi titik start (vertex B) dan himpunan F berisi vertex-vertex sisanya.

4. T={B} ; F={A,C,D,E,F}

 

B(- , -) : A(B,1) D(B,1) C(B,5) E(- , – ) F(- ,  -)

Tuliskan semua vertex yang memiliki kemungkinan terhubung dengan vertex B secara langsung. Penulisan A(B,1) artinya titik A bisa dihubungkan secara langsung dengan vertex B(titik start) dengan cost 1. Pada langkah ini vertex E dan F tidak dapat terhubung secara langsung sehingga kita menuliskannya dengan E(- ,  – ) dan F(- ,  -). Kemudian pilihlah jalur yang menghabiskan cost paling minimal. Pada langkah ini terdapat 2 jalur yang memiliki cost paling minimum, pilih saja yang lebih dulu yaitu A(B,1). Dan selanjutnya himpunan T dan F menjadi T={B,A} ; F={ C,D,E,F} .

5. T={B,A} ; F={C,D,E,F}

A(B , 1) : D(B,1) C(A,3) F(A , 3 ) E(- , -)

Saat ini vertex B dan A telah terhubung. Kemudian tuliskan semua kemungkinan vertex yang bisa dihubungkan secara langsung dengan vertex – vertex yang telah saling terhubung (bisa vertex A atau B). Pada langkah ini vertex E tidak memiliki kemungkinan dihubungkan secara langsung maka dituliskan dengan E(- , – ). Kemudian pilih jalur yang menghabiskan cost paling kecil.

 

6. T = {B,A,D}; F= {C,E,F}

D(B,1)  C(D,2) E (D,4) F ( A,3)

7. T = { B,A,D,C } ; F = { E,F}

E(D,2); E (C,1) F(A,3)

8. T = { B,A,D,C} ; F {C,D,E,F}

E(C,1); F (A,3)

9. selesai semua vertex telah terhubung dengan cost 8 ( cost optimal )

Begitulah cara kerja dari algoritma prim.

  

 

BAB III

PENUTUP

A.                Kesimpulan

Algoritma yang digunakan dalam masalah pengoptimalan yaitu Algoritma Greedy. Lebih tepatnya memecahkan masalah pohon perentang minimum dengan menggunakan pendekatan algoritma Prim dan algoritma Kruskal yang merupakan bagian dari algoritma Greedy. 2. Konsep dasar yang dipakai algoritma Prim adalah dalam setiap langkah, sisi graf G yang dipilih adalah berbobot minimum dan terhubung dengan pohon perentang T yang terbentuk dan tidak membentuk sirkuit.