Parcurgerea spațiului: BFS și DFS

Algoritmii de căutare sunt fundamentali în Inteligența Artificială. Ei explorează un spațiu de stări pentru a găsi o cale de la starea inițială la starea scop.

Concepte de bază

Spațiul de stări

Un spațiu de stări este definit de:

• Stare inițială: punctul de plecare
• Acțiuni: operațiile posibile din fiecare stare
• Model de tranziție: rezultatul aplicării unei acțiuni
• Test scop: verifică dacă am ajuns la soluție
• Cost cale (opțional): costul parcurgerii

Reprezentare ca graf

        A (start)
       / \
      B   C
     /|   |\
    D E   F G (scop)

Căutarea în lățime (BFS)

Breadth-First Search explorează nivelurile grafului pe rând, de la cel mai apropiat la cel mai îndepărtat.

Caracteristici

• Folosește o coadă (FIFO) pentru frontieră
• Găsește calea cea mai scurtă (în număr de pași)
• Complet: găsește soluția dacă există
• Optim: doar dacă toate costurile sunt egale

Algoritm

from collections import deque

def bfs(graf, start, scop):
    """
    Breadth-First Search.

    Args:
        graf: dicționar {nod: [vecini]}
        start: nodul de start
        scop: nodul țintă

    Returns:
        Lista nodurilor pe calea găsită sau None
    """
    # Coadă: (nod_curent, cale_până_aici)
    coada = deque([(start, [start])])
    vizitat = {start}

    while coada:
        nod, cale = coada.popleft()

        # Verifică dacă am ajuns la scop
        if nod == scop:
            return cale

        # Explorează vecinii
        for vecin in graf.get(nod, []):
            if vecin not in vizitat:
                vizitat.add(vecin)
                coada.append((vecin, cale + [vecin]))

    return None  # Nu s-a găsit cale

Exemplu de utilizare

graf = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F', 'G'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C'],
    'G': ['C']
}

cale = bfs(graf, 'A', 'G')
print(cale)  # ['A', 'C', 'G']

Vizualizarea execuției

Pas 1: Coada = [A]         Vizitat = {A}
Pas 2: Coada = [B, C]      Vizitat = {A, B, C}
Pas 3: Coada = [C, D, E]   Vizitat = {A, B, C, D, E}
Pas 4: Coada = [D, E, F, G] Vizitat = {A, B, C, D, E, F, G}
Pas 5: ... continuă până găsește G

---

Căutarea în adâncime (DFS)

Depth-First Search explorează cât mai adânc posibil pe o ramură înainte de a reveni.

Caracteristici

• Folosește o stivă (LIFO) sau recursivitate
• Nu garantează calea cea mai scurtă
• Complet: doar pentru grafuri finite (cu detecție de cicluri)
• Folosește mai puțină memorie decât BFS

Algoritm iterativ

def dfs_iterativ(graf, start, scop):
    """
    Depth-First Search (iterativ).

    Args:
        graf: dicționar {nod: [vecini]}
        start: nodul de start
        scop: nodul țintă

    Returns:
        Lista nodurilor pe calea găsită sau None
    """
    # Stivă: (nod_curent, cale_până_aici)
    stiva = [(start, [start])]
    vizitat = set()

    while stiva:
        nod, cale = stiva.pop()

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

        # Verifică dacă am ajuns la scop
        if nod == scop:
            return cale

        # Adaugă vecinii pe stivă (în ordine inversă pentru ordine corectă)
        for vecin in reversed(graf.get(nod, [])):
            if vecin not in vizitat:
                stiva.append((vecin, cale + [vecin]))

    return None

Algoritm recursiv

def dfs_recursiv(graf, start, scop, vizitat=None, cale=None):
    """
    Depth-First Search (recursiv).
    """
    if vizitat is None:
        vizitat = set()
    if cale is None:
        cale = []

    vizitat.add(start)
    cale = cale + [start]

    # Verifică dacă am ajuns la scop
    if start == scop:
        return cale

    # Explorează vecinii
    for vecin in graf.get(start, []):
        if vecin not in vizitat:
            rezultat = dfs_recursiv(graf, vecin, scop, vizitat, cale)
            if rezultat is not None:
                return rezultat

    return None

Exemplu de utilizare

graf = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F', 'G'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C'],
    'G': ['C']
}

cale = dfs_iterativ(graf, 'A', 'G')
print(cale)  # ['A', 'B', 'D', 'E', 'C', 'F', 'G'] sau altă cale

Vizualizarea execuției

Pas 1: Stiva = [A]         Vizitat = {A}
Pas 2: Stiva = [B, C]      Vizitat = {A}
       Pop C → Stiva = [B]  Vizitat = {A, C}
Pas 3: Stiva = [B, F, G]   Vizitat = {A, C}
       Pop G → GĂSIT!

---

Comparație BFS vs DFS

Caracteristică	BFS	DFS
Structură de date	Coadă (FIFO)	Stivă (LIFO)
Găsește calea minimă	Da	Nu
Complet	Da	Da (cu detecție cicluri)
Memorie	$O(b^d)$	$O(b \cdot d)$
Timp	$O(b^d)$	$O(b^d)$

Unde $b$ = factor de ramificare, $d$ = adâncimea soluției.

Când să folosim fiecare?

BFS:

• Când căutăm calea cea mai scurtă
• Când soluția este aproape de rădăcină
• Când avem suficientă memorie

DFS:

• Când memoria este limitată
• Când soluția este adâncă în arbore
• Pentru detectarea ciclurilor
• Pentru parcurgerea completă a grafului

---

Variante și extensii

DFS cu limită de adâncime

def dfs_limitat(graf, start, scop, limita):
    """DFS cu adâncime maximă."""
    return dfs_limitat_rec(graf, start, scop, limita, set(), [])

def dfs_limitat_rec(graf, nod, scop, limita, vizitat, cale):
    if nod == scop:
        return cale + [nod]
    if limita <= 0:
        return None

    vizitat.add(nod)
    for vecin in graf.get(nod, []):
        if vecin not in vizitat:
            rezultat = dfs_limitat_rec(graf, vecin, scop,
                                       limita - 1, vizitat, cale + [nod])
            if rezultat is not None:
                return rezultat
    vizitat.remove(nod)
    return None

Iterative Deepening DFS (IDDFS)

Combină avantajele BFS (optimalitate) cu cele ale DFS (memorie redusă).

def iddfs(graf, start, scop, max_adancime=100):
    """Iterative Deepening Depth-First Search."""
    for adancime in range(max_adancime):
        rezultat = dfs_limitat(graf, start, scop, adancime)
        if rezultat is not None:
            return rezultat
    return None

---

Aplicații practice

Labirint

def rezolva_labirint(labirint, start, scop):
    """
    Rezolvă un labirint folosind BFS.

    labirint: matrice 2D (0 = liber, 1 = zid)
    start, scop: tuple (linie, coloana)
    """
    linii, coloane = len(labirint), len(labirint[0])
    directii = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # dreapta, jos, stânga, sus

    coada = deque([(start, [start])])
    vizitat = {start}

    while coada:
        (l, c), cale = coada.popleft()

        if (l, c) == scop:
            return cale

        for dl, dc in directii:
            nl, nc = l + dl, c + dc
            if (0 <= nl < linii and 0 <= nc < coloane and
                labirint[nl][nc] == 0 and (nl, nc) not in vizitat):
                vizitat.add((nl, nc))
                coada.append(((nl, nc), cale + [(nl, nc)]))

    return None

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

cale = rezolva_labirint(labirint, (0, 0), (3, 3))
print(cale)  # [(0, 0), (0, 1), (1, 1), (2, 1), (2, 2), (2, 3), (3, 3)]

Verificarea conexității

def este_conex(graf):
    """Verifică dacă graful este conex folosind DFS."""
    if not graf:
        return True

    start = next(iter(graf))
    vizitat = set()

    def dfs(nod):
        vizitat.add(nod)
        for vecin in graf.get(nod, []):
            if vecin not in vizitat:
                dfs(vecin)

    dfs(start)
    return len(vizitat) == len(graf)

Detectarea ciclurilor

def are_ciclu(graf):
    """Detectează dacă graful are cicluri folosind DFS."""
    vizitat = set()
    in_stiva = set()

    def dfs(nod):
        vizitat.add(nod)
        in_stiva.add(nod)

        for vecin in graf.get(nod, []):
            if vecin not in vizitat:
                if dfs(vecin):
                    return True
            elif vecin in in_stiva:
                return True

        in_stiva.remove(nod)
        return False

    for nod in graf:
        if nod not in vizitat:
            if dfs(nod):
                return True
    return False

Sortare topologică

def sortare_topologica(graf):
    """Sortare topologică folosind DFS."""
    vizitat = set()
    rezultat = []

    def dfs(nod):
        vizitat.add(nod)
        for vecin in graf.get(nod, []):
            if vecin not in vizitat:
                dfs(vecin)
        rezultat.append(nod)

    for nod in graf:
        if nod not in vizitat:
            dfs(nod)

    return rezultat[::-1]