To‘liq qidiruv va backtracking

To‘liq qidiruv

To‘liq perebor — barcha variantlarni tekshirib, mosini tanlash. Eng oddiy va eng ishonchli yechim: agar n kichik bo‘lsa (masalan, 10–20 gacha), ko‘pincha shuning o‘zi yetadi.

from itertools import combinations, permutations, product

best = max(sum(c) for c in combinations(nums, 3) if sum(c) <= limit)   # 3 tadan tanlash
for p in permutations(range(n)): ...                                    # barcha tartiblar
for bits in product([0, 1], repeat=n): ...                              # barcha qism to‘plamlar

Qachon ishlatiladi

1. Chegaralar kichik — to‘g‘ridan-to‘g‘ri yechim.
2. Tez yechimni tekshirish uchun: kichik testlarda ikkalasining javobini solishtiring (stress-test).
3. Naqsh izlash: kichik n lar uchun javoblarni chiqarib, formulani ko‘rish.

Avval variantlar sonini hisoblang: 2²⁰ ≈ 10⁶ — bemalol, 2⁴⁰ — yo‘q.

Backtracking

Backtracking (orqaga qaytish) — javobni qadamma-qadam quramiz; yo‘l noto‘g‘ri bo‘lib chiqsa, oxirgi tanlovni bekor qilib, boshqasini sinaymiz. Bu aqlli to‘liq perebor.

def subsets(nums):
    result, cur = [], []

    def go(i):
        if i == len(nums):
            result.append(cur[:])
            return
        go(i + 1)              # nums[i] ni olmaymiz
        cur.append(nums[i])    # olamiz
        go(i + 1)
        cur.pop()              # bekor qilamiz — orqaga qaytish

    go(0)
    return result

Klassik masalalar

• Barcha qism to‘plamlar, perestanovkalar, kombinatsiyalar.
• N ta farzin (queen), sudoku, labirintdan barcha yo‘llar.

Kesish (pruning)

Javob bo‘lishi mumkin bo‘lmagan shoxni erta to‘xtating: masalan, yig‘indi allaqachon chegaradan oshgan bo‘lsa, chuqurroq kirmang. Bu vaqtni ko‘p marta qisqartiradi.