01. Blind search

Iterative deepening

E' una fusione tra depth first (nozione 4 pag 15r) e breadth first (nozione 2 pag15r).

funzionamento

Wikipedia spesso aiuta supponendo si avere il grafo seguente:

d1.jpg

si ha che si segue l'ordine. Prima si visita la radice, poi la radice ed i suoi figli, poi la radice, i figli ed i figli dei figli, seguendo la sequenza. In sostanza mano a mano vado più in profondità, quindi, limitandomi nella profondità, di volta in volta eseguo il depth first.
Il vantaggio è quello di usare poca memoria, visto che l'approccio è depth first, ma di limitare gli svantaggi del depth first con alberi sbilanciati o rami infiniti.
Lo svantaggio è che consumiamo molto tempo a riespandere nodi già visti (ma ciò ci salva in termini di memoria).

Costo spaziale: manteniamo in memoria al più $(B-1) \cdot K + 1$ nodi. Dove $(B-1)$ sono i figli generati di un nodo, tranne un figlio esplorato, K sono i livelli di profondità e +1 è il nodo corrente.
Costo temporale: nel caso in cui il goal sia al centro dell'ultimo livello

d2.jpg

si ha che fino al livello precedente vediamo tutti i nodi, ma ripetendo i passaggi! Cioè esploro tutti i nodi fino al livello 1, poi di nuovo tutti i nodi estendemi fino al livello 2, e così via. Se vedere tutti i nodi fino al livello i mi costa $\frac{B^{i+1}-1}{B-1}$, allora la somma di tutte queste esplorazioni "totali" mi determina il costo fino al livello precedente rispetto al goal (D-1). Dunque avrò che il costo totale è:

(1)
\begin{align} \sum_{i=0}^{D-1} \left ( \frac{B^{i+1}-1}{B-1} \right ) + \left ( D + \frac{B^{D+1}-1}{B-1} \right ) \cdot \frac{1}{2} \end{align}

Ora, io posso maggiorare ogni elemento della sommatoria con $\frac{B^{D+1}}{B-1}$ che è il valore nella parentesi (maggiorato di 1) del secondo termine, quindi alla fine conterei D+1 di questi termini (D dalla sommatoria e 1 dal secondo termine), quindi ho che il costo temporale ha questa limitazione:

(2)
\begin{align} \sum_{i=0}^{D-1} \left ( \frac{B^{i+1}-1}{B-1} \right ) + \left ( D + \frac{B^{D+1}-1}{B-1} \right ) \cdot \frac{1}{2} \leq \frac{(D+1) \cdot B^{D+1}}{2 \left ( B-1 \right ) } \end{align}

Il confronto con il depth first a livello temporale è ilseguente:

(3)
\begin{align} \frac{B+1}{B-1} = \frac{\mbox{it.deep.}}{\mbox{d.first}} \end{align}

Ovvero, man mano che B aumenta il divario è svantaggioso per l'iterative deepening (come si poteva intuire) ma non troppo.

Iterative broadening

Simile all'iterative deepening, ma procede con il breadth first piuttosto che con il depth first, funzionamento da vedere bene su internet (sembra non essere immediata la ricerca).

Random search

Si sceglie, andando in profondità, cosa visitare in modo casuale. Funziona discretamente in spazi di ricerca estesi con molti goal (dove costa molto poco fare una random search piuttosto che le ricerche che salvano in memoria molta roba).

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License