Wikiszótár

nemdeterminisztikus algoritmus

Magyar

Kiejtés

  • IPA: [ ˈnɛmdɛtɛrministikuʃɒlɡoritmuʃ]

Főnév

nemdeterminisztikus algoritmus

  1. (matematika)

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.


Fő jellemzők

  1. Végrehajtás: A nemdeterminisztikus algoritmus több ágon egyszerre tud haladni.
  2. Megoldáskeresés:
    • A bemenetek különböző lehetőségeket generálnak.
    • Az algoritmus “kipróbálja” a különböző lehetőségeket, és ha van helyes megoldás, akkor azt megtalálja.
  3. Determinista ellenőrzés:
    • A megoldás helyessége determinisztikus módon ellenőrizhető.
  4. Komplexitás:
    • Nemdeterminisztikus algoritmusok futási ideje ( O(n) ), ha nemdeterminisztikus gépen futtatjuk.
    • Determinisztikus gépeken a brute-force keresés vagy más technikák használatával valósítjuk meg.


Példák nemdeterminisztikus algoritmusokra

  1. NP-teljes problémák: A nemdeterminisztikus algoritmusok különösen hasznosak az NP-teljes problémák megfogalmazásában. Egy NP-probléma esetén a megoldás ellenőrzése hatékonyan, determinisztikusan megoldható, de a megoldás megtalálása nemdeterminisztikus.

1. Hamiltoni út probléma

  • Probléma: Adott egy gráf. Létezik-e benne olyan út, amely pontosan egyszer érinti a gráf minden csúcsát?
  • Nemdeterminisztikus algoritmus:
    1. Nemdeterminisztikusan válassz egy lehetséges utat a gráfban.
    2. Ellenőrizd, hogy az út tartalmazza-e az összes csúcsot pontosan egyszer.

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[i+1] not in graph[path[i]]:
            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'],
    'B': ['A', 'C', 'D'],
    'C': ['A', 'B', 'D'],
    'D': ['B', 'C']
}

result = hamiltonian_path(graph)
if result:
    print("Hamiltoni út:", result)
else:
    print("Nincs Hamiltoni út.")

Kimenet: 

Hamiltoni út: ('A', 'B', 'D', 'C')

2. KLIK probléma

  • Probléma: Adott egy gráf ( G ) és egy egész szám ( k ). Létezik-e ( G )-ben egy legalább ( k ) csúcsból álló teljes részgráf (klikk)?
  • Nemdeterminisztikus algoritmus:
    1. Válassz ki nemdeterminisztikusan ( k ) csúcsot a gráfból.
    2. Ellenőrizd, hogy a kiválasztott csúcsok között minden él létezik-e (teljes gráf).

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[j] not in graph[nodes[i]]:
                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'],
    'B': ['A', 'C', 'D'],
    'C': ['A', 'B', 'D'],
    'D': ['B', 'C']
}

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')

Nemdeterminisztikus algoritmus a gyakorlatban

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).


Összefoglalás

  1. Nemdeterminisztikus algoritmus: Olyan algoritmus, amely több utat próbálhat egyszerre.
  2. Megoldáskeresés: Minden lehetséges megoldást egyidejűleg “kipróbál”.
  3. Gyakorlati példa:
    • Hamiltoni út probléma,
    • KLIK probléma,
    • SAT probléma (kielégíthetőségi probléma).

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.

Fordítások

Tartalom

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=nemdeterminisztikus_algoritmus&oldid=3480706”