Algoritma DLS (Depth Limited Search)


Algoritma DLS (Depth Limited Search) adalah salah satu algoritma yang digunakan untuk pencarian jalur. Contoh yang dibahas kali ini adalah mengenai pencarian jalur yang melalui semua titik.
Algoritma ini merupakan variasi dari Algoritma DFS (Depth First Search) yang sudah dijelaskan sebelumnya. Jika Algoritma DFS (Depth First Search) melakukan perhitungan (yang dimulai dengan titik terakhir) dengan cara menghabiskan semua tingkatan / kedalaman dari sebuah titik, maka algoritma ini memiliki batasan dimana perhitungan pada sebuah titik hanya dihitung sampai pada kedalaman tertentu. Setelah semua kemungkinan pada kedalaman itu sudah habis, kemudian akan dilanjutkan pada titik berikutnya.



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

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

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



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

* 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.


Langkah-langkah penggunaan algoritma ini adalah

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

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

3. Tentukan titik awal pencarian jalur

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

Memasuki perhitungan pada fungsi DLS

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

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

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

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

4e. Lakukan perhitungan selama masih ada titik yang belum dihitung (poin 4e1 – 4e4)

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

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

4e3. 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,
maka lakukan pengecekan apakah semua titik sudah dihitung semua
Jika kondisi tersebut benar, maka hentikan perhitungan

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

4e4a. Tampilkan pesan kesalahan apabila jumlah titik yang sedang dihitung sudah melebihi limit / batas maksimal kedalaman

4e4b. Tampilkan pesan kesalahan apabila tidak terdapat jalur antara titik sebelumnya dan titik berikutnya

4e4c. Kurangi kedalaman pada posisi titik terhitung untuk masing-masing sisa titik yang tidak terhitung

4e4d. Dan untuk sisa titik tersebut, beri nilai kedalaman dengan angka 0

4e4e. 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

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

4e4g. 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

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


Hasil akhir adalah: (klik untuk perbesar gambar)

Berikut adalah perhitungan jalur dengan menggunakan limit sebanyak jumlah titik, yaitu sebanyak 5 tingkat
cmd79

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

Berikut adalah perhitungan jalur dengan menggunakan limit hanya sebanyak 3 tingkat
Karena hanya menggunakan 3 tingkat saja, sedangkan solusi yang dicari harus berjumlah 5 titik, maka solusi tidak dapat ditemukan
cmd80 limit 3


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.

Tinggalkan sebuah komentar

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