Dalam tutorial ini, anda akan belajar apa itu algoritma backtracking. Anda juga akan mendapat contoh pendekatan backtracking.
Algoritma backtracking adalah algoritma penyelesaian masalah yang menggunakan pendekatan brute force untuk mencari output yang diinginkan.
Pendekatan Brute force mencuba semua kemungkinan penyelesaian dan memilih penyelesaian yang diinginkan / terbaik.
Istilah mundur menunjukkan bahawa jika penyelesaian semasa tidak sesuai, maka mundur dan cuba jalan penyelesaian lain. Oleh itu, rekursi digunakan dalam pendekatan ini.
Pendekatan ini digunakan untuk menyelesaikan masalah yang mempunyai pelbagai penyelesaian. Sekiranya anda mahukan penyelesaian yang optimum, anda mesti mencari pengaturcaraan dinamik.
Pokok Angkasa Negeri
Pohon keadaan ruang adalah pokok yang mewakili semua kemungkinan keadaan (penyelesaian atau tidak penyelesaian) masalah dari akar sebagai keadaan awal hingga daun sebagai keadaan terminal.
Pokok Angkasa Negeri
Algoritma Backtracking
Backtrack (x) jika x bukan penyelesaian mengembalikan false jika x adalah penyelesaian baru tambahkan ke senarai penyelesaian backtrack (luaskan x)
Contoh Pendekatan Backtracking
Masalah: Anda ingin mencari semua kemungkinan cara mengatur 2 budak lelaki dan 1 gadis di 3 bangku. Kekangan: Gadis tidak boleh berada di bangku tengah.
Penyelesaian: Terdapat sejumlah 3! = 6 kemungkinan. Kami akan mencuba semua kemungkinan dan mendapatkan penyelesaian yang mungkin. Kami secara berulang-ulang mencuba semua kemungkinan.
Semua kemungkinan adalah:
Semua kemungkinan
Pokok ruang keadaan berikut menunjukkan kemungkinan penyelesaian.
Nyatakan pokok dengan semua penyelesaiannya
Aplikasi Algoritma Backtracking
- Untuk mencari semua Jalur Hamilton yang terdapat dalam grafik.
- Untuk menyelesaikan masalah N Queen.
- Masalah penyelesaian labirin.
- Masalah lawatan The Knight.
