Kamis, 24 Desember 2020

Backtracking From A Novice Point Of View

Ini hasil saya mengintip buku bacaan si anak anak yang sedang belajar komputer... Backtracking. di sana langsung terpampang kasus 2 Queen Problems.. intinya si queen di papan catur harus dipasang  di tempat yang nggak saling 'mematikan' alisa check mate. Naaah utnuk bisa begitu bagaimana caranya? terus si buku langsung mengeluarkan tahap tahapan program dan bahasa coding C yang (menurut saya) njelimet itu.. Gimana enggak.. penulisnya memang terkenal sebagai juara dalam urusan Competitive Programming, jadi maklum saja bahasanya bahasa planet.

Ok, karena masih penasaran dan biar bisa agak nyambung sama anak anak yang lagi beljar topik ini,  akhirnya saya Google tentang Backtracking. Ok, saya menemukan yang agak mudah dicerna di sini: https://www.geeksforgeeks.org/backtracking-introduction/. Menurut saya ini cocok sekali untuk pemula karena memang dari dasar sampai ke Coding, dikupas satu persatu tanpa loncat loncat. Kita juga bisa melihat N Queen Problem ini di Youtube, lebih tuntas lagi. 

  • https://www.geeksforgeeks.org/n-queen-problem-backtracking-3/
  • https://www.youtube.com/watch?v=0DeznFqrgAI

Jadi intinya Backtracking itu adalah mencari kemungkinan satu persatu secara sistematis dan berulang ulang untuk mendapatkan hasil yang benar, kalau dalam step yang sedang dijalankan ternyata salah, harus kembali ke step yang masih benar dan lanjutkan dengan pilihan berikutnya. 

Penjelasan lengkapnya dilihat di: https://medium.com/@viveksonani22/4-queens-problem-using-backtracking-632b9f3d6620

Gambar dari Geeks For Geeks

Misalnya  kalau ternyata posisi Queen yang kita pilih ternyata ada yang 'mematikan' (atau pilihan salah). kita harus kembali ke step berikutnya sampai pilihan itu benar dan melanjutkan ke alternatif lainnya. 

Nah Back tracking ini konon lebih cepat dibandingkan algoritma biasa karena kalau algoritma bisasa harus memeriksa satu persatu sampai selesai dan memasukkannya ke dalam list kalau solusinya benar. Backtracking, memeriksa pilihan yang benar dan jika ternyata salah tidak harus mengulang dari awal tapi hanya mundur satu step ke belakang dan memilih alternatif berikutnya lalu memasukkannya ke dalam list.

Menjalankan Backtracking bisa menggunakan Fungsi Rekursif atau cara lainnya.

Tidak ada komentar:

Posting Komentar