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

Passi preliminare necessari per il confronto

Per poter confrontare i piani e' necessario associare ogni istanza del piano 1 con una corrispondente istanza del piano 2, rappresentanti entrambe la stessa azione. Poiche' non tutte le azioni appartengono ad ambedue i piani, alcune di esse devono essere rimosse prima di poter procedere. In questo modo si ottengono due sottopiani aventi tutte le azioni in comune, alcune delle quali presenti con piu' istanze (che danno luogo ad ambiguita'). Essendo interessati alla somiglianza tra piani, e' ragionevole richiedere che le associazioni scelte conducano al minor valore possibile per l'indice rel, in modo da determinare il massimo valore possibile per l'indice di confronto.

Il problema consiste quindi nell'estrarre dai piani completi originali due sottopiani, caratterizzati dal minor valore di rel, in cui le azioni non comuni siano rimosse e tutte le istanze siano associate.

Ricerca Euristica

La costruzione puo' essere vista come una ricerca in uno spazio in cui lo stato sia costituito da piani parziali derivabili da quelli iniziali. Ogni stato e' caratterizzato da due piani ridotti, le cui istanze sono reciprocamente ed univocamente associate e da una lista di istanze ancora ambigue (da associare o eliminare). Tale lista assume la forma (per i piani di figura):

( <(b¹₁, b¹₂); b²₁ > ; <(d¹₁, d¹₂); d²₁> )

elencando tutte le possibili istanze del piano 1 con le possibili istanze associabili del piano 2.

Lo stato iniziale e' costituito dai due sottopiani composti dalle sole istanze banalmente associabili, ossia quelle che appaiono una sola volta in entrambi i piani.

Lo stato finale consiste di due sottopiani in cui tutte le ambiguita' siano state risolte ed avente il costo minimo.

Utilizzando l'algoritmo di ricerca A*, che garantisce sotto opportune ipotesi l'esplorazione del minor numero di stati, e' possibile generare un albero di ricerca rappresentante la costruzione progressiva della soluzione. Facendo coincidere il nodo iniziale con lo stato iniziale, i successori sono derivati inserendo in entrambi i piani una coppia di istanze selezionate tra quelle ancora ambigue.

All'aumentare della profondita' dell'albero, i piani ridotti associati a ciascun nodo aumentano di dimensione (di un'istanza ad ogni livello) e corrispondentemente la lista delle istanze ambigue si riduce. Analogamente, essendo il numero di relazioni strettamente crescente, ad ogni passo il numero di relazioni differenti esistenti tra i due sottopiani risulta monotono crescente, anche se non strettamente; infatti ogni nuovo inserimento non ha alcun effetto sulle relazioni preesistenti.

Il numero di relazioni differenti risulta essere quindi una buona stima del costo del nodo e garantisce la convergenza della ricerca A* verso la soluzione ottima; inoltre per quanto detto il costo di un nodo e' pari al costo del precedente sommato al numero di relazioni violate dalle sole nuove istanze inserite.

Essendo la lista delle possibili associazioni finita, il numero degli stati possibili risulta limitato, cosi come la profondita' massima dell'albero, alla quale si trovano tutti gli obiettivi, ottimali o meno. Pertanto la profondita' di un nodo risulta essere inversamente proporzionale alla sua distanza dall'obiettivo. Per garantire che la ricerca esplori il minor numero di nodi possibile, e' sufficiente espandere a parita' di costo i nodi piu' profondi.

Il numero di nodi esplorati puo' essere ulteriormente ridotto eseguendo le scelte piu' vincolanti all'inizio della ricerca, in modo da avere il minor fattore di ramificazione all'inizio. In questo modo, la ricerca A* taglierà porzioni dell'albero piu' numerose.

L'esempio finale chiarisce l'algoritmo utilizzato e la generazione dell'albero.

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