Wikiszótár

exponenciális algoritmus

Magyar

Kiejtés

  • IPA: [ ˈɛksponɛnt͡sijaːliʃɒlɡoritmuʃ]

Főnév

exponenciális algoritmus

  1. (matematika, algoritmusok, számításelmélet)

Az exponenciális algoritmusok olyan algoritmusok, amelyek idő- vagy tárigénye ( O(2^n) ), ( O(3^n) ), vagy általánosan ( O(k^n) ) nagyságrendű, ahol ( n ) a bemeneti méret, és ( k > 1 ). Ezek az algoritmusok általában csak kisebb méretű bemenetekre alkalmazhatók, mivel a futási idő exponenciálisan nő a bemenet méretével.


Példa 1: Hatványhalmaz generálása (( O(2^n) ))

A hatványhalmaz egy halmaz összes részhalmazának halmaza. Egy ( n ) elemű halmaz ( 2^n ) részhalmazzal rendelkezik.

Python-implementáció:

def generate_power_set(s):
    """
    Hatványhalmaz generálása rekurzívan.
    
    :param s: Eredeti halmaz (lista formában)
    :return: Részhalmazok listája
    """
    if len(s) == 0:
        return [[]]
    
    subsets = generate_power_set(s[:-1])  # Részhalmazok a n-1 elemre
    return subsets + [subset + [s[-1]] for subset in subsets]

# Példa használat
original_set = [1, 2, 3]
power_set = generate_power_set(original_set)
print("Hatványhalmaz:", power_set)

Kimenet: 

Hatványhalmaz: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

Példa 2: Közönséges hátterezés (Backtracking) - Királynők problémája (( O(n!) ))

A királynők problémája egy klasszikus példa, amelyben ( n ) sakktábla méret esetén ( n ) királynőt kell úgy elhelyezni, hogy azok ne üthessék egymást.

Python-implementáció:

def solve_n_queens(n):
    """
    Királynők problémájának megoldása hátterezéssel.
    
    :param n: Tábla mérete (n x n)
    :return: Az összes lehetséges megoldás listája
    """
    def is_safe(board, row, col):
        for i in range(row):
            if board[i] == col or abs(board[i] - col) == abs(i - row):
                return False
        return True

    def backtrack(board, row, solutions):
        if row == n:
            solutions.append(board[:])
            return
        for col in range(n):
            if is_safe(board, row, col):
                board[row] = col
                backtrack(board, row + 1, solutions)

    solutions = []
    backtrack([-1] * n, 0, solutions)
    return solutions

# Példa használat
n = 4
solutions = solve_n_queens(n)
print(f"{n} királynők megoldásai ({len(solutions)} megoldás):", solutions)

Kimenet: 

4 királynők megoldásai (2 megoldás): [[1, 3, 0, 2], [2, 0, 3, 1]]

Példa 3: Utazó ügynök problémája (TSP) - Brute Force (( O(n!) ))

Az utazó ügynök problémában az összes város lehetséges sorrendjét végignézzük, hogy megtaláljuk a legrövidebb utat.

Python-implementáció:

from itertools import permutations

def tsp_brute_force(distance_matrix):
    """
    Brute force megoldás az utazó ügynök problémára.
    
    :param distance_matrix: Távolságokat tartalmazó mátrix
    :return: A legrövidebb út és annak hossza
    """
    n = len(distance_matrix)
    cities = range(n)
    shortest_path = None
    min_distance = float('inf')

    for perm in permutations(cities):
        current_distance = sum(distance_matrix[perm[i]][perm[i+1]] for i in range(n-1))
        current_distance += distance_matrix[perm[-1]][perm[0]]  # Visszatérés az első városba
        if current_distance < min_distance:
            min_distance = current_distance
            shortest_path = perm
    
    return shortest_path, min_distance

# Példa használat
distance_matrix = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]

path, distance = tsp_brute_force(distance_matrix)
print(f"Legrövidebb út: {path}, Hossz: {distance}")

Kimenet: 

Legrövidebb út: (0, 1, 3, 2), Hossz: 80

Összefoglalás

Az exponenciális algoritmusok erősek, de nem skálázódnak jól nagy bemenetekkel. Ezek az algoritmusok kis bemeneti méretű problémákra használhatók, vagy heurisztikákkal kell őket kombinálni, hogy csökkentsük a keresési tér nagyságát.

Fordítások

Tartalom

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=exponenciális_algoritmus&oldid=3480682”