Back-tracking (runut balik) adalah salah satu algoritma yang memakai basis DFS (pencarian dalam) untuk mencari solusi yang lebih mendalam. Sebenarnya, backtracking merupakan perbaikan dari algoritma brute-force. Backtracking juga merupakan algoritma rekursif. Backtaracking sering digunakan untuk memecahkan beberapa masalah, sebagai contoh Menara Hanoi dan Clique.....
Menara Hanoi adalah permainan matematis yang menggunakan tiga tiang da beberapa cakram. Permainan ini ditemukan oleh matematikawan Perancis, Edouard Lucas, pada tahun 1883.Initial statenya adalah semua cakram disusun secara berurutan dari yang paling besar hingga yang paling kecil di tiang paling kiri, sementara final statenya adalah semua cakram disusun secara berurutan seperti initial state di tiang paling kanan. Peraturannya adalah:
1. Hanya boleh memindahkan satu cakram setiap satu perpindahan.
2. Cakram yang diambil adalah cakram yang paling atas dari tiang-tiang yang tersedia.
3. Tidak dipernolehkan memindahkan cakram yang lebih besar di atas cakram yang lain.
Peramainan ini sering digunakan dalam penelitian psikologis dan fdalm pengajaran algoritma rekursif....
Clique adalah sebuah upagraf lengkap yang dipeoleh dari suatu graf yang terdiri dari beberapa simpul (minimal 3 simpul) dimana setiap simpul memeiliki jarak yang dekat dengan simpul lainnya. salah satu contoh permasalahan yang serupa dengan Clique adalah struktur molekul DNA.
