Oke geng... kali ini kita akan membahas tentang
combinatorial problem..
Sebelum kita masuk pada intinya kita harus tahu dulu
apa itu combinatorial..??
Jadi geng.., dalam ilmu matematika kombinatorial
adalah salah satu cabang dari matematika yang bertujuan untuk menghitung jumlah
penyusunan objek tanpa mengenumerasi semua kemungkinan susunannya.
Oke geng.., sekarang dapat kita simpulkan bahwa combinatorial problem
adalah suatu permasalahan matematis dalam menyusun , mengelompokan, mensorting,
atau memilih sejumlah objek diskrit tertentu. Dan sampai saat ini combinatorial
promblem masih menjadi salah satu yang paling sulit dalam komputasi, baik itu
dari teori maupun prakteknya.
Jadi geng, Dalam
Combinatorial promble ini tudak diketahui dengan pasti algoritma mana yang
dapat menyelesaikan masalahnya..
Tapi geng.., walau pun
algoritma nya sangat susah bukan berarti tidak bisa diselesaikan..
Dia bisa diselesaikan
dengan algoritma yang efisien, tapi itu harus mengikuti aturan-aturannya.
Berikut adalah beberapa
contoh kasus dari combinatorial problem :
1. Travelling Salesman
Problem (TSP)
TSP atau Travelling
Salesman Problem merupakan masalah kombinasi optimasi dalam menemukan tour yang
paling terpendek. TSP adalah problem untuk menentukan urutan dari sejumlah kota
yang harus dilalui oleh salesman, setiap kota hanya boleh dilalui satu kali
dalam perjalanannya, dengan jarak anatara setiap kota satu dengan setiap kota
lainnya sudah diketahui. Salesman tersebut harus meminimalkan biaya dan jarak
yang harus ditempuh dalam perjalanan tersebut.
3. Knapsack Problem
Knapsack Problem merupakan masalah dimana
orang dihadapkan pada persoalan optimasi pada pemilihan benda yang dapat
dimasukan kedalam sebuah wadah yang memiliki keterbatasan ruang atau daya
tampung. Dengan adanya optimasi dalam pemilihan benda yang akan dimasukkkan ke
dalam wadah tersebut diharapkan dapat menghasilkan keuntungan yang maksimal.
Contoh dari Knapsack Problem adalah Jasa pengangkutan barang dalam kontainer
dengan media kapal. Knapsack Problem bisa ditasi dengan algoritma Brute Force,
Algoritma Greedy dan Algoritma Genetika.
Jenis-Jenis Knapsack
Problem
a. 0/1
Knapsack Problem
Setiap barang hanya tersedia 1 unit, take it
or leave it.
b. Fractional
Knapsack Problem
Barang boleh dibawa sebagian saja (dalam
unit pecahan). Versi problem ini menjad masuk akal apabila barang-barang dibagi
misalnya gula, tepung, dan sebaginya.
c. Bounded
Knapsak Problem
Setiap barang tersedia sebanyak N unit
(jumlahnya terbatas).
d. Unbounded
Knapsak Problem
Setiap barang tersedia lebih dari 1 unit, jumlah nya
tidak terbatas.
2. Vehicle Routing (VRP)
VRP atau Vehicle Routing
merupakan permasalahan optimasi penentuan rute dengan keterbatasan kapasitas
kendaraan. Contoh dari permasalahan ini adalah ketika terdapat salesman yang
berangkat dari suatu kota kemudian melakukan kunjungan ke sejumlah kota. Setiap
kotanya hanya dapat dikunjungi oleh satu
salesman saja. Tujuan utamanya adalah meminimalkan total jarak atau total biaya
perjalanan. VRP merupakan permasalahan klasik yang sangat dekat dengan
kehidupan manusia. Contoh permasalahan yang dapat diselesaian dengan pendekatan
VRP antara lain penentuan rute pengiriman surat, paket, laundry dan koran.
Algoritma yang dapat menyelesaikan masalah Combinatorial Problem diantaranya
adalah Genetic Algoritm, Tabu Search, Simulated Annealing, Nearest Neighbor dan
CODEQ.
//////////////////////////////////////////////////////////////////////////////////
berikut adalah contoh source code travelling salesmen problem :
#include<stdio.h>
#include<conio.h>
int
main ()
{
Int
cost[20],min,l,m,sr[20],sc[20],flag[20],i,j,k,rf[20],cf[20],n;
Int
nrz[20],ncz[20,cn,a,noz,nrz1[20],ncz[20],count er=0;
Printf(“\n\masukan jumlah tugas : “);
Scanf (“%d”, &n);
//Masukan Cost Matriks
Printf (“\nMasukan cost matriks\n”);
For (i=0; i<n; i++)
{
Printf(“\n”);
For (j=0; j<n; j++)
{
Printf(“const[%d][%d] = “,i,j);
Scanf (“%d”, &cost[i][j]);
}
}
Printf (“\n\n”);
//Menampilkan cost matriz yang
dimasukan
Printf (“cost matriks : \n”);
For (i=0; i<n; i++)
{
For (j=0; j<n; j++)
Printf(“\t%d\t”, costi[i][j]);
Printf(“\n”);
}
//operasi kolom
For (i=0; i<n; i++)
{
Min=cost[i][j];
//Menemukan elemen minimum disetiap
baris
For (j=;j<n;j++)
{
If (min>cost[i][j])
Min=cost[i][j];
}
//kurangi unsur dari minimum dari
setiap elemen baris
For (j=0;j<n;j++)
Const[i][j]-min;
}
//operasi dalam kolom
For (i=0;i<n;i++)
{
Min=cost[0][i];
//menemukan elemen disetiap kolom
For(j=0;j<n;j++)
{
If (min>cost[j][i])
Min=cost[j][i];
}
//kurangi unsur minimum dari setiap
elemen kolom
For (j=0;j<n; j++)
Costj[j][i]=cost[j][i]-min;
}
Printf(“\n\n”);
Printf{“Cost matriks setelah operasi baris
dan kolom : \n”);
For (i=0; i<n; i++)
{
For (j=0; j<n; j++)
Printf(“\t%d\t”, cost[i][j]);
Print (“\n”);
}
Repatx:;
//Menarik jumlah minimum garis
horizontal dan vertical
A=0; noz=0, min=1000;
For (i=0; i<n; i++)
{
For (j=0; j<n; j++)
Flag[i][j]=0;
}
For (i=0;i<n; i++)
{
Cn=0;
For (j=0; j<n; j++)
{
If (cost[i][j]==0)
{
Cn++;
Flag[i][j]=1;
}
}
Nrz[i]=cn;
Noz=noz+cn;
}
For
(i=0;i<n; i++)
{
Cn=0;
For (j=0; j<n; j++)
{
If(cost[j][i]==0)
{
Cn++;
Flag[j][i]=1;
}
}
Ncz[i]=cn;
Noz=noz+cn;
}
For
(i=0; i<n; i++)
{
Nrz1[i]=nrz[i];
Ncz1[i]=ncz[i];
}
K=0;
While
(nrz[k] !=0 || ncz[k] !=0)
{
For (i=0; i<n; i++)
{
Cn=0;
For(j=0; j<n; j++)
{
If (flag[i][j]==1)
Cn++;
Nrz[i]=cn;
}
If (nrz[i]==1)
{
For (j=0; j<n; j++)
{
If (flag[i][j]==1)
{
Flag[i][j]=2;
For(k=0;
k<n; k++)
{
If(flag[k][j]==1)
Flag[k][j]=0;
}
}
}
}
For (i=0; i<n; i++)
{
Cn=0;
For(j=0; j<n; j++)
{
If(flag[j][i]==1)
Cn++;
Ncz[i]=cn;
}
If(ncz[i]==1)
{
For (j=0; j<n; j++)
{
If(flag[j][i]==1)
{
Flag[j][k]=0;
}
}
}
}
}
K++;
}
For (i=0; i<n; I++)
{
For(j=0l j<n; j++)
{
If (flag[i][j]==2)
A++
}
}
//Jika jumlah minuman baris, adl sama dengan
urutan dari matriks n maka dapat diselesaikan secara optimal//
If(a==n)
{
Printf(“\nTugas\n”);
//Menampilkan urutan tugas//
For (i=0; i<n; i++)
{
For(j=0; j<n; j++)
{
If(flag[i][j]==2)
Printf(“%d->%d”,i+1,j+1);
}
Printf(“\n”);
}
Getch();
Exit(0);
}
//Menentukan unsur terkecil yang tidak
mencakup oleh garis kemudian mengurangi elemen minimum ini dari semua elemen
ditemukan & menambahkan elemen yang sama dipersimpangan garis horizontal
ataupun vertical//
Else
{
For(i=0; i<n; i++)
{
Rf[i]=0, sr[i]=0;
Cf[i]=0, sc[i]=0;
}
For (k=n; (k>0&&noz!=0); k--)
{
For(i=0; i<n; i++)
{
M=0;
For(j=0;j<n; j++)
{
If((flag[i][j]==4&&(cost[i][j]==0))
M++;
}
Sr[i]=m;
}
For(i=0; i<n; i++)
{
If
(nrz1[i]==k&&nrz1[i]!=sr[i])
{
Rf[i]=1;
For(j==0; j<n; j++)
{
If(cost[i][j]==0)
Flag[i][j]=4;
}
Noz=noz-k;
}
}
For (i=0; i<n; i++)
{
1=0;
For(j=0; j<n; j++)
{
If((flag[j][i]==4)&&(cost[j][i]==0))
l++;
}
Sc[i]=l;
}
For(i=0; i<n; i++)
{
If(ncz1[i]==k&&ncz1[i]!=sc[i])
{
Cf[i]=1;
For(j=0; j<n; j++)
{
If(cost[j][i]==0)
Flag[j][i]=4;
}
Noz=noz-k;
}
}
For(i=0; i<n; i++)
{
For(j=0; j<n; j++)
{
If(flag{i][j]!=3)
{
If(rf[i]==1 &&
cf[j]==1)
{
Flag[i][j]=3;
If(cost[i][j]==0)
Noz=noz+1;
}
}
}
}
}
For(i=0;
i<n; i++)
{
For(j=0; j<n; j++)
{
If(rf[i]!=1&&cf[j]!=1)
{
If(min>cost[i][j])
Min=cost[i][j];
}
}
}
For(i=0;
i<n; i++)
{
For(j=0; j<n; j++)
{
If(rf[i]!=1&&cf[j]!=1)
Cost[i][j]=cost[i][j]-min;
}
}
For(i=0;
i<n; i++)
{
For(j=0; j<n; j++)
{
If(flag[i][j]==3)
Cost[i][j]=cost[i][j]+min;
}
}
}
Printf(“\n\n”);
If(counter
< 10)
{
Counter = counter+1;
Printf(“\n\matriks
tengah : \n”);
For
(i=0; i<n; i++)
{
For(j=0; j<n j++)
Printf(“\t%d\t”, cost[i][j]);
Printf(“\n”);
}
}
Else
{
Printf(“\n\nSolusi optimal”);
Getch();
Return 0;
}
Goto repatx;
}
////////////////////////////////////////
Oke geng.., mungkin
segitu aja sedikit penjelasan tentang combinatorial problem dari gua, kalau ada
salah atau kurang gua minta maaf, silah kan commen dibawah untuk pendapat
kalian....
keren..
BalasHapusmembantu bro, thanks..
BalasHapus