Backtracking Algorithm

Backtracking (orqaga qaytish) algoritmi — bu barcha mumkin bo'lgan yechimlar variantini tizimli ko'rib chiqish orqali kerakli natijani topish uchun brute force (to'liq saralash) yondashuvidan foydalanadigan rekursiv algoritmik texnikadir.

[!NOTE] Brute force (to'liq qidirish) yondashuvi — barcha mumkin bo'lgan yechimlarni birma-bir sinab ko'radi va ular orasidan shartlarni qanoatlantiruvchi eng maqbul yoki to'g'ri yechimlarni tanlaydi.

"Backtracking" (orqaga qaytish) atamasi shuni anglatadiki: agar joriy tanlangan qadam yoki yechim yo'li masalaning yakuniy yechimiga olib kelmasa (yoki qo'yilgan cheklovlarga zid bo'lib qolsa), algoritm ortga — oldingi qadamga qaytadi (backtrack qiladi) va boshqa muqobil yo'llarni sinab ko'radi. Shu sababli, ushbu yondashuvda doimo rekursiya qo'llaniladi.

Ushbu yondashuv bir nechta to'g'ri yechimga ega bo'lgan yoki yechimlar kombinatsiyasini topish talab etiladigan murakkab masalalarni hal qilishda ishlatiladi. Agar sizga yagona global optimal yechim kerak bo'lsa, odatda dinamik dasturlashdan (Dynamic Programming) foydalanish maqsadga muvofiqdir.

State Space Tree

Holatlar fazosi daraxti:

Holatlar fazosi daraxti (State Space Tree) — bu masalaning barcha mumkin bo'lgan holatlarini (yechim bo'lgan va yechim bo'lmagan holatlarni) ildizdan (boshlang'ich holat) barg tugunlarigacha (yakuniy to'xtash holati) daraxt ko'rinishida ifodalovchi tuzilmadir.

Holatlar fazosi daraxti (State Space Tree)

Backtracking algoritmining umumiy ishlash tartibi

Backtrack(x)
    if x yaroqli yechim bo'lmasa:
        return false
    if x to'liq yechim bo'lsa:
        yechimlar ro'yxatiga qo'shish
    backtrack(x ni kengaytirish)

Backtracking yondashuvi misoli

Masala: 2 ta o'g'il bola (B1, B2) va 1 ta qiz bolani (G) 3 ta o'rindiqqa joylashtirishning barcha mumkin bo'lgan usullarini toping.
Cheklov (shart): Qiz bola o'rtadagi (ikkinchi) o'rindiqda o'tirmasligi kerak.

Yechim:

3 ta odamni 3 ta o'rindiqqa joylashtirishning jami 3! = 6 ta varianti mavjud. Biz rekursiya yordamida barcha ehtimollarni birma-bir sinab ko'ramiz.

Barcha mumkin bo'lgan 6 ta variant:

Barcha 6 ta ehtimol

Quyidagi holatlar fazosi daraxti (state space tree) qaysi variantlar yechim bo'lishi va qaysilari cheklov tufayli rad etilishini (orqaga qaytilishini) ko'rsatadi:

Cheklov asosida yaroqsiz tarmoqlarni qirqib tashlash (pruning) va 4 ta yaroqli yechimni topish

E'tibor bering, qiz bola o'rtadagi o'rindiqqa o'tirgan holatlar (B1 G B2 va B2 G B1) shartni buzgani uchun ularning keyingi tarmoqlari o'rganilmasdan to'xtatiladi va algoritm orqaga qaytadi. Natijada faqat 4 ta to'g'ri yechim qoladi:

1. B1, B2, G
2. B2, B1, G
3. G, B1, B2
4. G, B2, B1

Dasturiy kod

package main

import "fmt"

func backtrack(bench int, used []bool, current []string, result *[][]string) {
	if bench == 3 {
		row := make([]string, len(current))
		copy(row, current)
		*result = append(*result, row)
		return
	}

	people := []string{"B1", "B2", "G"}
	for i, p := range people {
		if !used[i] {
			// Cheklov: Qiz bola (G) 2-o'rindiqda (indeks 1) o'tirmasligi kerak
			if bench == 1 && p == "G" {
				continue // Ushbu tarmoq rad etiladi va orqaga qaytiladi
			}

			used[i] = true
			current = append(current, p)
			backtrack(bench+1, used, current, result)
			current = current[:len(current)-1]
			used[i] = false
		}
	}
}

func main() {
	var result [][]string
	used := make([]bool, 3)

	backtrack(0, used, []string{}, &result)

	fmt.Printf("Mavjud yaroqli yechimlar soni: %d\n", len(result))
	for _, res := range result {
		fmt.Printf("%v\n", res)
	}
}

Backtracking algoritmining qo'llanilishi

• Gamilton yo'llarini topish (Hamiltonian Paths): Grafdagi har bir cho'qqiga aynan bir marta tashrif buyuradigan yo'llarni aniqlash.
• N-Queens (N ta farzin masalasi): Shaxmat doskasida farzinlarni bir-biriga xavf solmaydigan qilib joylashtirish.
• Labirint masalalari (Maze solving): Labirintning kirishidan chiqishigacha bo'lgan barcha to'siqsiz yo'llarni aniqlash.
• Otning yurishi masalasi (Knight's Tour): Shaxmat oti yordamida doskaning barcha kataklariga aynan bir marta qadam qo'yib chiqish.
• Sudoku va krossvordlarni yechish.