backtracking

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ű)

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.

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.

def is_safe(queens, row, col):
    for c in range(col):
        r = queens
        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 = row
                backtrack(col + 1)
    queens =  * n
    solutions = 
    backtrack(0)
    return solutions

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.

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.

• 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

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

• 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)

• backtracking - Szótár.net (en-hu)
• backtracking - Sztaki (en-hu)
• backtracking - Merriam–Webster
• backtracking - Cambridge
• backtracking - WordNet
• backtracking - Яндекс (en-ru)
• backtracking - Google (en-hu)
• backtracking - Wikidata
• backtracking - Wikipédia (angol)