Algoritma Mundur

Algoritma Mundur

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 a pendekatan kekerasan 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. Dengan demikian, 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 keadaan yang mungkin (solusi atau non-penyelesaian) masalah dari akar sebagai keadaan awal hingga daun sebagai keadaan terminal.

State Space Tree
State Space Tree

Algoritma Mundur

Backtrack(x)
    if x is not a solution
        return false
    if x is a new solution
        add to list of solutions
    backtrack(expand 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
Semua kemungkinan

Pohon ruang negara berikut menunjukkan solusi yang mungkin.

Pohon negara bagian
Sebutkan pohon dengan semua solusi

Aplikasi Algoritma Backtracking

  1. Untuk menemukan semua Jalur Hamilton yang ada dalam grafik.
  2. Untuk mengatasi masalah N Queen.
  3. Labirin memecahkan masalah.

  4. Masalah tur Ksatria.