nemdeterminisztikus algoritmus
A nemdeterminisztikus algoritmus olyan algoritmus, amely egy adott bemenet esetén több lehetséges végrehajtási utat választhat, és ezen utak közül legalább egy vezet a helyes megoldáshoz. A nemdeterminisztikus algoritmusok gyakran elméleti konstrukciók, amelyeket a számítástudományban, különösen a komplexitáselméletben használnak.
A nemdeterminisztikus algoritmusokat úgy képzeljük el, mintha egy “varázslatos” számítógép egyszerre próbálná ki az összes lehetséges megoldást, és kiválasztaná a helyeset.
Pszeudokód:
Nemdeterminisztikus_Algoritmus(G):
Válassz ki nemdeterminisztikusan egy csúcssorrendet P.
Ha P Hamiltoni út, akkor VISSZAIGAZOLÁS.
Egyébként ELUTASÍTÁS.
Python implementáció determinisztikus gépen (brute-force szimulációval):
from itertools import permutations
def is_hamiltonian_path(graph, path):
for i in range(len(path) - 1):
if path not in graph]:
return False
return True
def hamiltonian_path(graph):
nodes = list(graph.keys())
for path in permutations(nodes):
if is_hamiltonian_path(graph, path):
return path
return None
# Példa gráf
graph = {
'A': ,
'B': ,
'C': ,
'D':
}
result = hamiltonian_path(graph)
if result:
print("Hamiltoni út:", result)
else:
print("Nincs Hamiltoni út.")
Kimenet:
Hamiltoni út: ('A', 'B', 'D', 'C')
Pszeudokód:
Nemdeterminisztikus_Algoritmus(G, k):
Válassz ki nemdeterminisztikusan k csúcsot.
Ha a k csúcs egy teljes részgráfot alkot, akkor VISSZAIGAZOLÁS.
Egyébként ELUTASÍTÁS.
Python implementáció determinisztikus gépen:
from itertools import combinations
def is_clique(graph, nodes):
for i in range(len(nodes)):
for j in range(i + 1, len(nodes)):
if nodes not in graph]:
return False
return True
def find_clique(graph, k):
nodes = list(graph.keys())
for subset in combinations(nodes, k):
if is_clique(graph, subset):
return subset
return None
# Példa gráf
graph = {
'A': ,
'B': ,
'C': ,
'D':
}
k = 3
result = find_clique(graph, k)
if result:
print(f"{k}-méretű klikk található:", result)
else:
print(f"Nincs {k}-méretű klikk.")
Kimenet:
3-méretű klikk található: ('B', 'C', 'D')
A nemdeterminisztikus algoritmusok nem “futnak” a hagyományos számítógépeken, de az NP-problémák megfogalmazásában kulcsszerepük van. Az algoritmusokat gyakran determinisztikus módon szimuláljuk, például brute-force kereséssel, vagy heurisztikus módszerekkel (pl. genetikus algoritmusokkal, backtrackinggel, dinamikus programozással).
Ezek a problémák a NP osztályhoz tartoznak, és determinisztikus gépeken gyakran brute-force technikával közelítjük meg őket.