Torna alla Home Page del corso     Torna alla pagina degli Elaborati     Precedente Successiva

ESEMPIO

Si supponga di dover confrontare i due piani della figura:

L'algoritmo prevede per prima cosa l'eliminazione delle azioni che appartenenti ad un solo piano: in questo caso C ed E e le rispettive istanze c¹₁, c¹₂ ed e²₁. Ne risultano i due piani seguenti, non ancora confrontabili per via delle istanze multiple:

Solamente le due istanze dell'azione A possono essere associate univocamente; pertanto la situazione associata al nodo 0 da cui si dirama l'albero di ricerca sara':

Al passo successivo, la ricerca prevede la generazione di due nodi figli ottenuti inserendo nei piani parziali le azioni D. In questo esempio, poiche' le relative istanze occupano posizioni identiche nei due nodi di primo livello, il costo risulta in entrambi i casi unitario a causa delle differenti relazioni tra le coppie di istanze <d,a>.

Espandendo ulteriormente il nodo 2 (l'ultimo generato), sono possibili due associazioni alternative per l'istanza b¹₁:

In entrambi i casi, una nuova relazione risulta essere differente tra i due piani parziali incrementando ulteriormente il costo. Avendo effettuato tutte le scelte possibili, la lista delle istanze ambigue risulta vuota e pertanto i nodi 3 e 4 rappresentano due obiettivi; tuttavia essi potrebbero non essere ottimali (col minor costo) in quanto esiste il nodo 1, non ancora espando e con costo inferiore.

In questo esempio, la ricerca A* deve necessariamente espandere tutto l'albero per verificare l'ottimalita' degli obiettivi, generando pertanto i nodi:

Dati i piani iniziali, sono stati trovati ben 4 obiettivi, tutti equivalenti e caratterizzati dal costo 2. Poiche' il costo di tutti i nodi trascura solamente le relazioni presenti nel nodo iniziale, ed esse si propagano invariate in tutti i nodi successori, il valore effettivo dell'indice rel e' pari al costo minimo finale trovato sommato al numero di relazioni differenti esistenti tra i piani del nodo 0, ed e' indipendente dall'obiettivo scelto.

Il valore normalizzato degli indici per l'esempio riportato risulta essere:

N₃'=5/11=0,45 (il 45% delle istanze e' assente nei piani parziali finali)

rel'=2/3=0,67 (il 67% delle relazioni e' diverso tra i piani parziali finali)

Indice complessivo = (1-N₃')(1-rel') = 0,18

L'indice complessivo puo' variare da 0 (piani completamente diversi) ad 1 (piani uguali). In questo caso, i piani iniziali risultano essere molto diversi.

Torna alla Home Page del corso     Torna alla pagina degli Elaborati     Precedente Successiva