Heru C Rustamaji

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 …???