Il problem-solving Gianpiero Cabodi e Paolo Camurati Dip. Automatica e Informatica Politecnico di...

Il problem-solving

Gianpiero Cabodi e Paolo CamuratiDip. Automatica e Informatica

Politecnico di Torino

A.A. 2004/2005 14 Il problem-solving 2

SOSTANZE

Problema di ottimizzazione Trovare una serie (di costo minimo) di di N

elementi, uno per ogni fase di un processo industriale, non incompatibili tra loro.

L'elenco degli elementi, con il loro nome e le relative incompatibilità, viene letto da file.


Problema in dettaglioProcesso industriale per il trattamento dei materiali, composto da 10 fasi

In ogni fase viene utilizzata una sostanza particolare, scelta in un certo numero di sostanze

Ogni sostanza è caratterizzata da un determinato prezzo

Ogni sostanza può inoltre essere incompatibile con altre sostanze utilizzabili nel processo (in altre fasi), così che l'uso di una sostanza rende impossibile l'utilizzo di tutte le sostanze con essa incompatibili, in tutte le fasi del processo, precedenti e/o successive.


Problema in dettaglioIl programma

(ricerca) determina per ogni fase la sostanza da utilizzare, compatibile con quelle scelte in tutte le altre fasi

(ottimizzazione) è necessario minimizzare il costo del processo (somma dei costi delle sostanze selezionate).

Il programma legge da file le informazioni relative alle sostanze disponibili, al loro prezzo (espresso come intero inferiore a 1000), alla fase in cui sono utilizzabili, e alla lista delle eventuali incompatibilita'.


Formato file input La prima riga contiene il numero di sostanze

disponibili, sotto forma di un intero tra 1 e 100 per ogni sostanza vi sono nel file:

una riga contenente il nome della sostanza, il suo prezzo, la fase in cu può essere utilizzata, il numero di sostanze (tra quelle precedentemente riportate nel file) con cui e' incompatibile, nel formato'#'<nome> <prezzo> <fase> <numero di incompatibilità>

tante righe quante sono le sostanze incompatibili, in ognuna delle quali è riportato il nome della sostanza.


Algoritmo

Strategia: Ricerca Visitare (enumerare in modo

ricorsivo) tutte le possibili soluzioni. Per 10 fasi 10 chiamate ricorsive: la ricorsione di profondità i prova tutte le sostanze possibili per la fase i e attiva ricorsivamente il completamento delle fasi successive.

Ottimizzazione si mantengono soluzione corrente e soluzione migliore provvisoria. Ogni nuova soluzione viene confrontata con la migliore ed eventualmente la aggiorna (simile a ricerca di massimo/minimo)


Struttura datiOccorre prevedere strutture dati per:

Elenco delle sostanze, con fasi in cui utilizzarle e costo. Sono possibili più scelte:

elenco unico di sostanze oppure sottoinsiemi di sostanze per le singola fasi

Incompatibilità tra sostanze. Sono informazioni simili ad archi in un grafo, sono quindi possibili:

Rappresentazioni a matrice o liste delle adiacenze (incompatibilità)

Soluzioni (corrente e migliore) Due vettori o due liste


Informazioni su sostanze Elenco unificato (es. array di struct)

contenente tutte le sostanze Semplicità di lettura e di gestione L’enumerazione delle sostanze compatibili con

la fase i ha costo O(Ntot), con Ntot numero totale delle sostanze

Sostanze raggruppate in sottoinsiemi disgiunti (non è previsto il possibile uso di una sostanza in più fasi)

Difficoltà implementativa (es. array di array o array di liste)

L’enumerazione delle sostanze compatibili con la fase i ha costo O(Ni), con Ni numero delle sostanze dell’i-esimo sottoinsieme


Informazioni su sostanze

Soluzione intermedia: elenco unificato, ordinato per sottoinsiemi Lettura semplice da file Sorting per fase Le sostanze

appartenenti allo stesso sottoinsieme sono adiacenti nel vettore

I 10 sottoinsiemi sono facilmente identificabili mediante un array di indici


Grafo delle incompatibilità

Le incompatibilità sono un grafo: La matrice di adiacenza fornisce

test di incompatibilità O(1) tra due sostanze date Elenco delle incompatibilità, per una data

sostanze, di costo O(Ntot)

Le liste di adiacenza offrono (Ntot: lunghezza max. di lista di incompatibilità

test di incompatibilità O(Ntot) tra due sostanze date

Elenco delle incompatibilità, per una data sostanze, di costo O(Ntot)


Grafo delle incompatibilità: utilizzoDato un insieme di sostanze già selezionate (per le prime fasi)

percorrere solo quelle compatibili lista delle compatibilità: Soluzione migliore ma

difficile da realizzare (compatibilità con più sostanze, lista dinamica)

oppure Provare tutte quelle adatte alla fase corrente,

verificando la compatibilità con quelle già scelte

matrice di compatibilità/incompatibilità: doppio loop con test di compatibilità O(1).

Buon compromesso tra semplicità realizzativa e costo !


Il problema dei nomiProblema: passare da una sostanza alle informazioni relative (costo, fase, compatibilità/incompatibilità).

Se le informazioni sono in uno o più vettori, occorre associare a ogni sostanza un INDICE (es. intero tra 0 e Ntot)

Se una sostanza viene individuata per NOME, occorre un meccanismo di conversione NOME INDICE

Una soluzione efficiente consiste nell’identificare le sostanze mediante indice (anziché nome). L’algoritmo e le liste o matrice di incompatibilità si basano su indici (accesso diretto). Il passaggio al nome (O(1)) viene fatto solo quando necessario (es. per output).


Soluzione corrente/miglioreLe due soluzioni gestite (corrente e migliore) possono essere gestite come vettori o liste.

Vista la dimensione ridotta e predicibile (10) risulta più semplice gestire due vettori di indici (interi) alle sostanze selezionate.

Un insieme di sostanze per le prime i fasi viene identificato da un vettore caricato fino all’i-esima casella. Il backtrack è semplice (basta decrementare il numero di caselle occupate.


La soluzione proposta

Variabili statiche: minore modularità ma soluzione ad hoc semplice

Vettore di struct sostanza (non ordinato: soluzione più semplice)

Matrice (statica) delle incompatibilità Conversione nome-indice (ricerca

lineare in vettore) in fase di lettura Soluzioni corrente e migliore: array di

indici

sostanze.c

Il problem-solving Gianpiero Cabodi e Paolo Camurati Dip. Automatica e Informatica Politecnico di...

Documents

Transcript of Il problem-solving Gianpiero Cabodi e Paolo Camurati Dip. Automatica e Informatica Politecnico di...