Heru C Rustamaji

Pak dosen juga nge-Blog

Algoritma Greedy

Cara kerja algoritma ini adalah dengan membuat suatu rangkaian keputusan/pilihan, dimana masing masing merupakan pilihan pada posisi tersebut. Sekali suatu keputusan dipilih, maka tidak ada jalan untuk melakukan backtracking. Bentuk umumnya adalah :

while (problem belum selesai)

{

buat pilihan terbaik yang feasible

}

Contoh penyelesaian menggunakan algoritma greedy ini adalah mencari pohon perentang minimum, baik menggunakan Prim maupun Kruskal

Pohon perentang minimum
Misalkan G = (V, E) adalah suatu graph tidak berarah, terhubung, dan mempunyai bobot yang non negatif. Maka pohon perentang minimum adalah subgraph G yang mempunyai sifat
berupa pohon
Mengandung semua simpul pada G
Mempunyai jumlah bobot pada busur yang minimum.


Y = {v0} untuk setiap v0 āˆˆ V

while (Y = V )

{

Cari busur (u,v)dengan bobot minimum dengan u āˆˆ Y

dan v āˆˆ/ Y

Masukkan busur (u, v) pada MST
Tambahkan v pada Y

}

Kode programnya adalah sebagai berikut

for (i = 1; i <= n; i ++)

{

V [i] . Reached = FALSE;

V [i] . Connect_Wt = INFINITY;

}

V [Start] . Connect_Wt = 0;

V [Start] . Connect_From = 0;

for (i = 1; i <= n; i ++)

{

Min_Connect = INFINITY;

for (j = 1; j <= n; j ++)

if (V [j] . Connect_Wt < Min_Connect)

{

Min_Connect = V [j] . Connect_Wt;

Min_V = j;

}

V [Min_V] . Reached = TRUE;

for (j = 1; j <= n; j ++)

if (! V [j] . Reached

&& Weight [Min_V] [j]

< V [j] . Connect_Wt)

{

V [j] . Connect_Wt = Weight [Min_V] [j];

V [j] . Connect_From = Min_V;

}

}

Algoritma Kruskal
Tempatkan masing masing simpul sebagai himpunan terpisah
for ( setiap busur (u,v) yang diurutkan bobotnya secara ascending)
if (u dan v berada dalam himpunan terpisah)
{
Masukkan busur (u,v) dalam MST
gabungkan himpunan yang mengandung u dan v
}

Inilah potongan programnya

for (i = 1; i <= n; i ++)

{

V [i] . Reached = FALSE;

V [i] . Connect_Wt = INFINITY;

}

V [Start] . Connect_Wt = 0;

V [Start] . Connect_From = 0;

for (i = 1; i <= n; i ++)

{

Min_Connect = INFINITY;

for (j = 1; j <= n; j ++)

if (V [j] . Connect_Wt < Min_Connect)

{

Min_Connect = V [j] . Connect_Wt;

Min_V = j;

}

V [Min_V] . Reached = TRUE;

for (j = 1; j <= n; j ++)

if (! V [j] . Reached

&& Weight [Min_V] [j]

< V [j] . Connect_Wt)

{

V [j] . Connect_Wt = Weight [Min_V] [j];

V [j] . Connect_From = Min_V;

}

}

Kira kira, ada yang bisa bantu tentukan kompleksitasnya …???

Iklan

Mei 17, 2008 - Posted by | Uncategorized

3 Komentar »

  1. wah listingnya bener-bener greedy
    sampe berkunang-kunang bacanya

    Komentar oleh konco lawas | Juni 11, 2008 | Balas

  2. pak,boleh minta materi ttg alg. greedy gak?

    Komentar oleh henry | September 16, 2008 | Balas

  3. PAK BOLEH MINTA MATERI TENTANG ALGORITMA GREEDY GK?

    Komentar oleh HARIS KURNIAWAN | Oktober 19, 2008 | Balas


Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

%d blogger menyukai ini: