Algoritma Held-Karp

Algoritma Held-Karp 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.
Berbeda dengan algoritma pencarian jalur yang lain, seperti Algoritma Dijkstra dan Algoritma A* (A-Star) yang sudah pernah dibahas sebelumnya, algoritma ini dapat menghitung jalur sampai kembali ke titik awal. Bisa jadi jalur yang hanya melalui semua titik berbeda dengan jalur yang sampai kembali ke titik awal. Dan pada pembahasan contoh kali ini akan ditunjukkan bahwa kedua perhitungan tersebut memiliki perbedaan jalur.

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

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

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

Const jumlahTitik As Integer = 5

Langkah-langkah penggunaan algoritma ini adalah

1. Lakukan inisialisasi daftar titik sebanyak jumlah titik, dan masukkan masing-masing titik ke dalam daftar

daftarTitik = New Integer(jumlahTitik - 1) {0, 1, 2, 3, 4}

2. Lakukan inisialisasi daftar jalur sesuai dengan data yang tersedia

daftarJalur = New Double(jumlahTitik - 1, jumlahTitik - 1) { _
	{0, 10, 0, 0, 11}, _
	{12, 0, 20, 6, 9}, _
	{0, 15, 0, 14, 0}, _
	{0, 7, 5, 0, 0}, _
	{0, 0, 8, 13, 0} _
}

3 Tentukan titik awal pencarian jalur

Console.WriteLine("Tentukan titik awal pencarian jalur antara 1 sampai dengan " & jumlahTitik & ": ")
Dim idxTitikAwal As Integer = Integer.Parse(Console.ReadLine) - 1

4 Tentukan apakah perhitungan yang dilakukan hanya sampai pada semua titik sudah dilalui, atau sampai kembali ke titik awal
Jika inputan bernilai ya, maka jalur yang dicari harus sampai kembali ke titik awal
Jika inputan bernilai tidak, maka jalur yang dicari hanya sampai pada semua titik sudah dilalui saja

Console.WriteLine("Apakah perhitungan jalur sampai kembali ke titik awal (ya / tidak)?")
Dim st As String = (Console.ReadLine).ToString.ToLower

Dim isKembaliKeTItikAwal As Boolean
If st = "ya" Then
	isKembaliKeTItikAwal = True
Else
	isKembaliKeTItikAwal = False
End If

5. Lakukan perhitungan pencarian jalur dengan biaya terendah
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini (poin 5a – 5c)

Dim jalur As IEnumerable(Of Integer) = HeldKarp(idxTitikAwal, isKembaliKeTItikAwal, biaya)

Memasuki perhitungan pada fungsi HeldKarp

5a. Lakukan Inisialisasi daftar titik selain titik awal,
kemudian masukkan semua titik selain titik awal ke dalam daftar tersebut

Dim daftarTitikSelainTitikAwal = New HashSet(Of Integer)(daftarTitik)
daftarTitikSelainTitikAwal.Remove(titikAwal)

5b. Lakukan perhitungan pencarian biaya terendah pada semua titik
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini (poin 5b1 – 5b4)

Dim akar = New Titik()
biaya = HitungBiayaTerendah(titikAwal, daftarTitikSelainTitikAwal, akar, idxTitikAwal, isKembaliKeTItikAwal)

5b1. Lakukan perhitungan pada semua titik tujuan

For Each titikTujuan In daftarTitikSelainTitikAwal
. . .

5b2. Tambahkan cabang semua titik tujuan pada titik awal

akar.AnakCabang(i) = New Titik()
akar.AnakCabang(i).Biaya = titikTujuan

5b3. Tentukan biaya jalur awal dari titik awal ke titik tujuan

Dim biayaJalurIni As Double = daftarJalur(titikAwal, titikTujuan)

5b4. Apabila biaya jalur lebih dari 0, maka lakukan perhitungan berikut (poin 5b4a – 5b4b)

5b4a. buat daftar titik baru untuk semua titik selain titik awal dan titik tujuan

Dim daftarTitikSelainTitikTujuan = New HashSet(Of Integer)(daftarTitikSelainTitikAwal)
daftarTitikSelainTitikTujuan.Remove(titikTujuan)

* Jika membutuhkan perhitungan jalur sampai kembali ke titik awal, maka jalankan skrip ini
Ulangi fungsi ini untuk menghitung biaya terendah pada setiap titik pada daftar titik baru

biayaTitikSelainTitikTujuan = HitungBiayaTerendah(titikTujuan, daftarTitikSelainTitikTujuan, akar.AnakCabang(i), idxTitikAwal, isKembaliKeTItikAwal)

* Jika hanya membutuhkan perhitungan jalur sampai semua titik sudah dilalui, maka jalankan skrip ini
Jika daftar titik baru hanya berjumlah 1 maka
jadikan titik baru tersebut sebagai anak cabang dari titik tujuan
hitung biaya pada jalur terakhir
Selain itu, Ulangi fungsi ini untuk menghitung biaya terendah pada setiap titik pada daftar titik baru

If daftarTitikSelainTitikTujuan.Count = 1 Then
	akar.AnakCabang(i).AnakCabang = New Titik(0) {}
	akar.AnakCabang(i).AnakCabang(0) = New Titik()
	akar.AnakCabang(i).AnakCabang(0).Biaya = daftarTitik(daftarTitikSelainTitikTujuan(0))
	akar.AnakCabang(i).AnakCabang(0).isTerpilih = True

	biayaTitikSelainTitikTujuan = daftarJalur(titikTujuan, daftarTitikSelainTitikTujuan(0))
Else
	biayaTitikSelainTitikTujuan = HitungBiayaTerendah(titikTujuan, daftarTitikSelainTitikTujuan, akar.AnakCabang(i), idxTitikAwal, isKembaliKeTItikAwal)
End If

5b4b. Apabila biaya jalur pada titik tujuan ke titik baru lebih dari 0, maka jumlahkan biaya tersebut pada biaya awal
Jika total biaya kurang dari total terbaik maka ambil jalurnya sebagai jalur terbaik

If biayaTitikSelainTitikTujuan > 0 Then
	Dim biayaSekarang As Double = biayaJalurIni + biayaTitikSelainTitikTujuan

	If totalBiaya > biayaSekarang Then
		totalBiaya = biayaSekarang
		idxTitikTerpilih = i
	End If
End If

5c. Cari jalur titik-titik dengan biaya terendah yang sudah ditemukan sebelumnya
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini

Dim arrayTitik = New Queue(Of Integer)()
arrayTitik.Enqueue(titikAwal)
CariJalur(akar, arrayTitik)

6. Catat hasil akhir untuk masing-masing jawaban garis yang ditemukan
Kemudian tampilkan total biaya jalur tersebut

Dim s As String = ""
For i As Integer = 0 To jalur.ToArray().Length - 1
	s &= (IIf(s <> "", " - ", "") & "Titik " & Chr(jalur(i) + 65))
Next
Console.WriteLine(s)
Console.WriteLine("Total biaya = " & biaya)

* Agar dapat menjalankan skrip diatas, maka diperlukan sebuah Class Titik untuk menampung data biaya dan anak cabang dari sebuah titik. Deklarasi Class Titik adalah sebagai berikut:

Public Class Titik
    Private m_Biaya As Integer
    Private m_AnakCabang As Titik()
    Private m_isTerpilih As Boolean

    Public Property Biaya() As Integer
        Get
            Return m_Biaya
        End Get
        Set(value As Integer)
            m_Biaya = value
        End Set
    End Property

    Public Property AnakCabang() As Titik()
        Get
            Return m_AnakCabang
        End Get
        Set(value As Titik())
            m_AnakCabang = value
        End Set
    End Property

    Public Property isTerpilih() As Boolean
        Get
            Return m_isTerpilih
        End Get
        Set(value As Boolean)
            m_isTerpilih = value
        End Set
    End Property
End Class

Hasil akhir adalah: (klik untuk perbesar gambar)

Berikut adalah perhitungan jalur yang sampai kembali pada titik awal

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

Berikut adalah perhitungan jalur yang hanya sampai pada titik akhir saja

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

dapat disimpulkan bahwa kedua perhitungan tersebut memang memiliki perbedaan jalur yang dilewati.

Contoh modul / source code dalam bahasa VB (Visual Basic) 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.