Wikiszótár

heurisztika

Magyar

Kiejtés

  • IPA: [ ˈhɛuristikɒ]

Főnév

heurisztika

  1. (matematika) A heurisztika az új igazságok módszeres felfedezésének művészete. Az a folyamat, amelynek során nem szigorúan szabatos logikai következtetéssel jutunk el a premisszáktól a konklúzióig, ám az eredmény helyes lesz. Másképpen: az egyértelmű algoritmusok helyett próbálkozásokkal, korábban megszerzett tapasztalatok felhasználásával működő feladatmegoldási módszer. A mesterségesintelligencia-kutatásban a szónak ennél szűkebb, precízen definiálható értelme van.

A heurisztika olyan problémamegoldási vagy döntéshozási módszer, amely az optimális megoldás helyett gyors és elégséges (szuboptimális) megoldást kínál. Pythonban különböző heurisztikus algoritmusokat használhatunk például keresési problémák, optimalizálás vagy mesterséges intelligencia alkalmazásokban. Az alábbiakban néhány példa található:


1. Heurisztikus keresés: A* algoritmus

Az A* algoritmus egy grafikus keresési algoritmus, amely a legjobb utat találja meg egy gráfban. Heurisztikát használ az útvonal optimalizálásához.

Példa:

import heapq

def a_star_search(graph, start, goal, heuristic):
    open_set = []
    heapq.heappush(open_set, (0, start))
    came_from = {}
    g_score = {node: float('inf') for node in graph}
    g_score[start] = 0
    f_score = {node: float('inf') for node in graph}
    f_score[start] = heuristic(start, goal)

    while open_set:
        _, current = heapq.heappop(open_set)

        if current == goal:
            path = []
            while current in came_from:
                path.append(current)
                current = came_from[current]
            return path[::-1]

        for neighbor, cost in graph[current].items():
            tentative_g_score = g_score[current] + cost
            if tentative_g_score < g_score[neighbor]:
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g_score
                f_score[neighbor] = g_score[neighbor] + heuristic(neighbor, goal)
                heapq.heappush(open_set, (f_score[neighbor], neighbor))

    return None

# Gráf definiálása
graph = {
    'A': {'B': 1, 'C': 3},
    'B': {'A': 1, 'D': 1, 'E': 5},
    'C': {'A': 3, 'F': 2},
    'D': {'B': 1},
    'E': {'B': 5, 'F': 2},
    'F': {'C': 2, 'E': 2}
}

# Heurisztika (példa: egyenes vonalú távolságok)
def heuristic(node, goal):
    heuristics = {
        'A': 6, 'B': 4, 'C': 4,
        'D': 2, 'E': 2, 'F': 0
    }
    return heuristics[node]

# Keresés A* algoritmussal
path = a_star_search(graph, 'A', 'F', heuristic)
print("Optimális útvonal:", path)

2. Lokális keresés: Hill Climbing

A Hill Climbing algoritmus egy lokális optimalizálási technika, amely egy kezdő állapotból indul, és a legjobb szomszédot választja.

Példa:

import random

def hill_climbing(problem, initial_state):
    current_state = initial_state
    while True:
        neighbors = problem['neighbors'](current_state)
        if not neighbors:
            break
        next_state = max(neighbors, key=problem['fitness'])
        if problem['fitness'](next_state) <= problem['fitness'](current_state):
            break
        current_state = next_state
    return current_state

# Példa probléma: maximális érték keresése
problem = {
    'fitness': lambda x: -((x - 3) ** 2) + 9,  # Függvény: parabola
    'neighbors': lambda x: [x - 1, x + 1] if 0 <= x <= 6 else []
}

# Kezdő állapot
initial_state = random.randint(0, 6)
solution = hill_climbing(problem, initial_state)
print("Megoldás:", solution)

3. Genetikus algoritmus

A genetikus algoritmus egy evolúciós heurisztika, amely az evolúciós biológia inspirációján alapul.

Példa:

import random

def genetic_algorithm(population, fitness_func, mutate_func, crossover_func, generations=100):
    for _ in range(generations):
        population = sorted(population, key=fitness_func, reverse=True)
        next_gen = population[:2]  # Legjobb két egyed
        for _ in range(len(population) // 2 - 1):
            parents = random.sample(population[:10], 2)
            child = crossover_func(*parents)
            next_gen.append(mutate_func(child))
        population = next_gen
    return max(population, key=fitness_func)

# Példa probléma: maximális szám keresése
fitness_func = lambda x: -((x - 50) ** 2) + 2500
mutate_func = lambda x: x + random.randint(-5, 5)
crossover_func = lambda p1, p2: (p1 + p2) // 2

# Kezdő populáció
population = [random.randint(0, 100) for _ in range(20)]
solution = genetic_algorithm(population, fitness_func, mutate_func, crossover_func)
print("Megoldás:", solution)

Ezek az algoritmusok egyszerű példák a heurisztikus megközelítések használatára Pythonban. További testreszabásokkal komplexebb problémák megoldására is alkalmasak.

Fordítások

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=heurisztika&oldid=3480677”
  NODES
orte 1