Algoritma Runut-balik (Backtracking) - Skripsi Teknik Informatika

Algoritma runut-balik/backtracking adalah algoritma yang berbasis pada DFS untuk mencari solusi persoalan secara lebih akurat. Algoritma runut-balik, yang merupakan perbaikan dari algoritma brute-force, secara sistematis mencari solusi persoalan di antara semua kemungkinan solusi yang ada.

Dengan metode runut-balik, kita tidak perlu memeriksa semua kemungkinan solusi yang ada. Hanya pencarian yang mengarah ke solusi saja yang selalu dipertimbangkan. Akibatnya, waktu pencarian dapat dihemat. Saat ini algoritma runut-balik banyak diterapkan untuk program games (seperti permainan tic-tac-toe, menemukan jalan keluar dalam sebuah labirin, catur, dll) dan masalah-masalah  pada bidang kecerdasan buatan (artificial intelligence).

Penggunaan dalam algoritma Runut-balik/Backtracking yaitu misalkan anda harus membuat rangkaian keputusan di antara beberapa pilihan, dimana:

• Anda tidak punya cukup informasi untuk mengetahui apa yang akan dipilih
• Tiap keputusan mengarah pada sekumpulhan pilihan baru
• Beberapa sekuens pilihan (bisa lebih dari satu) mungkin merupakan solusi persoalan

Backtracking adalah cara yang metodologis mencoba beberapa sekuens keputusan, sampai Anda menemukan sekuens yang “bekerja”

Contoh (Maze problem): diberikan sebuah labirin (maze), temukan lintasan dari titik awal sampai titik akhir

Baca juga Jasa Bimbingan Skripsi Teknik Informatika

• Pada tiap perpotongan, anda harus memutuskan satu diantara tiga pilihan:

1. Maju terus
2. Belok kiri
3. Belok kanan

• Anda tidak punya cukup informasi untuk memilih pilihan yang benar (yang mengarah ke titik akhir)
• Tiap pilihan mengarah ke sekumpulan pilihan lain
• Satu atau lebih sekuens pilihan mengarah ke solusi.
• Backtracking (runut-balik) dapat digunakan untuk  persoalan seperti ini

Animasi Backtracking  

Contoh runut-balik pada sebuah labirin. Runut-balik diperlihatkan dengan 

garis putus-putus.

Penyelesaian dengan bactracking:

• Bagi lintasan menjadi sederetan langkah. 
• Sebuah langkah terdiri dari pergerakan satu unit sel pada arah tertentu. 
• Arah yang mungkin: lurus (straight), kiri (left), ke kanan (right). 

          Garis besar algoritma runut-baliknya:

• Bagaimana mengetahui langkah yang mana yang perlu dijejaki kembali? 

Ada dua solusi untuk masalah ini:

1. Simpan semua langkah yang pernah dilakukan, atau kedua

2. Gunakan rekursi (yang secara implisit menyimpan semua langkah). 

• Rekursi adalah solusi yang lebih mudah.

Contoh runut-balik pada sebuah labirin:

Runut-balik diperlihatkan dengan 

garis putus-putus.

Jika kita menggambarkan sekuens pilihan yang kita lakukan, maka diagram berbentuk  seperti pohon.

• Simpul daun merupakan:

1. Titik backtrack, atau
2. Simpul goal

Pada titik backtrack, simpul tersebut menjadi mati (tidak bisa diekspansi lagi) 

Baca juga Jasa Bimbingan Skripsi Teknik Informatika

Jadi kesimpulan yang bisa diambil adalah sebagai berikut :

• Runut-balik (backtracking) adalah algoritma pencarian solusi yang berbasis pada DFS.

• Algoritma runut-balik banyak diterapkan untuk program games :

1. Permainan tic-tac-toe, 
2. Menemukan jalan keluar dalam sebuah labirin,
3. Catur, crossword puzzle, sudoku, dan masalah-masalah  pada bidang kecerdasan buatan (artificial intelligence).  

• Algoritma runut-balik merupakan perbaikan dari algoritma brute-force (exhaustive search)

• Pada exhaustive search, semua kemungkinan solusi dieksplorasi satu per satu.

• Pada backtracking, hanya pilihan yang mengarah ke solusi yang dieksplorasi, pilihan yang tidak mengarah ke solusi tidak dipertimbangkan lagi

 


Kata Kunci : Algoritma Runut-balik (Backtracking) ,Skripsi Teknik Informatika , Contoh Skripsi, Skripsi, Contoh Algoritma, Backtracking