Algoritma Runut-balik (Backtracking)

Algoritma Runut-balik (Backtracking)

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

Algoritma Runut-balik (Backtracking)
  • 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  


Algoritma Runut-balik (Backtracking)

Algoritma Runut-balik (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:

Algoritma Runut-balik (Backtracking)

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

Algoritma Runut-balik (Backtracking)


Contoh runut-balik pada sebuah labirin:

Algoritma Runut-balik (Backtracking)
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) 


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