Algoritmul A*

A* (A-star) este unul dintre cei mai populari algoritmi de căutare informată. Combină avantajele căutării uniforme (Dijkstra) cu euristici pentru a găsi eficient calea optimă.

Concepte de bază

Funcția de evaluare

A* folosește funcția:

$$f(n) = g(n) + h(n)$$

Unde:

• $f(n)$ = costul total estimat al căii prin nodul $n$
• $g(n)$ = costul real de la start până la nodul $n$
• $h(n)$ = euristica - costul estimat de la $n$ la scop

Euristica

O euristică $h(n)$ este admisibilă dacă nu supraestimează niciodată costul real:

$$h(n) \leq h^*(n)$$

unde $h^*(n)$ este costul real până la scop.

O euristică este consistentă (monotonă) dacă:

$$h(n) \leq cost(n, n') + h(n')$$

pentru orice succesor $n'$ al lui $n$.

Algoritm

import heapq

def a_star(graf, start, scop, h):
    """
    Algoritmul A*.

    Args:
        graf: dicționar {nod: [(vecin, cost), ...]}
        start: nodul de start
        scop: nodul țintă
        h: funcția euristică h(nod) -> cost estimat

    Returns:
        (cale, cost) sau (None, inf)
    """
    # Priority queue: (f, g, nod, cale)
    heap = [(h(start), 0, start, [start])]
    vizitat = {}  # nod -> cel mai mic g cunoscut

    while heap:
        f, g, nod, cale = heapq.heappop(heap)

        # Dacă am ajuns la scop
        if nod == scop:
            return cale, g

        # Skip dacă am vizitat cu cost mai mic
        if nod in vizitat and vizitat[nod] <= g:
            continue
        vizitat[nod] = g

        # Explorează vecinii
        for vecin, cost in graf.get(nod, []):
            g_nou = g + cost
            f_nou = g_nou + h(vecin)

            if vecin not in vizitat or vizitat[vecin] > g_nou:
                heapq.heappush(heap, (f_nou, g_nou, vecin, cale + [vecin]))

    return None, float('inf')

Euristici comune

Distanța Manhattan

Pentru grile unde ne putem deplasa doar ortogonal (sus, jos, stânga, dreapta).

$$h(n) = |x_n - x_{scop}| + |y_n - y_{scop}|$$

def manhattan(nod, scop):
    return abs(nod[0] - scop[0]) + abs(nod[1] - scop[1])

Distanța Euclidiană

Pentru deplasare în orice direcție.

$$h(n) = \sqrt{(x_n - x_{scop})^2 + (y_n - y_{scop})^2}$$

import math

def euclidiana(nod, scop):
    return math.sqrt((nod[0] - scop[0])**2 + (nod[1] - scop[1])**2)

Distanța Chebyshev (diagonală)

Pentru grile cu mișcare diagonală permisă.

$$h(n) = max(|x_n - x_{scop}|, |y_n - y_{scop}|)$$

def chebyshev(nod, scop):
    return max(abs(nod[0] - scop[0]), abs(nod[1] - scop[1]))

Distanța octilă

Pentru grile unde mișcarea diagonală costă $\sqrt{2}$.

def octila(nod, scop):
    dx = abs(nod[0] - scop[0])
    dy = abs(nod[1] - scop[1])
    return dx + dy + (math.sqrt(2) - 2) * min(dx, dy)

Exemplu: Navigare pe grilă

import heapq
import math

def a_star_grila(grila, start, scop):
    """
    A* pe o grilă 2D.

    grila: matrice 2D (0 = liber, 1 = obstacol)
    start, scop: tuple (linie, coloana)
    """
    linii, coloane = len(grila), len(grila[0])

    # Direcții: sus, jos, stânga, dreapta
    directii = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    def h(nod):
        return manhattan(nod, scop)

    def vecini(nod):
        l, c = nod
        rezultat = []
        for dl, dc in directii:
            nl, nc = l + dl, c + dc
            if 0 <= nl < linii and 0 <= nc < coloane and grila[nl][nc] == 0:
                rezultat.append(((nl, nc), 1))  # cost 1 per pas
        return rezultat

    # Priority queue: (f, g, nod, cale)
    heap = [(h(start), 0, start, [start])]
    vizitat = {}

    while heap:
        f, g, nod, cale = heapq.heappop(heap)

        if nod == scop:
            return cale, g

        if nod in vizitat:
            continue
        vizitat[nod] = g

        for vecin, cost in vecini(nod):
            if vecin not in vizitat:
                g_nou = g + cost
                f_nou = g_nou + h(vecin)
                heapq.heappush(heap, (f_nou, g_nou, vecin, cale + [vecin]))

    return None, float('inf')

# Exemplu
grila = [
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 0, 0, 0],
    [0, 0, 0, 0, 0]
]

cale, cost = a_star_grila(grila, (0, 0), (4, 4))
print(f"Cale: {cale}")
print(f"Cost: {cost}")

Comparație cu alți algoritmi

Algoritm	Complet	Optim	Timp	Spațiu
BFS	Da	Da*	$O(b^d)$	$O(b^d)$
DFS	Nu	Nu	$O(b^m)$	$O(bm)$
Dijkstra	Da	Da	$O(b^d)$	$O(b^d)$
A*	Da	Da**	$O(b^d)$	$O(b^d)$

* BFS optim doar pentru costuri uniforme * A optim cu euristică admisibilă

Avantajele A*

• Optim: găsește întotdeauna calea cu cost minim (cu euristică admisibilă)
• Eficient: explorează mai puține noduri decât Dijkstra
• Flexibil: poate fi adaptat cu diferite euristici

Variante ale A*

Weighted A*

Folosește $f(n) = g(n) + w \cdot h(n)$ cu $w > 1$ pentru viteză în detrimentul optimalității.

def weighted_a_star(graf, start, scop, h, w=1.5):
    heap = [(w * h(start), 0, start, [start])]
    vizitat = {}

    while heap:
        _, g, nod, cale = heapq.heappop(heap)

        if nod == scop:
            return cale, g

        if nod in vizitat:
            continue
        vizitat[nod] = g

        for vecin, cost in graf.get(nod, []):
            if vecin not in vizitat:
                g_nou = g + cost
                f_nou = g_nou + w * h(vecin)
                heapq.heappush(heap, (f_nou, g_nou, vecin, cale + [vecin]))

    return None, float('inf')

IDA (Iterative Deepening A)

Economisește memorie prin căutare iterativă.

def ida_star(graf, start, scop, h):
    """IDA* - A* cu memorie redusă."""

    def search(cale, g, threshold):
        nod = cale[-1]
        f = g + h(nod)

        if f > threshold:
            return f, None
        if nod == scop:
            return f, cale

        minim = float('inf')
        for vecin, cost in graf.get(nod, []):
            if vecin not in cale:
                cale.append(vecin)
                t, rezultat = search(cale, g + cost, threshold)
                if rezultat is not None:
                    return t, rezultat
                minim = min(minim, t)
                cale.pop()

        return minim, None

    threshold = h(start)
    cale = [start]

    while True:
        t, rezultat = search(cale, 0, threshold)
        if rezultat is not None:
            return rezultat
        if t == float('inf'):
            return None
        threshold = t

Exemplu: Puzzle 8

import heapq

def puzzle_8():
    """Rezolvă puzzle-ul cu 8 piese folosind A*."""

    scop = ((1, 2, 3), (4, 5, 6), (7, 8, 0))

    def h_manhattan(stare):
        """Suma distanțelor Manhattan pentru fiecare piesă."""
        dist = 0
        for i in range(3):
            for j in range(3):
                val = stare[i][j]
                if val != 0:
                    goal_i, goal_j = (val - 1) // 3, (val - 1) % 3
                    dist += abs(i - goal_i) + abs(j - goal_j)
        return dist

    def gaseste_zero(stare):
        for i in range(3):
            for j in range(3):
                if stare[i][j] == 0:
                    return i, j

    def vecini(stare):
        zi, zj = gaseste_zero(stare)
        rezultat = []
        for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            ni, nj = zi + di, zj + dj
            if 0 <= ni < 3 and 0 <= nj < 3:
                # Creează stare nouă prin interschimbare
                lista = [list(rand) for rand in stare]
                lista[zi][zj], lista[ni][nj] = lista[ni][nj], lista[zi][zj]
                noua_stare = tuple(tuple(rand) for rand in lista)
                rezultat.append((noua_stare, 1))
        return rezultat

    def rezolva(start):
        heap = [(h_manhattan(start), 0, start, [start])]
        vizitat = set()

        while heap:
            f, g, stare, cale = heapq.heappop(heap)

            if stare == scop:
                return cale

            if stare in vizitat:
                continue
            vizitat.add(stare)

            for vecin, cost in vecini(stare):
                if vecin not in vizitat:
                    g_nou = g + cost
                    f_nou = g_nou + h_manhattan(vecin)
                    heapq.heappush(heap, (f_nou, g_nou, vecin, cale + [vecin]))

        return None

    # Stare inițială
    start = ((1, 2, 3), (4, 0, 6), (7, 5, 8))
    solutie = rezolva(start)

    print(f"Număr de pași: {len(solutie) - 1}")
    for pas in solutie:
        for rand in pas:
            print(rand)
        print()

puzzle_8()

Proprietăți importante

Eficiența euristicii

O euristică mai bună (mai aproape de costul real) duce la explorarea mai puținor noduri:

$$h_1(n) \leq h_2(n) \leq h^*(n)$$

$h_2$ domină $h_1$ și va explora mai puține noduri.

Combinarea euristicilor

def h_combinat(nod, scop, euristici):
    """Combină mai multe euristici luând maximul."""
    return max(h(nod, scop) for h in euristici)

Relaxare

Pentru a crea euristici admisibile, relaxăm problema:

• Puzzle 8: Permitem oricărei piese să se miște oriunde → distanța Manhattan
• Călătorie: Ignorăm obstacolele → distanța în linie dreaptă