Ugrás a tartalomhoz

backtracking

A Wikiszótárból, a nyitott szótárból

Angol


Főnév

backtracking (tsz. backtrackings)

  1. (informatika) visszalépéses keresés A backtracking (visszalépéses keresés) egy algoritmikus módszer, amellyel komplex kombinatorikus problémák oldhatók meg – olyanok, ahol egy megoldástér minden pontját részmegoldások lépésenkénti bővítésével fedezzük fel, és visszalépünk, ha zsákutcába futunk.

Ez a módszer különösen hasznos keresési, optimalizálási, és döntési problémákban, például:

  • N-királynő probléma
  • Sudoku
  • Kakuro
  • Hamilton-út, gráf színezés
  • Backtracking-es fa bejárások (DFS-szerű)


🧠 1. Alapötlet

A backtracking lényege:

  • Lépésről lépésre építjük a megoldást.
  • Minden lépésnél ellenőrizzük, hogy az aktuális részmegoldás érvényes-e.
  • Ha igen, tovább haladunk.
  • Ha nem, akkor visszalépünk egy korábbi állapothoz, és új irányba próbálkozunk.


📐 2. Általános sablon

def backtrack(state):
    if solution_found(state):
        save_solution(state)
        return

    for option in possible_choices(state):
        if is_valid(option, state):
            apply(option, state)
            backtrack(state)
            undo(option, state)

Ez egy rekurzív mélységi keresés (DFS), ahol minden „ág” csak akkor folytatódik, ha nem sérti a korlátozásokat.


📦 3. Példa: N-Királynő probléma (rövidített)

def is_safe(queens, row, col):
    for c in range(col):
        r = queens[c]
        if r == row or abs(r - row) == abs(c - col):
            return False
    return True

def solve_n_queens(n):
    def backtrack(col):
        if col == n:
            solutions.append(queens[:])
            return
        for row in range(n):
            if is_safe(queens, row, col):
                queens[col] = row
                backtrack(col + 1)
    queens = [-1] * n
    solutions = []
    backtrack(0)
    return solutions

🔁 4. Backtracking működésének lépései

  1. Indulás egy üres megoldásból.
  2. Egy új lépés hozzáadása a részmegoldáshoz.
  3. Ha az új részmegoldás érvénytelen, akkor:
    • Visszalépés (backtrack) → új ágat próbálunk.
  4. Ha a megoldás teljes és érvényes, akkor:
    • Eltároljuk/kilépünk.


🎯 5. Hol hatékony?

Backtracking akkor hasznos, ha:

  • A megoldási tér exponenciális.
  • Sok érvénytelen ágat lehet kizárni korán.
  • Pl. Sudoku esetén egyetlen rossz szám kizárhat sok megoldást → kevesebb felesleges lépés.


🧮 6. Tipikus problémák backtrackinggel

Probléma Rövid leírás
N-Queens N királynő elhelyezése, ne üssék egymást
Sudoku 9×9 rács kitöltése szabályok szerint
Permutációk Összes lehetséges sorrend előállítása
Kombinációk Adott elemszámú részhalmazok
Gráf színezés Minden csúcs színezése szomszédos konfliktus nélkül
Labirintus Útvonal megtalálása a célig
Subset Sum Elemsorozatból adott összeg képzése


⚡ 7. Optimalizálás – intelligens keresés

  • Forward Checking – előre kizárja azokat az értékeket, amelyek biztosan érvénytelenek
  • Constraint Propagation – a döntés után új következtetéseket vonunk le más változókra
  • Heurisztikák – „legígéretesebb” lépés választása előre (pl. MRV, LCV)
  • Memoizáció – ismétlődő állapotok elkerülése


🧾 8. Előnyök és hátrányok

✅ Előnyök:

  • Könnyű implementálni rekurzívan
  • Teljes, azaz minden megoldást megtalál
  • Nagyon rugalmas, sokféle problémára használható

❌ Hátrányok:

  • Lassú nagy keresési tér esetén
  • Rossz választási sorrend = sok felesleges átfutás
  • Nem garantálja az optimális megoldást (csak ha kiegészítjük)


🧩 9. Összefoglalás

Fogalom Jelentés
Backtracking Rekurzív keresési módszer, visszalép ha nem érvényes lépés
Alkalmazási terület CSP, puzzle, keresési problémák
Kulcselemek Részmegoldás, érvényesség ellenőrzése, visszalépés
Optimalizálható? Igen, heurisztikával és előfeldolgozással
Legfontosabb jellemző DFS + kizárás + próbálkozás


További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=backtracking&oldid=3494934”