Algoritma BiDi Search (BiDirectional Search) / Pencarian Dwiarah 2

Algoritma BiDi Search (BiDirectional Search) adalah salah satu algoritma yang digunakan untuk pencarian jalur. Contoh yang dibahas kali ini adalah mengenai pencarian jalur yang melalui semua titik.
Secara singkat, Algoritma ini adalah penggabungan dari 3 buah algoritma yang sudah dijelaskan sebelumnya, yaitu Algoritma BFS (Breadth First Search), Algoritma DFS (Depth First Search), dan Algoritma DLS (Depth Limited Search). Pencarian solusi dilakukan dari titik awal dan titik tujuan secara bersamaan, sampai akhirnya bertemu di sebuah titik tengah. Setelah menemukan titik tengah dan hasil jalur dari masing-masing perhitungan sudah tepat, maka jawaban sudah ditemukan.

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 yang ada
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

* Tentukan limit atau batas maksimal kedalaman pencarian
Karena ada 5 titik yang akan dicari solusinya, maka limit harus bernilai minimal 5 buah agar solusi dapat ditemukan
Jika tidak, maka solusi tidak dapat ditemukan karena pencarian titik tidak akan sampai pada pencarian 5 titik.

Const limit 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

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

2. Lakukan inisialisasi daftar jalur sesuai dengan data yang tersedia
Terdapat matriks berukuran [jumlah titik x jumlah titik] untuk menyimpan jalur dari masing-masing titik
Jika tidak ada jalur diantara 2 titik, maka nilai jalurnya adalah 0

Dim daftarBiaya(,) As Double = 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 titik tujuan pencarian jalur

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

5. Lakukan perhitungan pencarian jalur melalui semua titik yang ada
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini (poin 5a – 5e)

Dim jalur As ArrayList = BiDi(daftarTitik, daftarBiaya, idxTitikAwal, idxTitikTujuan, (limit + 1) / 2)

Memasuki perhitungan pada fungsi BiDi

5a. Masukkan titik awal sebagai titik pertama yang akan dicari jalurnya

Dim daftarIndukAwal As New ArrayList()
daftarIndukAwal.Add(idxTitikAwal)

Dim daftarIndukTujuan As New ArrayList()
daftarIndukTujuan.Add(idxTitikTujuan)

5b. Kemudian masukkan titik-titik lain secara terurut dari titik pertama ke titik terakhir

For i As Integer = 0 To daftartitik.Length - 1
	If i <> idxTitikAwal Then daftarIndukAwal.Add(i)
Next

For i As Integer = daftartitik.Length - 1 To 0 Step -1
	If i <> idxTitikTujuan Then daftarIndukTujuan.Add(i)
Next

5c. Inisialisasi variabel depth / kedalaman untuk mengetahui kedalaman pada saat pencarian jalur

Dim depthAwal(daftartitik.Count - 1) As Integer
Dim depthTujuan(daftartitik.Count - 1) As Integer
Dim depthNormal(daftartitik.Count - 1) As Integer
For i As Integer = 0 To depthNormal.Length - 1
	depthAwal(i) = daftartitik.Count - i
	depthTujuan(i) = daftartitik.Count - i
	depthNormal(i) = daftartitik.Count - 1 - i
Next

5d. Masukkan titik pertama ke dalam jalur yang akan dihitung
Dan hilangkan titik tersebut dari daftar titik yang sudah dihitung

Dim jalurAwal As New ArrayList()
jalurAwal.Add(daftarIndukAwal(0))
daftarIndukAwal.RemoveAt(0)
depthAwal(jalurAwal.Count - 1) -= 1

Dim jalurTujuan As New ArrayList()
jalurTujuan.Add(daftarIndukTujuan(0))
daftarIndukTujuan.RemoveAt(0)
depthTujuan(jalurTujuan.Count - 1) -= 1

* Lakukan perhitungan selama masih ada titik yang belum dihitung (poin 5e – 5f)

5e. Lakukan perhitungan pada titik awal berurutan dari titik pertama ke titik terakhir
Metode yang digunakan adalah BFS (Breadth First Search)

5e1. Masukkan titik berikutnya ke dalam jalur yang sedang dihitung
Dan hilangkan titik tersebut dari daftar titik yang sudah dihitung

jalurAwal.Add(titikBerikutnya)
daftarIndukAwal.RemoveAt(0)

5e2. Hitung kedalaman pada titik yang sedang dihitung
Apabila nilai kedalaman adalah 0, maka beri nilai awal kedalaman
Selain itu kurangkan nilai kedalamannya dengan 1

If depthAwal(jalurAwal.Count - 1) <= 0 Then
	depthAwal(jalurAwal.Count - 1) = depthNormal(jalurAwal.Count - 1)
Else
	depthAwal(jalurAwal.Count - 1) -= 1
End If

5e3. Jika terdapat jalur antara titik sebelumnya dan titik berikutnya,
dan semua titik sudah dihitung semua atau jumlah titik yang sedang dihitung belum melebihi limit / batas maksimal kedalaman,
Lakukan pengecekan apakah semua titik sudah dihitung semua
Jika kondisi tersebut benar, maka hentikan perhitungan

If daftarBiaya(titikSebelumnya, titikBerikutnya) <> 0 _
	AndAlso (jalurAwal.Count = daftartitik.Count Or jalurAwal.Count < limit) Then

	If jalurAwal.Count = daftartitik.Count Then
		Console.WriteLine("Titik Awal   -> Jalur sudah ditemukan")
		Console.Write("Titik Awal   -> Jalur yang terbentuk = ")

		For i As Integer = 0 To jalurAwal.Count - 1
			Dim titik As Integer = jalurAwal(i)
			Console.Write(IIf(i = 0, "", "-") & Chr(titik + 65))
		Next
		Console.WriteLine("")
	End If
. . .

5e4. Jika kondisi diatas tidak terpenuhi,
maka lakukan perhitungan berikut (poin 5e4a – 5e4f)

Else
. . .

5e4a. Lakukan perhitungan berikut apabila terdapat jalur antara titik sebelumnya dan titik berikutnya (poin 5e4a1 – 5e4a3)

If daftarBiaya(titikSebelumnya, titikBerikutnya) <> 0 Then
. . .

5e4a1. Catat jalur sementara yang sudah terbentuk
dan simpan status titik yang sudah dikunjungi

Dim calonJalurAwal(jalurAwal.Count - 1) As Integer
Dim stNormal(daftartitik.Count - 1) As Boolean
Dim st(daftartitik.Count - 1) As Boolean
For i As Integer = 0 To jalurAwal.Count - 1
	Dim titik As Integer = jalurAwal(i)

	calonJalurAwal(i) = titik
	stNormal(titik) = True
	st(titik) = True

	Console.Write(IIf(i = 0, "", "-") & Chr(titik + 65))
Next

5e4a2. Tambahkan jalur sementara tersebut ke dalam daftar jalur awal

daftarJalurAwal.Add(calonJalurAwal)

5e4a3. Lakukan perhitungan pada semua daftar jalur tujuan yang sudah ditemukan (poin 5e4a3a – 5e4a3c)

5e4a3a. Lakukan perhitungan pada jalur antar titik dan status titik
Jika tidak terdapat jalur antar 2 titik bersebelahan, maka lanjutkan ke perhitungan jalur sementara berikutnya
Jika status titik tujuan ternyata sudah dikunjungi, maka lanjutkan ke perhitungan jalur sementara berikutnya

If calonJalurAwal(jalurAwal.Count - 1) = JalurTerpilih(0) Then

ElseIf daftarBiaya(calonJalurAwal(jalurAwal.Count - 1), JalurTerpilih(0)) <> 0 Then
	If st(JalurTerpilih(0)) = True Then Continue For
	st(JalurTerpilih(0)) = True
Else
	Continue For
End If

Dim isSelesai As Boolean = False
For j As Integer = 0 To JalurTerpilih.Length - 2
	If daftarBiaya(JalurTerpilih(j), JalurTerpilih(j + 1)) <> 0 Then
		If st(JalurTerpilih(j + 1)) = True Then
			isSelesai = True
			Exit For
		End If

		st(JalurTerpilih(j + 1)) = True
	End If
Next
If isSelesai Then Continue For

5e4a3b. Lakukan pengecekan apabila status semua titik bernilai true / benar

Dim isSemuaTrue As Boolean = True
For j As Integer = 0 To st.Length - 1
	If st(j) <> True Then
		isSemuaTrue = False
		Exit For
	End If
Next

5e4a3c. Apabila status semua titik bernilai true / benar,
maka hentikan perhitungan karena jalur gabungan sudah ditemukan

If isSemuaTrue Then
	Console.WriteLine("")
	Console.WriteLine("Jalur Gabungan sudah ditemukan")
	Console.Write("Jalur yang terbentuk = ")

	Dim jalurGabungan As New ArrayList()
	
	. . .

	Return jalurGabungan
End If

5e4b. Kurangi kedalaman pada posisi titik terhitung untuk masing-masing sisa titik yang tidak terhitung

For i As Integer = 0 To daftarIndukAwal.Count - 1
	depthAwal(jalurAwal.Count - 1) -= 1
Next

5e4c. Dan untuk sisa titik tersebut, beri nilai kedalaman dengan angka 0

For i As Integer = jalurAwal.Count To depthAwal.Count - 1
	depthAwal(i) = 0
Next

5e4d. Untuk semua titik dengan nilai kedalaman 0,
Hilangkan titik-titik tersebut dari jalur yang sedang dihitung
dan masukkan kembali titik-titik tersebut kedalam daftar titik yang sudah dihitung

While depthAwal(jalurAwal.Count - 1) <= 0
	Dim titikTerakhir As Integer = jalurAwal(jalurAwal.Count - 1)

	daftarIndukAwal.Add(titikTerakhir)
	jalurAwal.Remove(titikTerakhir)

	If jalurAwal.Count = 0 Then
		Console.WriteLine("Titik Awal   -> Jalur Tidak Ditemukan")
		Console.WriteLine("")
		isSemuaTitikAwalTerhitung = True
		Exit While
	End If

	depthAwal(jalurAwal.Count - 1) -= 1
End While

5e4e. Tentukan titik berikutnya dengan urutan terdekat setelah titik yang terakhir dihitung
Yaitu titik dengan selisih indeks positif terendah

Dim minSelisihPositif As Integer = Integer.MaxValue
For i As Integer = 0 To daftarIndukAwal.Count - 2
	If daftarIndukAwal(i) - titikTujuan > 0 AndAlso minSelisihPositif > daftarIndukAwal(i) - titikTujuan Then
		minSelisihPositif = daftarIndukAwal(i) - titikTujuan
		titikTerdekat = daftarIndukAwal(i)
		idxtitikTerdekat = i
	End If
Next

5e4f. Setelah menemukan titik terdekat,
Urutkan semua titik yang belum dihitung selain titik terdekat
Kemudian masukkan titik terdekat ini pada urutan pertama sebelum urutan tersebut

daftarIndukAwal.RemoveAt(idxtitikTerdekat)
daftarIndukAwal.Sort()
daftarIndukAwal.Insert(0, titikTerdekat)

5f. Lakukan perhitungan pada titik tujuan berurutan dari titik terakhir ke titik pertama
Metode yang digunakan adalah DFS (Depth First Search) (poin 5f1 – 5f4)

5f1. Masukkan titik berikutnya ke dalam jalur yang sedang dihitung
Dan hilangkan titik tersebut dari daftar titik yang sudah dihitung

jalurTujuan.Add(titikBerikutnya)
daftarIndukTujuan.RemoveAt(0)

5f2. Hitung kedalaman pada titik yang sedang dihitung
Apabila nilai kedalaman adalah 0, maka beri nilai awal kedalaman
Selain itu kurangkan nilai kedalamannya dengan 1

If depthTujuan(jalurTujuan.Count - 1) <= 0 Then
	depthTujuan(jalurTujuan.Count - 1) = depthNormal(jalurTujuan.Count - 1)
Else
	depthTujuan(jalurTujuan.Count - 1) -= 1
End If

5f3. Jika terdapat jalur antara titik sebelumnya dan titik berikutnya,
dan semua titik sudah dihitung semua atau jumlah titik yang sedang dihitung belum melebihi limit / batas maksimal kedalaman,
Lakukan pengecekan apakah semua titik sudah dihitung semua
Jika kondisi tersebut benar, maka hentikan perhitungan

If daftarBiaya(titikBerikutnya, titikSebelumnya) <> 0 _
	AndAlso (jalurTujuan.Count = daftartitik.Count Or jalurTujuan.Count < limit) Then

	If jalurTujuan.Count = daftartitik.Count Then
		Console.WriteLine("Titik Tujuan -> Jalur sudah ditemukan")
		Console.Write("Titik Tujuan -> Jalur yang terbentuk = ")

		For i As Integer = jalurTujuan.Count - 1 To 0 Step -1
			Dim titik As Integer = jalurTujuan(i)
			Console.Write(IIf(i = jalurTujuan.Count - 1, "", "-") & Chr(titik + 65))
		Next
		Console.WriteLine("")
	End If
. . .

5f4. Jika kondisi diatas tidak terpenuhi,
maka lakukan perhitungan berikut (poin 5f4a – 5f4f)

Else
. . .

5f4a. Lakukan perhitungan berikut apabila terdapat jalur antara titik sebelumnya dan titik berikutnya (poin 5f4a1 – 5f4a3)

If daftarBiaya(titikBerikutnya, titikSebelumnya) <> 0 Then
. . .

5e4a1. Catat jalur sementara yang sudah terbentuk
dan simpan status titik yang sudah dikunjungi

Dim calonJalurTujuan(jalurTujuan.Count - 1) As Integer
Dim stNormal(daftartitik.Count - 1) As Boolean
Dim st(daftartitik.Count - 1) As Boolean
For i As Integer = jalurTujuan.Count - 1 To 0 Step -1
	Dim titik As Integer = jalurTujuan(i)

	calonJalurTujuan(jalurTujuan.Count - 1 - i) = titik
	stNormal(titik) = True
	st(titik) = True

	Console.Write(IIf(i = jalurTujuan.Count - 1, "", "-") & Chr(titik + 65))
Next

5f4a2. Tambahkan jalur sementara tersebut ke dalam daftar jalur awal

daftarJalurTujuan.Add(calonJalurTujuan)

5f4a3. Lakukan perhitungan pada semua daftar jalur tujuan yang sudah ditemukan (poin 5f4a3a – 5f4a3c)

5f4a3a. Lakukan perhitungan pada jalur antar titik dan status titik
Jika tidak terdapat jalur antar 2 titik bersebelahan, maka lanjutkan ke perhitungan jalur sementara berikutnya
Jika status titik tujuan ternyata sudah dikunjungi, maka lanjutkan ke perhitungan jalur sementara berikutnya

If JalurTerpilih(jalurTujuan.Count - 1) = calonJalurTujuan(0) Then

ElseIf daftarBiaya(JalurTerpilih(jalurTujuan.Count - 1), calonJalurTujuan(0)) <> 0 Then
	If st(JalurTerpilih(jalurTujuan.Count - 1)) = True Then Continue For
	st(JalurTerpilih(jalurTujuan.Count - 1)) = True
Else
	Continue For
End If

Dim isSelesai As Boolean = False
For j As Integer = JalurTerpilih.Length - 2 To 0 Step -1
	If daftarBiaya(JalurTerpilih(j), JalurTerpilih(j + 1)) <> 0 Then
		If st(JalurTerpilih(j)) = True Then
			isSelesai = True
			Exit For
		End If

		st(JalurTerpilih(j)) = True
	End If
Next
If isSelesai Then Continue For

5f4a3b. Lakukan pengecekan apabila status semua titik bernilai true / benar

Dim isSemuaTrue As Boolean = True
For j As Integer = 0 To st.Length - 1
	If st(j) <> True Then
		isSemuaTrue = False
		Exit For
	End If
Next

5f4a3c. Apabila status semua titik bernilai true / benar,
maka hentikan perhitungan karena jalur gabungan sudah ditemukan

If isSemuaTrue Then
	Console.WriteLine("")
	Console.WriteLine("Jalur Gabungan sudah ditemukan")
	Console.Write("Jalur yang terbentuk = ")

	Dim jalurGabungan As New ArrayList()
	
	. . .

	Return jalurGabungan
End If

5f4b. Kurangi kedalaman pada posisi titik terhitung untuk masing-masing sisa titik yang tidak terhitung

For i As Integer = 0 To daftarIndukTujuan.Count - 1
	depthTujuan(jalurTujuan.Count - 1) -= 1
Next

5f4c. Dan untuk sisa titik tersebut, beri nilai kedalaman dengan angka 0

For i As Integer = jalurTujuan.Count To depthTujuan.Count - 1
	depthTujuan(i) = 0
Next

5f4d. Untuk semua titik dengan nilai kedalaman 0,
Hilangkan titik-titik tersebut dari jalur yang sedang dihitung
dan masukkan kembali titik-titik tersebut kedalam daftar titik yang sudah dihitung

While depthTujuan(jalurTujuan.Count - 1) <= 0
	Dim titikTerakhir As Integer = jalurTujuan(jalurTujuan.Count - 1)

	daftarIndukTujuan.Add(titikTerakhir)
	jalurTujuan.Remove(titikTerakhir)

	If jalurTujuan.Count = 0 Then
		Console.WriteLine("Titik Tujuan -> Jalur Tidak Ditemukan")
		Console.WriteLine("")
		isSemuaTitikTujuanTerhitung = True
		Exit While
	End If

	depthTujuan(jalurTujuan.Count - 1) -= 1
End While

5f4e. Tentukan titik berikutnya dengan urutan terdekat setelah titik yang terakhir dihitung
Yaitu titik dengan selisih indeks negatif terendah

Dim minSelisihNegatif As Integer = Integer.MinValue
For i As Integer = 0 To daftarIndukTujuan.Count - 2
	If daftarIndukTujuan(i) - titikTujuan < 0 AndAlso minSelisihNegatif < daftarIndukTujuan(i) - titikTujuan Then
		minSelisihNegatif = daftarIndukTujuan(i) - titikTujuan
		titikTerdekat = daftarIndukTujuan(i)
		idxtitikTerdekat = i
	End If
Next

5f4f. Setelah menemukan titik terdekat,
Urutkan semua titik yang belum dihitung selain titik terdekat dari titik terakhir ke titik pertama
Kemudian masukkan titik terdekat ini pada urutan pertama sebelum urutan tersebut

daftarIndukTujuan.RemoveAt(idxtitikTerdekat)
daftarIndukTujuan.Sort()
daftarIndukTujuan.Reverse()
daftarIndukTujuan.Insert(0, titikTerdekat)

6. Setelah menemukan jalur, maka hitung biaya untuk jalur tersebut

Dim biaya As Double = 0
For i As Integer = 0 To jalur.Count - 2
	Dim titikAwal As Integer = jalur(i)
	Dim titikTujuan As Integer = jalur(i + 1)

	biaya += daftarBiaya(titikAwal, titikTujuan)
Next

Hasil akhir adalah: (klik untuk perbesar gambar)

Berikut adalah hasil perhitungan yang menghasilkan jalur yang sah

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

Tidak semua inputan yang diinputkan akan menghasilkan sebuah jawaban jalur yang sah. Berikut adalah contoh hasil perhitungan yang tidak menghasilkan jalur yang sah

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.