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.
A hatványhalmaz egy halmaz összes részhalmazának halmaza. Egy ( n ) elemű halmaz ( 2^n ) részhalmazzal rendelkezik.
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) # Részhalmazok a n-1 elemre
return subsets + ] for subset in subsets]
# Példa használat
original_set =
power_set = generate_power_set(original_set)
print("Hatványhalmaz:", power_set)
Kimenet:
Hatványhalmaz: , , , , , , , ]
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.
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 == col or abs(board - 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 = col
backtrack(board, row + 1, solutions)
solutions =
backtrack( * 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): , ]
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.
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]] for i in range(n-1))
current_distance += distance_matrix]] # 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 = [
,
,
,
]
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
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.