Algoritma Edmonds


Algoritma Edmonds adalah salah satu algoritma yang digunakan untuk pencarian jalur. Contoh yang dibahas kali ini adalah mengenai pencarian jalur yang melalui semua titik dengan biaya terendah.
Algoritma ini dapat digunakan untuk menghitung jalur searah, yaitu biaya antara titik A dan titik B berbeda dengan biaya antara titik B dan titik A. Tetapi dalam contoh kasus dibawah ini akan digunakan jalur yang tidak memiliki arah, sehingga biaya dari titik A dan titik B akan dianggap sama dengan biaya dari titik B dan titik A.



Diasumsikan ada 5 titik yang harus dilalui semuanya, yaitu A,B,C,D,E
semua titik tidak terhubung secara langsung dengan titik-titik lainnya, melainkan hanya melalui jalur tertentu saja
setiap jalur juga memiliki biaya sendiri-sendiri
maka tentukan jalur yang harus diambil untuk mengelilingi semua titik dengan biaya terendah
Diasumsikan data jalur yang tersedia adalah sebagai berikut

Titik awalTitik TujuanJarak
Titik ATitik B6
Titik ATitik E7
Titik BTitik C5
Titik BTitik D4
Titik BTitik E8
Titik CTitik D7
Titik CTitik E3
Titik DTitik E9

Jika diilustrasikan dalam gambar, maka model data awal adalah sebagai berikut
kruskal awal



Sebelum masuk kedalam langkah-langkah pembahasan algoritma, ada beberapa konstanta atau parameter yang harus diketahui, yaitu:
* Tentukan jumlah titik yang harus dihubungkan
Diasumsikan dalam kasus ini, jumlah titik ada 5 buah

jumlahTitik = 5;

Langkah-langkah penggunaan algoritma ini adalah

1. Lakukan inisialisasi daftar titik sebanyak jumlah titik

daftarTitik=[1:jumlahTitik]';

2. Lakukan inisialisasi daftar biaya sesuai dengan data yang tersedia

daftarBiaya(1,:) = [1 2 6];
daftarBiaya(2,:) = [1 5 7];
daftarBiaya(3,:) = [2 3 5];
daftarBiaya(4,:) = [2 4 4];
daftarBiaya(5,:) = [2 5 8];
daftarBiaya(6,:) = [3 4 7];
daftarBiaya(7,:) = [3 5 3];
daftarBiaya(8,:) = [4 5 9];

3. Lakukan perhitungan sampai semua titik pada perhitungan sebelumnya sudah dilewati (poin 3a – 3c)

while(size(tmpTitik, 2) ~= jumlahTitik)
. . .

3a. Lakukan pengacakan pada urutan titik yang akan dihitung terlebih dahulu

daftarTitik = randperm(jumlahTitik);

3b. Lakukan proses perhitungan dengan menggunakan metode Edmonds
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini

e = edmonds(daftarTitik,daftarBiaya);

Memasuki perhitungan pada fungsi edmonds

* Lakukan perulangan sampai pada kondisi dimana semua titik sudah dilewati (poin 3b1 – 3b6)
Kondisi ini nanti akan dijelaskan pada saat perulangan

while(1)
. . .

3b1. Catat daftar titik dan daftar biaya yang digunakan pada perhitungan sebelumnya

daftarTitik=e(iMapping).daftarTitik;
daftarBiaya=e(iMapping).daftarBiaya;

3b2. Lakukan pencarian titik yang belum dilewati

[titikBelumDilewati, idxTitikBelumDilewati] = setdiff(daftarTitik,e(iMapping).titikTerbaik);
[~,idx] = sort(idxTitikBelumDilewati);
titikBelumDilewati = titikBelumDilewati(idx);

3b3. Jika semua titik sudah dilewati maka hentikan perhitungan

if (numel(titikBelumDilewati)==0)
	break;
end

3b4. Tambahkan titik pertama yang belum dilewati pada titik terbaik

titikTerpilih=titikBelumDilewati(1);
e(iMapping).titikTerbaik=[e(iMapping).titikTerbaik,titikTerpilih];

3b5. Tentukan titik tujuan yang memiliki biaya terendah dari titik terpilih
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini

[biayaTerendah,titikTujuan] = BiayaTerendahDariTitikTerpilih(daftarBiaya,titikTerpilih);

* Gunakan fungsi ini untuk mencari titik tujuan dengan biaya terendah dari titik awal

function[biayaTerendah,titikTujuan]=BiayaTerendahDariTitikTerpilih(daftarBiaya,titikTerpilih)
if numel(daftarBiaya)==0
    biayaTerendah=-1;
    titikTujuan=NaN;
    return;
end

CalonTitikTujuan = find(daftarBiaya(:,2) == titikTerpilih);
BiayaTitikTujuan = (daftarBiaya(CalonTitikTujuan,3));
[biayaTerendah,idxBiayaTerendah] = min(BiayaTitikTujuan);
titikTujuan=CalonTitikTujuan(idxBiayaTerendah);

3b6. Lakukan perhitungan berikut apabila terdapat jalur dengan biaya terendah (poin 3b6a – 3b6g)

if biayaTerendah > 0
. . .

3b6a. Lakukan pengecekan apakah jalur sementara yang terbentuk sudah membentuk loop
Contoh jalur yang membentuk loop adalah A – B – C – A atau A – B – C – B

[totalBiayaDalamLoop,daftarTitikDalamLoop]=isLoop([daftarBiaya(e(iMapping).jalurTerbaik,:)],daftarBiaya(titikTujuan,1),daftarBiaya(titikTujuan,2));

* Gunakan fungsi ini untuk mengecek apakah jalur sementara yang terbentuk sudah membentuk loop

function[totalBiayaDalamLoop,daftarTitikDalamLoop] = isLoop(jalurTerbaikSementara,titikAwal,titikTujuan)
if size(jalurTerbaikSementara,1)>0
    maksTitik = max([titikAwal,titikTujuan,max( unique(jalurTerbaikSementara(:,1:2)) )]);
    jalurTerbaikSementara = [jalurTerbaikSementara; maksTitik,maksTitik,0];
    DG = sparse(jalurTerbaikSementara(:,1),jalurTerbaikSementara(:,2),jalurTerbaikSementara(:,3));

    %Jika tidak ditemukan loop dari titik awal ke titik tujuan
    %Lakukan pengecekan loop dari titik tujuan ke titik awal
    [totalBiayaDalamLoop,daftarTitikDalamLoop] = graphshortestpath(DG,titikAwal,titikTujuan);    
    if totalBiayaDalamLoop==Inf
        [totalBiayaDalamLoop,daftarTitikDalamLoop] = graphshortestpath(DG,titikTujuan,titikAwal);
    end 
else
    totalBiayaDalamLoop=Inf;
    daftarTitikDalamLoop=[];
end

3b6b. Catat daftar titik dalam loop yang ditemukan

e(iMapping).daftarTitikDalamLoop=daftarTitikDalamLoop;

3b6c. Tambahkan titik tujuan ke dalam jalur terbaik

e(iMapping).jalurTerbaik = [e(iMapping).jalurTerbaik, titikTujuan];

3b6d. Lakukan perhitungan berikutnya apabila terdapat jalur yang membentuk loop

if totalBiayaDalamLoop < Inf
. . .

3b6e. Lakukan pemberian label ulang pada daftar titik
Titik dengan jalur yang membentuk loop akan dibuang untuk membentuk daftar titik yang baru

[eBaru,MapDaftarTitik,MapDaftarBiaya]=LabelUlang(e(iMapping));

3b6f. Lakukan pencatatan mapping daftar titik dan daftar biaya yang baru pada mapping sebelumnya

e(iMapping).MapDaftarTitik = MapDaftarTitik;
e(iMapping).MapDaftarBiaya = MapDaftarBiaya;

3b6g. Lakukan pencatatan titik terbaik, jalur terbaik, daftar titik dan daftar biaya pada mapping yang baru
Selanjutnya mapping ini akan digunakan untuk perhitungan sampai dibentuk mapping lain

iMapping = iMapping+1;
e(iMapping).titikTerbaik=eBaru.titikTerbaik;
e(iMapping).jalurTerbaik=eBaru.jalurTerbaik;
e(iMapping).daftarTitik=eBaru.daftarTitik;
e(iMapping).daftarBiaya=eBaru.daftarBiaya;

3c. Hitung jumlah titik yang dilewati pada perhitungan ini untuk dibandingkan dengan jumlah titik semula

tmpTitik = e.titikTerbaik;

Hasil akhir adalah:

Algoritma Edmonds
Contoh: Pencarian jalur yang melalui semua titik dengan biaya terendah
Diasumsikan ada 5 titik yang harus dilalui semuanya, yaitu A,B,C,D,E
semua titik tidak terhubung secara langsung dengan titik-titik lainnya, melainkan hanya melalui jalur tertentu saja
setiap jalur juga memiliki biaya sendiri-sendiri
maka tentukan jalur yang harus diambil untuk mengelilingi semua titik dengan biaya terendah
Diasumsikan data jalur yang tersedia adalah sebagai berikut
Titik awal, Titik Tujuan, Biaya
Titik A   , Titik B     , 6
Titik A   , Titik E     , 7
Titik B   , Titik C     , 5
Titik B   , Titik D     , 4
Titik B   , Titik E     , 8
Titik C   , Titik D     , 7
Titik C   , Titik E     , 3
Titik D   , Titik E     , 9


Jumlah Titik = 5


Hasil akhir:
Jalur 1 adalah dari titik A ke titik B dengan biaya 6
Jalur 2 adalah dari titik B ke titik C dengan biaya 5
Jalur 3 adalah dari titik C ke titik E dengan biaya 3
Jalur 4 adalah dari titik B ke titik D dengan biaya 4


Total biaya = 18

Jika diilustrasikan dalam gambar, maka model hasil akhirnya adalah sebagai berikut
kruskal akhir

Contoh modul / source code menggunakan Matlab dapat didownload disini:



Jika membutuhkan jasa kami dalam pembuatan program, keterangan selanjutnya dapat dilihat di Fasilitas dan Harga
Jika ada yang kurang paham dengan langkah-langkah algoritma diatas, silahkan berikan komentar Anda.
Selamat mencoba.

Tinggalkan sebuah komentar

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *