A determinisztikus algoritmus olyan algoritmus, amely adott bemenet esetén mindig ugyanazt az eredményt adja, és végrehajtása során a lépések pontosan meghatározottak. Minden lépés előre definiált és nem tartalmaz véletlenszerűséget vagy bizonytalanságot.
Az algoritmus végrehajtása teljesen kiszámítható.
Ugyanarra a bemenetre mindig ugyanazt az eredményt adja.
Az algoritmus idő- és tárhasználata rögzített, a bemenettől függően.
Pl. Lineáris vagy bináris keresés.
A lineáris keresés adott lista elemeiben keres egy konkrét értéket.
def linear_search(arr, target):
"""
Determinisztikus lineáris keresés.
:param arr: Lista, amelyben keresünk.
:param target: Keresett érték.
:return: Az érték indexe, ha megtalálható, különben -1.
"""
for i in range(len(arr)):
if arr == target:
return i
return -1
# Példa használat
arr =
target = 7
result = linear_search(arr, target)
if result != -1:
print(f"Az érték ({target}) megtalálható az {result}. indexen.")
else:
print(f"Az érték ({target}) nincs a listában.")
Kimenet:
Az érték (7) megtalálható az 3. indexen.
A buborékrendezés egy determinisztikus algoritmus, amely az elemeket növekvő sorrendbe rendezi.
def bubble_sort(arr):
"""
Determinisztikus buborékrendezés.
:param arr: Rendezendő lista.
:return: A rendezett lista.
"""
n = len(arr)
for i in range(n):
for j in range(n - i - 1):
if arr > arr:
arr, arr = arr, arr
return arr
# Példa használat
arr =
print("Eredeti lista:", arr)
sorted_arr = bubble_sort(arr)
print("Rendezett lista:", sorted_arr)
Kimenet:
Eredeti lista: Rendezett lista:
A Dijkstra algoritmus egy determinisztikus algoritmus, amely egy gráfban keresi meg a legrövidebb utat egy forráscsúcsból.
import heapq
def dijkstra(graph, start):
"""
Determinisztikus Dijkstra algoritmus a legrövidebb út keresésére.
:param graph: Szomszédsági lista gráf reprezentáció.
:param start: A kezdő csúcs.
:return: A legrövidebb utak hossza a start csúcsból.
"""
distances = {node: float('infinity') for node in graph}
distances = 0
pq = # Prioritási sor: (távolság, csúcs)
while pq:
current_distance, current_node = heapq.heappop(pq)
if current_distance > distances:
continue
for neighbor, weight in graph:
distance = current_distance + weight
if distance < distances:
distances = distance
heapq.heappush(pq, (distance, neighbor))
return distances
# Példa gráf
graph = {
'A': ,
'B': ,
'C': ,
'D': ,
}
start = 'A'
result = dijkstra(graph, start)
print(f"Legrövidebb utak a {start} csúcsból:")
for node, distance in result.items():
print(f"{node}: {distance}")
Kimenet:
Legrövidebb utak a A csúcsból: A: 0 B: 1 C: 3 D: 4
A determinisztikus algoritmusok:
A fentebb bemutatott Python példák (lineáris keresés, buborékrendezés, Dijkstra algoritmus) demonstrálják, hogy hogyan működnek a determinisztikus algoritmusok a gyakorlatban.