Wikiszótár

visszalépéses keresés

Magyar

Kiejtés

  • IPA: [ ˈvisːɒleːpeːʃɛʃkɛrɛʃeːʃ]

Főnév

visszalépéses keresés

  1. (matematika, algoritmusok) A visszalépéses keresés egy általános algoritmikus technika, amelyet problémák megoldására használnak, különösen akkor, ha a megoldás keresési térben történő kiterjesztése iteratívan és feltételesen történik. Az algoritmus rekurzívan próbálja ki a lehetséges megoldásokat, és ha egy részmegoldás nem vezet sikerhez, visszalép egy korábbi állapotba.


Alapelvek

  1. Keresési tér:
    • A problémát olyan keresési térként modelláljuk, amelyben minden csomópont egy részleges megoldást reprezentál.
  2. Rekurzív próbálkozás:
    • A részleges megoldásokból kiindulva próbáljuk meg kiterjeszteni azt egy teljes megoldássá.
  3. Visszalépés:
    • Ha egy adott részmegoldás nem vezet teljes megoldáshoz (nem kielégítő), visszalépünk, és más lehetőségeket próbálunk ki.
  4. Hatékonyság:
    • A “vágás” technikát használjuk, hogy elkerüljük a nyilvánvalóan rossz megoldási útvonalakat.


Pszeudokód

Backtrack(solution):
    ha a solution kielégítő:
        térj vissza a solution
    különben:
        minden lehetséges választási lehetőség esetén:
            ha a választás érvényes:
                add hozzá a választást a solution-höz
                hívj meg Backtrack-et a frissített solution-nel
                ha a frissített solution megoldást eredményezett:
                    térj vissza a solution
                távolítsd el a választást (visszalépés)
    térj vissza sikertelenként

Alkalmazási példák

  1. N királynő problémája:
    • Helyezzünk el (N) királynőt egy (N N) sakktáblán úgy, hogy ne támadhassák egymást.
  2. Sudoku megoldása:
    • Töltsük ki a táblázatot úgy, hogy a szabályok teljesüljenek.
  3. Hátizsák probléma:
    • Válasszunk tárgyakat úgy, hogy a hátizsák kapacitása ne lépje túl a megadott értéket.
  4. Labirintus keresése:
    • Találjunk utat egy adott kezdőpontból a célhoz.


Python implementáció

N királynő problémája

def is_safe(board, row, col, n):
    # Ellenőrizzük az oszlopot
    for i in range(row):
        if board[i][col] == 1:
            return False

    # Átlós ellenőrzés (bal felülről jobb alulra)
    for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
        if board[i][j] == 1:
            return False

    # Átlós ellenőrzés (jobb felülről bal alulra)
    for i, j in zip(range(row, -1, -1), range(col, n)):
        if board[i][j] == 1:
            return False

    return True

def solve_n_queens(board, row, n):
    if row >= n:
        return True

    for col in range(n):
        if is_safe(board, row, col, n):
            board[row][col] = 1
            if solve_n_queens(board, row + 1, n):
                return True
            board[row][col] = 0  # Visszalépés

    return False

def print_solution(board):
    for row in board:
        print(" ".join("Q" if x == 1 else "." for x in row))

# Példa
n = 8
board = [[0 for _ in range(n)] for _ in range(n)]

if solve_n_queens(board, 0, n):
    print("Megoldás:")
    print_solution(board)
else:
    print("Nincs megoldás.")

Kimenet (8 királynő esetén): 

Megoldás:
Q . . . . . . .
. . . . Q . . .
. . . . . . Q .
. . Q . . . . .
. . . . . Q . .
. Q . . . . . .
. . . Q . . . .
. . . . . . . Q

C++ implementáció

N királynő problémája

#include <iostream>
#include <vector>
using namespace std;

bool is_safe(const vector<vector<int>>& board, int row, int col, int n) {
    // Ellenőrizzük az oszlopot
    for (int i = 0; i < row; ++i)
        if (board[i][col] == 1)
            return false;

    // Átlós ellenőrzés (bal felülről jobb alulra)
    for (int i = row, j = col; i >= 0 && j >= 0; --i, --j)
        if (board[i][j] == 1)
            return false;

    // Átlós ellenőrzés (jobb felülről bal alulra)
    for (int i = row, j = col; i >= 0 && j < n; --i, ++j)
        if (board[i][j] == 1)
            return false;

    return true;
}

bool solve_n_queens(vector<vector<int>>& board, int row, int n) {
    if (row >= n)
        return true;

    for (int col = 0; col < n; ++col) {
        if (is_safe(board, row, col, n)) {
            board[row][col] = 1;
            if (solve_n_queens(board, row + 1, n))
                return true;
            board[row][col] = 0;  // Visszalépés
        }
    }

    return false;
}

void print_solution(const vector<vector<int>>& board) {
    for (const auto& row : board) {
        for (int cell : row)
            cout << (cell == 1 ? "Q " : ". ");
        cout << endl;
    }
}

int main() {
    int n = 8;
    vector<vector<int>> board(n, vector<int>(n, 0));

    if (solve_n_queens(board, 0, n)) {
        cout << "Megoldás:" << endl;
        print_solution(board);
    } else {
        cout << "Nincs megoldás." << endl;
    }

    return 0;
}

Kimenet (8 királynő esetén): 

Megoldás:
Q . . . . . . .
. . . . Q . . .
. . . . . . Q .
. . Q . . . . .
. . . . . Q . .
. Q . . . . . .
. . . Q . . . .
. . . . . . . Q

Összegzés

A visszalépéses keresés hatékony módszer kombinatorikus problémák megoldására, különösen akkor, ha a probléma jól strukturált és a keresési tér könnyen korlátozható. Ez a megközelítés gyakran alkalmazható optimális megoldások keresésére, például az N királynő problémájában, Sudoku megoldásában, vagy útvonal keresésben.

Fordítások

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=visszalépéses_keresés&oldid=3479485”