Greedy yaklaşımı, graf üzerinde belirli bir konuda optimum sonucu veya en iyi sonucu bulabilmek amacıyla dolaşma yapılırken bir sonraki düğümü belirlemek için kullanılan bir karar verme yöntemidir. Greedy yaklaşımında o andaki seçenekler içerisinden en iyi olarak görünen seçilir. Greedy yönlü ve maliyetli graflarda kullanılır.
Örnek olarak 5 düğümlü bir graf 5x5 komşuluk matrisi şeklinde gösterilsin. Grafın şekli dizide gösterilmiştir.
#include<iostream>
#define N 5
#define EBAS 0x7FFFFFFF
using namespace std;
int maliyethesapla();
int GRAF[N][N]={ -1, 2, -1, -1, 5,
-1, -1, 1, 4, 2,
1, -1, -1, -1, 4,
12, -1, -1, -1, -1,
-1, -1, -1, 3, -1
};
int EKM[N];
int main()
{
int i;
maliyethesapla();
for (i=0;i<N;i++)
cout<<EKM[i]<<" ";
return 0;
}
int maliyethesapla()
{
char ELEALINDI[N]={0};
int i, j, ead, enkucuk;
for (i=1;i<=N;i++)
EKM[i]=EBAS;
EKM[0]=0;
ead=0;
for (i=0;i<N;i++)
{
for (j=0;j<N;j++)
if (!ELEALINDI[j])
if (GRAF[ead][j]!=-1)
if (EKM[j]>GRAF[ead][j]+EKM[ead])
EKM[j]=GRAF[ead][j]+EKM[ead];
enkucuk=EBAS;
for (j=1;j<N;j++)
if (!ELEALINDI[j])
if (EKM[j]<enkucuk)
{
enkucuk=EKM[j];
ead=j;
}
ELEALINDI[ead]=1;
}
}
Kaynak: Algoritma Geliştirme ve Veri Yapıları
Dr. Rıfat Çölkesen