Algoritma Kuhn-Munkres / Hungaria

Algoritma Kuhn-Munkres / Hungaria 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.
Sama seperti Algoritma Held-Karp yang sudah pernah dibahas sebelumnya, algoritma ini dapat menghitung jalur sampai kembali ke titik awal. Lebih tepatnya, fungsi utama algoritma ini hanya dapat menghitung pencarian jalur yang harus kembali ke titik awal. Setelah itu dapat dilakukan sedikit manipulasi untuk menghitung jalur yang tidak perlu kembali ke titik awal.

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

Contoh data awal adalah sebagai berikut:
Jika tidak terdapat jalur diantara kedua titik,
maka beri nilai yang sangat besar pada jalur tersebut
dalam kasus ini digunakan angka 99 sebagai nilai yang sangat besar

daftarJarak=[99 12 99 99 99; ...
            10 99 15 7 99; ...
            99 20 99 5 8; ...
            99 6 14 99 13; ...
            11 9 99 99 99];

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

Langkah-langkah penggunaan algoritma ini adalah

* Lakukan proses perhitungan dengan menggunakan metode Kuhn-Munkres
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini (poin 1 – 7)

[daftarJalur,biaya]=munkres(daftarJarak);

Memasuki perhitungan pada fungsi munkres

1. Kurangi setiap baris daftar jarak dengan nilai terendah pada baris tersebut
Sehingga dalam setiap baris akan selalu ada nilai nol

daftarJarakAwal = bsxfun(@minus, daftarJarakAwal, min(daftarJarakAwal,[],2));

2. Cari setiap angka 0 pada daftar jarak
beri tanda true pada data jarak pada posisi tersebut
Kemudian beri tanda false untuk setiap data pada baris dan kolom tersebut
Ulangi untuk setiap nilai 0 yang ditemukan

zP = ~daftarJarakAwal;
markedZ = false(n);
while any(zP(:))
    [baris,kolom]=find(zP,1);
    markedZ(baris,kolom)=true;
    zP(baris,:)=false;
    zP(:,kolom)=false;
end

3. Beri cover pada masing-masing posisi yang sudah ditandai
Jika semua kolom sudah dicover, berarti perhitungan sudah selesai

primedZ = false(n);
kolomTercover = any(markedZ);
if ~any(~kolomTercover)
	break
end
barisTercover = false(n,1);

4. Cari angka 0 yang tidak tercover dan beri tanda prime
Jika tidak ada angka 0 yang ditandai di baris yang mengandung nilai 0 prime diatas, maka ulangi langkah 3 diatas.
Selain itu maka beri cover untuk baris ini dan hilangkan cover dari kolom yang mengandung angka 0 yang sudah ditandai
Ulangi langkah tersebut sampai tidak ada lagi angka 0 sudah tercover semua
Simpan nilai terendah yang tidak tercover dan lanjutkan ke langkah 6

zP(:) = false;
zP(~barisTercover,~kolomTercover) = ~daftarJarakAwal(~barisTercover,~kolomTercover);
Step = 6;
while any(any(zP(~barisTercover,~kolomTercover)))
	[BarisZNoncover,KolomZNoncover] = find(zP,1);
	primedZ(BarisZNoncover,KolomZNoncover) = true;
	markZ = markedZ(BarisZNoncover,:);
	if ~any(markZ)
		Step = 5;
		break;
	end
	barisTercover(BarisZNoncover) = true;
	kolomTercover(markZ) = false;
	zP(BarisZNoncover,:) = false;
	zP(~barisTercover,markZ) = ~daftarJarakAwal(~barisTercover,markZ);
end

5. Tentukan baris Z1, yaitu angka 0 yang sudah ditandai pada kolom dimana angka 0 prime yang tidak tercover telah ditemukan
Ulangi perhitungan berikutnya sampai pada posisi kolom nilai 0 prime tidak memiliki nilai 0 yang sudah ditandai
Hilangkan tanda pada [posisi barisZ1, kolom 0 yang tidak tercover]
Beri tanda pada setiap angka 0 prime
Kemudian hapus semua nilai dengan tanda prime dan hilangkan cover pada semua data pada matriks
Lanjutkan kembali ke langkah 3

barisZ1 = markedZ(:,KolomZNoncover);
markedZ(BarisZNoncover,KolomZNoncover)=true;
while any(barisZ1)
	markedZ(barisZ1,KolomZNoncover)=false;
	KolomZNoncover = primedZ(barisZ1,:);
	BarisZNoncover = barisZ1;
	barisZ1 = markedZ(:,KolomZNoncover);
	markedZ(BarisZNoncover,KolomZNoncover)=true;
end

6. Tambahkan nilai terendah yang tidak tercover tersebut kepada semua data pada baris yang sudah tercover,
dan kurangi semua data pada kolom yang tidak tercover dengan nilai tersebut
Setelah itu lanjutkan kembali ke langkah 4 dengan data marked, primed, dan cover yang baru

M=daftarJarakAwal(~barisTercover,~kolomTercover);
nilaiMinimal=min(min(M));
if nilaiMinimal==inf
	return
end
daftarJarakAwal(barisTercover,kolomTercover)=daftarJarakAwal(barisTercover,kolomTercover)+nilaiMinimal;
daftarJarakAwal(~barisTercover,~kolomTercover)=M-nilaiMinimal;

7. Catat jalur yang terbentuk
Kemudian hitung biaya yang dihasilkan jalur tersebut

daftarJalur(daftarBarisValid,daftarKolomValid) = markedZ(1:jumlahBaris,1:jumlahKolom);
biaya = sum(daftarJarak(daftarJalur));

Hasil akhir adalah:

Algoritma Kuhn-Munkres / Hungaria
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     , 10
Titik A   , Titik E     , 11
Titik B   , Titik A     , 12
Titik B   , Titik C     , 20
Titik B   , Titik D     , 6
Titik B   , Titik E     , 9
Titik C   , Titik B     , 15
Titik C   , Titik D     , 14
Titik D   , Titik B     , 7
Titik D   , Titik C     , 5
Titik E   , Titik C     , 8
Titik E   , Titik D     , 13


Hasil akhir:
Jalur 1 adalah dari titik A ke titik E dengan biaya 11
Jalur 2 adalah dari titik B ke titik A dengan biaya 12
Jalur 3 adalah dari titik C ke titik D dengan biaya 14
Jalur 4 adalah dari titik D ke titik B dengan biaya 7
Jalur 5 adalah dari titik E ke titik C dengan biaya 8


Total biaya = 52

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

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.