Dalam tutorial ini, Anda akan mempelajari apa itu algoritma backtracking. Juga, Anda akan menemukan contoh pendekatan mundur.
Algoritma backtracking adalah algoritma pemecahan masalah yang menggunakan pendekatan brute force untuk menemukan keluaran yang diinginkan.
Pendekatan Brute force mencoba semua solusi yang mungkin dan memilih solusi yang diinginkan / terbaik.
Istilah mundur menunjukkan bahwa jika solusi saat ini tidak sesuai, maka mundur dan coba solusi lain. Jadi, rekursi digunakan dalam pendekatan ini.
Pendekatan ini digunakan untuk menyelesaikan masalah yang memiliki banyak solusi. Jika Anda menginginkan solusi yang optimal, Anda harus menggunakan pemrograman dinamis.
State Space Tree
Pohon keadaan ruang adalah pohon yang mewakili semua kemungkinan keadaan (solusi atau non-penyelesaian) masalah dari akar sebagai keadaan awal hingga daun sebagai keadaan terminal.
State Space Tree
Algoritma Mundur
Mundur (x) jika x bukan solusi kembalikan salah jika x adalah solusi baru tambahkan ke daftar solusi mundur (luaskan x)
Contoh Pendekatan Backtracking
Masalah: Anda ingin menemukan semua kemungkinan cara mengatur 2 anak laki-laki dan 1 perempuan di 3 bangku. Kendala: Gadis tidak boleh berada di bangku tengah.
Solusi: Totalnya ada 3! = 6 kemungkinan. Kami akan mencoba semua kemungkinan dan mendapatkan solusi yang memungkinkan. Kami secara rekursif mencoba semua kemungkinan.
Semua kemungkinannya adalah:
Semua kemungkinan
Pohon ruang negara berikut menunjukkan solusi yang mungkin.
Sebutkan pohon dengan semua solusi
Aplikasi Algoritma Backtracking
- Untuk menemukan semua Jalur Hamilton yang ada dalam grafik.
- Untuk mengatasi masalah N Queen.
- Labirin memecahkan masalah.
- Masalah tur Ksatria.
