OKPEDIA CSP

Ottimizzazione dei vincoli

L'ottimizzazione dei vincoli è un insieme di tecniche e di metodi della programmazione lineare e della ricerca operativa, finalizzati a ottimizzare e/o semplificare un sistema matematico CSP. Un problema di ottimizzazione dei vincoli è conosciuto anche con l'acronimo COP ( Constraint Optimization Problem ). In tale ambito occupano una grande importanza l'analisi della consistenza locale ( nodo, arco, cammino ), la propagazione dei vincoli e l'eliminazione dei vincoli.

  • Consistenza locale. La consistenza locale è una condizione che si verifica quando ogni variabile ( nodo ) del sistema matematico ( rete ) soddisfa i vincoli unari, binari e n-ari rispetto alle altre variabili.
  • Propagazione dei vincoli. La propagazione dei vincoli è un tipo di inferenza sul sistema matematico che consente di ridurre i domini delle variabili ( campo di variazione ) facendo propagare gli effetti della riduzione del dominio di una variabile indipendente nel dominio delle variabili dipendenti.
  • Eliminazione dei vincoli unari. Un sistema matematico è caratterizzato da variabili e da vincoli. In alcuni casi è possibile eliminare i vincoli unari del sistema integrandoli nel campo di variazione dei valori delle variabili ( dominio ) o, quando possibile, accorpando tra loro i vincoli unari in vincoli globali. A parità di risultato, questa analisi consente di ottenere una semplificazione e ottimizzazione del sistema matematico, agevolando le successive operazioni di ricerca e/o di elaborazione degli algoritmi CSP.
  • Semplificazione dei vincoli. Un problema complesso composto da variabili e vincoli può essere semplificato riducendo il grafo dei vincoli a una struttura lineare o a una struttura ad albero. Ciò può essere realizzato separando un sottoinsieme delle variabili da tutte le altre ( insieme di taglio condizionato ) oppure raggruppando le variabili in sottoproblemi vincolati ( soddisfacimento dei vincoli distribuiti ).

Gli algoritmi di ottimizzazione dei vincoli sono eseguiti in una fase preliminare dell'elaborazione dei dati, ossia sono eseguiti prima dell'algoritmo di ricerca vero e proprio. Ciò consente di ridurre l'insieme dei valori possibili delle variabili da utilizzare nel processo di assegnazione, riducendo il tempo di elaborazione della fase di ricerca.

OTTIMIZZAZIONE DEI VINCOLI

Tempo di esecuzione della fase di ottimizzazione preliminare. In alcuni casi, la fase preliminare di ottimizzazione potrebbe allungare notevolmente il tempo di elaborazione. Ad esempio, quando l'obiettivo della ricerca è trovare la prima soluzione accettabile al problema nel minore tempo possibile, la fase preliminare di ottimizzazione dei vincoli potrebbe allungare eccessivamente il tempo di elaborazione complessivo ( fase preliminare + fase di ricerca ). L'algoritmo potrebbe trovare la soluzione migliore, restituendo però il risultato quando non è più utile ( inefficacia dell'algoritmo ). Ad esempio, in un sistema di guida automatica, l'algoritmo potrebbe decidere di frenare quando il veicolo è già caduto in un burrone, ecc. Viceversa, se l'obiettivo della ricerca è trovare la migliore soluzione possibile a un problema, la durata della fase preliminare di ottimizzazione non incide in alcun modo sull'efficacia dell'algoritmo. Ad esempio, la fase preliminare di ottimizzazione è molto utile per alimentare la tabella di conoscenza di un sistema esperto.

Ricerca con inferenza in avanti. La ricerca con inferenza in avanti è una tecnica di propagazione dei vincoli online. Mentre l'analisi di consistenza locale e dalla propagazione dei vincoli sono elaborate sull'intero albero di ricerca prima del processo di ricerca vero e proprio, la ricerca con inferenza in avanti è elaborata durante il processo di ricerca stesso, in ogni singola sottoramificazione. Ciò consente di eliminare il tempo di esecuzione della fase preliminare di ottimizzazione dei vincoli. L'ottimizzazione dei vincoli è integrata nella ricerca stessa tramite un processo di potatura logica online. L'efficienza del processo di ricerca in avanti può essere ulteriormente aumentata utilizzando le tecniche di ricerca backjumping e nogood ( apprendimento ).

https://www.okpedia.it/ottimizzazione_dei_vincoli


Segnala un errore o invia un suggerimento per migliorare la pagina


Constraint Satisfaction Problem


FacebookTwitterLinkedinLinkedin