visszalépéses keresés

• IPA:

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.

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.

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

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.

def is_safe(board, row, col, n):
    # Ellenőrizzük az oszlopot
    for i in range(row):
        if board == 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 == 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 == 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 = 1
            if solve_n_queens(board, row + 1, n):
                return True
            board = 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 =  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

#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 == 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 == 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 == 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 = 1;
            if (solve_n_queens(board, row + 1, n))
                return true;
            board = 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

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.

• angol: backtrack search (en)
• orosz: поиск с возвратом (ru) (poisk s vozvratom)

• visszalépéses keresés - Értelmező szótár (MEK)
• visszalépéses keresés - Etimológiai szótár (UMIL)
• visszalépéses keresés - Szótár.net (hu-hu)
• visszalépéses keresés - DeepL (hu-de)
• visszalépéses keresés - Яндекс (hu-ru)
• visszalépéses keresés - Google (hu-en)
• visszalépéses keresés - Helyesírási szótár (MTA)
• visszalépéses keresés - Wikidata
• visszalépéses keresés - Wikipédia (magyar)