ABSTRAK
Algoritma greedy adalah algoritma yang berusaha untuk menemukan solusi optimum dalam persoalan optimasi (optimization problem) dengan membentuk solusi langkah per langkah (step by step). Terdapat banyak pilihan yang perlu dieksplorasi pada setiap langkah solusi. Oleh karena itu, pada setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan. Keputusan yang telah diambil pada suatu langkah tidak dapat diubah lagi pada langkah selanjutnya. Pendekatan yang digunakan di dalam algoritma greedy adalah membuat pilihan yang “tampaknya” memberikan perolehan terbaik, yaitu dengan membuat pilihan optimum lokal (local optimum) pada setiap langkah
dengan harapan bahwa sisanya mengarah ke solusi optimum global (global optimum). Algoritma Greedy dapat menyelesaikan beberapa masalah dalam kehidupan nyata, yang akan kami bahas kali ini adalah :
- TSP (Travelling Sallesperson Problem)
I. PENDAHULUAN
Persoalan optimasi (optimization problems) yaitu persoalan yang menuntut pencarian solusi optimum.
Persoalan optimasi ada dua macam:
- Maksimasi (maximization)
- Minimasi (minimization)
Solusi optimum (terbaik) adalah solusi yang bernilai minimum atau maksimum dari sekumpulan alternatif solusi yang mungkin.
Elemen persoalan optimasi:
- Kendala (constraints)
- Fungsi Objektif (atau fungsi optimasi)
Solusi yang mengatasi semua kendala disebut solusi layak (feasible solution). Solusi layak yang mengoptimumkan fungsi optimasi disebut solusi optimum. Algoritma greedy merupakan metode yang paling populer untuk memecahkan persoalan optimasi dengan membentuk solusi langkah per langkah (step by step). Terdapat banyak pilihan yang perlu dieksplorasi pada setiap langkah solusi.Oleh karena itu, pada setiap langkah harus
dibuat keputusan yang terbaik dalam menentukan pilihan. Keputusan yang telah diambil pada suatu langkah tidak dapat diubah lagi pada langkah selanjutnya.Pendekatan yang digunakan di dalam algoritma greedy adalah membuat pilihan yang “tampaknya” memberikan perolehan terbaik,yaitu dengan membuat pilihan optimum lokal (local optimum) pada setiap langkah dengan harapan bahwa sisanya mengarah ke solusi optimum global (global optimum).
Algoritma greedy adalah algoritma yang memecahkan masalah langkah per langkah, pada setiap langkahnya adalah :
- Mengambil pilihan yang terbaik yang dapat diperoleh saat itu tanpa
memperhatikan konsekuensi ke depan (prinsip “take what you can get now!”)
- Berharap bahwa dengan memilih optimum lokal pada setiap langkah akan
berakhir dengan optimum global.
Pada setiap langkah diperoleh optimum lokal. Bila algoritma berakhir, kita berharap optimum lokal menjadi optimum global.
Secara umum algoritma greedy disusun oleh elemen-elemen berikut :
- Himpunan kandidat,Berisi elemen-elemen pembentuk solusi.
- Himpunan solusi,Berisi kandidat-kandidat yang terpilih sebagai solusi persoalan.
- Fungsi seleksi (selection function),Memilih kandidat yang paling memungkinkan mencapai solusi optimal. Kandidat yang sudah dipilih pada suatu langkah tidak pernah dipertimbangkan lagi pada langkah
selanjutnya.
- Fungsi kelayakan (feasible)Memeriksa apakah suatu kandidat yang telah dipilih dapat memberikan solusi yang layak, yakni kandidat tersebut bersama-sama dengan himpunan solusi yang sudah terbentuk tidak melanggar
kendala (constraints) yang ada. Kandidat yang layak dimasukkan ke
dalam himpunan solusi, sedangkan kandidat yang tidak layak dibuang dan
tidak pernah dipertimbangkan lagi.
Algoritma Greedy dapat menyelesaikan beberapa masalah dalam kehidupan nyata, dan yang akan kita bahas dalam makalah kali ini adalah :
- TSP (Travelling Sallesperson Problem)
II. PEMBAHASAN
1. TSP (Travelling Sallesperson Problem)
Penggambaran yang sangat sederhana dari istilah Traveling Salesman Problem (TSP) adalah seorang salesman keliling yang harus mengunjungi n kota dengan aturan sebagai berikut :
- Ia harus mengunjungi setiap kota hanya sebanyak satu kali.
- Ia harus meminimalisasi total jarak perjalanannya.
- Pada akhirnya ia harus kembali ke kota asalnya.
Dengan demikian, apa yang telah ia lakukan tersebut akan kita sebut sebagai sebuah tour.
Guna memudahkan permasalahan, pemetaan n kota tersebut akan digambarkan dengan sebuah graph, dimana jumlah vertice dan edge-nya terbatas (sebuah vertice akan mewakili sebuah kota dan sebuah edge akan mewakili jarak antar dua kota yang dihubungkannya). Penanganan problem TSP
ini ekuivalen dengan mencari sirkuit Hamiltonian terpendek.
Terdapat berbagai algoritma yang dapat diterapkan untuk menangani kasus TSP ini, mulai dari exhaustive search hingga dynamic programming. Akan tetapi saat ini yang akan digunakan adalah algoritma Greedy.
Strategi greedy yang digunakan untuk memilih kota berikutnya yang akan dikunjungi adalah sebagai berikut :
”Pada setiap langkah, akan dipilih kota yang belum pernah dikunjungi, dimana kota tersebut memiliki jarak terdekat dari kota sebelumnya”, berdasarkan aturan tersebut dapat dilihat bahwa greedy tidak mempertimbangkan nilai heuristic (dalam hal ini bisa berupa jarak langsung antara dua kota).
2. METODE PENELITIAN
Algoritma greedy dapat digunakan untuk menangani problem TSP ini, dimana algoritma ini akan mencari sirkuit Hamilton minimum.
Berikut adalah algoritmanya yang diimplementasikan dalam bahasa C++:
void TSP ( )
{
int i,x,b[MAX_NODE],top,w,v;
int min_wt,y,f_wt[MAX_NODE],bentuk;
node *ptr1;
f_node *ptr2;
f_list=NULL;
for(i=1;i<=totNodes;i++)
{
status[i]=unseen;
x=1;
status[x]=intree;
top=0;
bentuk=0;
while( (top <= (totNodes-1)) && (!bentuk))
{
ptr1=adj[x];
while(ptr1!=NULL)
{
y=ptr1->vertex;
w=ptr1->weight;
if((status[y]==fringe) && (w<f_wt[y]))
{
b[y]=x;
f_wt[y]=w;
}
else if(status[y]==unseen)
{
status[y]=fringe;
b[y]=x;
f_wt[y]=w;
Insert_Beg(y);
}
ptr1=ptr1->next;
}
if(f_list==NULL)
bentuk=1
else
{
x=f_list->vertex;
min_wt=f_wt[x];
ptr2=f_list->next;
while(ptr2!=NULL)
{
w=ptr2->vertex;
if(f_wt[w] < min_wt)
{
x=w;
min_wt=f_wt[w];
}
ptr2=ptr2->next;
}
del(x);
status[x]=intree;
top++;
}
}
}
for(x=2;x<=totNodes;x++)
cout<<"("<<x<<","<<b[x]<<")\n";
}
Input :
Graf-berbobot terhubung G = (V, E), dimana V =vertex dan E = edge.
Output :
Sirkuit Hamilton minimum T = (V, E’).
3. HASIL PENELITIAN
Terdapat empat buah kota (n = 4) dengan jarak antar kota adalah sebagai berikut :
| | JAKARTA | SURABAYA | BANDUNG | YOGYAKARTA |
| JAKARTA | 0 | 700 | 150 | 400 |
| SURABAYA | 700 | 0 | 600 | 300 |
| BANDUNG | 150 | 600 | 0 | 320 |
| YOGYAKARTA | 400 | 300 | 320 | 0 |
Berdasarkan data jarak di atas, maka graph yang dihasilkan adalah sebagai berikut :
JAKARTA 400 SURABAYA 150 300
600
BANDUNG YOGYAKARTA
4. ANALISIS
Algoritma ini digunakan untuk memilih node selanjutnya pada graf G yang akan dikunjungi,dimana pada setiap langkah akan dipilih node yang belum pernah dikunjungi dan mempunyai jarak terdekat. Pada setiap langkah tersebut, pilih sisi dari graf G yang mempunyai bobot minimum yang membentuk sirkuit hamilton minimum.
5. KESIMPULAN DAN SARAN
Algoritma Greedy adalah suatu algoritma yang menyelesaikan masalah secara step by step sehingga ketika pada satu langkah telah diambil keputusan maka pada langkah selanjutnya keputusan itu tidak dapat diubah lagi. Jadi algoritma ini menggunakan pendekatan untuk mendapatkan solusi lokal yang optimum dengan harapan akan mengarah
pada solusi global yang optimum. Dengan kata lain algoritma greedy tidak dapat menjamin solusi global yang optimum.Penerapan algoritma greedy diantaranya dapat dilihat dalam kasus Travelling Salesperson
Problem (TSP).
