Newsgroup: it.scienza.informatica
Titolo: Percorsi di norma massima

Per motivi di ricerca  (non in campo informatico, ma aerodinamico), sto
lavorando alla scrittura di un algoritmo che, data una matrice A nxm di
reali positivi, fornisca un percorso P fra gli elementi della matrice stessa
soggetto a vari vincoli. Per "percorso" intendo dire che parto da un
elemento a_ij di A, e mi posso spostare solo in uno fra i quattro elementi
di A immediatamente adiacenti ad a_ij ( tre elementi se sono sui bordi della
matrice, due se sono in uno dei 4 spigoli).
L' elemento iniziale di P non è fissato, ma bisogna rispettare le seguenti
regole:
1) dev' essere aperto ( elementi finale ed iniziale distinti)  e semplice
 niente nodi, un elemento di A vi può comparire al + una volta, per cui non
si può neanche tornare indietro, ergo, tranne che per la prima mossa, gli
elementi di A fra cui scegliere, ad ogni passo, in realtà sono 3,2,1 nei
vari casi di interno, bordo, spigolo);
2) deve avere lunghezza prefissata r ( ovviamente minore di nxm);
3)  nessuno dei segmenti orizzontali o verticali che lo compongono può
essere affiancato da un altrto segmento orizzontale o verticale, cioè P non
deve mai ripassare "di fianco" a se stesso, insomma se a_12, a_13 ed a_23
fanno parte del percorso, allora a_13 non può farne parte ( se ve lo
disegnate capite meglio );
4) - fra tutti i percorsi che soddisfano 1), 2) 3), P deve essere a norma 1
massima, cioè la somma degli elementi di A toccati da P dev' essere la
massima possibile, dati 1), 2), 3).
Il problema evidentemente non ha soluzione per ogni r ed ogni A, nel qual
caso lo posso "rilassare" diminuendo il valore di r, preferibilmente non
sotto min{n,m}: inoltre mi interessa anche il problema, più semplice, in cui
si parte dal massimo valore di A e ci si muove scartando, fra i 4 valori di
A che circondano a_max, quelli che non permettono di soddisfare 1), 2),3),
dopodichè fra quelli restanti scelgo quello di valore massimo. E così via
proseguendo, mi sposto sempre sul più grande valore adiacente consentitomi
da 1),2),3): è chiaro che in questo caso non soddisfo 4), cioè di solito il
percorso dei massimi (locali) non è il percorso massimo.
Se avete materiale, risultati teorici e/o  referenze bibliografiche a
riguardo, oppure semplicemente vi va di darmi qualche dritta , ve ne sarei
molto grato, dato che mi occupo di tutt'altro, ma adesso ho necessità di
risolvere tale problema (tenete però conto che non sono un ingegnere
informatico, nè un matematico indirizzo informatico, nè un laureato in
Scienze
dell' Informazione, ecc. e neanche un brillante autodidatta (ehm..)per cui
se  ci date subito dentro col programma del corso di Ingegneria del
Software, poi non posso seguirvi ) . Ringraziandovi anticipatamente vi
saluto,
Andrea

 regole:
Scusate, modificando il messaggio più volte ne ho alterato il senso: il
periodo corretto era "L' elemento di iniziale di P non è fissato, ma P
stesso deve rispettare le seguenti regole:" . Vi saluto di nuovo,
Andrea

 Andrea
di niente, Diego

Ciao,
e' da un bel po' che hai fatto questa richiesta, ma visto che la mole di 
messaggi del ng non e' elevata, e la questione interessa anche un'altra 
persona, provo a darti una soluzione.
Un modo per risolvere il tuo problema e' quello di ricorrere alla 
programmazione matematica.
In pratica si imposta un problema nella forma "massimizzare 
(minimizzare) cx sotto il vincolo Ax <= b ", dove b e c sono vettori 
dati, A una matrice data e x il vettore di valori da trovare ( alcuni 
dei quali eventualmente interi ). Se hai seguito un corso di Ricerca 
Operativa penso tu abbia capito dove voglio andare a parare.
Si tratta quindi di risolvere due questioni: trovare una formulazione 
adatta ( trasformare il tuo problema in uno di questo tipo ) e trovare 
una libreria che ti risolva questi tipi di problemi :-).
Per la formulazione non dovrebbero esserci problemi : possiamo vedere la 
matrice come un grafo in cui i nodi sono gli elementi della matrice e 
gli archi un cammino tra due caselle, e di solito per i problemi su 
grafi non ci sono grossi problemi a trovare una formulazione.
Le variabili su cui possiamo lavorare sono i cammini tra una casella e 
l'altra e quindi il nostro vettore x sara' un vettore che rappresenta la 
scelta o meno di un arco. Se la nostra matrice ha dimensione n x m 
allora il nostro vettore x avra' n*(m-1) + m*(n-1) coordinate: per 
ognuna il valore 0 indica che non scegliamo un dato arco, il valore 1 
che lo scegliamo.
Ora dobbiamo scrivere tutti i vincoli del problema in forma di equazioni 
lineari nelle x(i).
Dobbiamo imporre che il circuito sia aperto(vincolo 1).  Un modo pratico 
per fare questo e' aggiungere una casella 'virtuale' che sia 'adiacente' 
a tutte le caselle della matrice, e imporre che il circuito passi 
comunque  per questa nuova casella ( in questo caso allora la lunghezza 
del circuito aumentera' ad r+2  ).
Questo si traduce nell'imporre che la somma di tutte le x(i) che 
corrispondono ad un cammino che esce dalla casella 'virtuale' sia due.
Ad esempio dobbiamo imporre (vincolo 2) che il cammino abbia lunghezza r.
Questo puo' essere facilmente imposto imponendo che la somma degli 
elementi di x sia uguale a r+2.
Ora tocca al vincolo (3). Per questo non sono riuscito a trovare una 
soluzione consistente in un solo vincolo: ore per ogni possibile coppia 
di cammini adiacenti dobbiamo imporre che la somma delle coordinate ad 
esse relative sia minore o uguale ad uno ( al piu' uno venga scelto ).
Sono quindi parecchi vincoli, dovrebbero essere ((m-1)*(n-1))^2.
I coefficienti di queste disuguaglianze ( possiamo riscrivere 
l'uguaglianza come due disuguaglianze se necessario ) andranno a 
costituire la matrice A, e le costanti ( ad esempio r+2 del primo 
vincolo ) i coefficienti del vettore b.
Ora non ci resta che scegliere i coefficienti del vettore c in modo che 
cx ci dia la norma del percorso. Visto che massimizziamo tra le 
soluzioni valide, possiamo dare ad ogni arco meta' della somma delle 
norme delle due caselle che collega. Avendo un arco entrante e uno 
uscente per ogni casella scelta ( e qui l'aggiunta scelta della casella 
virtuale e' fondamentale ) la somma totale sugli archi,dara' la somma 
dei valore delle caselle. Per gli archi che collegano la casella 
virtuale con le altre bastera' dare meta' della norma dell'altra casella.
Il secondo problema e' risolvere questo problema.
Come hai visto la quantita di vincoli e' esuberante, e cosi' di 
conseguenza la matrice A risultante ( dovrebbe avere un numero di 
elementi nell'ordine di n^3 * m^3 ). Senza contare che le variabili in 
gioco sono intere ( in particolare binarie ).Per risolverla la soluzione 
migliore e' quindi quella di ricorrere ad una libreria apposita per 
questi tipi di problemi. In pratica dovresti ottenere buoni risultati 
visto che queste librerie di solito utilizzano matrici sparse ( la 
maggior parte delle caselle di A avra' valore 0 ) e algoritmi con buoni 
risultati nei casi real-life. Le migliori di queste purtroppo sono a 
pagamento, ma ce ne sono anche di gratutite in circolazione ( che 
comunque non ho provato ).
Come vedi in fondo non c'e' molta informatica, piu' che altro algebra 
lineare.
Ho cercato di essere il piu' chiaro possibile ( a volte magari 
dilungandomi anche troppo ! =D ), non esitare comunque a chiedermi 
chiarimenti.
Marco

Ovviamente non potevo non commettere qualche errore.
Non abbiamo imposto il vincolo piu' importante, e cioe' che gli archi 
che scegliamo devono costituire un circuito, ovvero che per ogni 
elemento della matrice abbiamo due cammini che lo interessano o nessuno.
Tradotto in disuguaglianze questo vuol dire che per ogni elemento j 
della matrice abbiamo che ( chiamando v il vettore che vale 1 in 
corrispondenza di un arco che interessa quell'elemento e 0 viceversa )
va = 2*y(j)
dove a e' quella parte del vettore x che indica la presenza o meno degli 
archi e y(j) una variabile ausiliaria ( e quindi un'altra variabili che 
va ad aggiungersi al vettore x ) che vincoliamo a valere 0 o 1 e che in 
pratica serve per effettuare un 'o' disgiuntivo: o abbiamo archi per 
quell'elemeno o nessuno.
Sperando di non dover correggere altri errori,
Marco

 Marco
Beh, io pensavo semplicemente, come descritto nei vincoli, che ormai la
soluzione + semplice fosse data da un algoritmo greedy... del resto nn puoi
scegliere il punto di partenza, non puoi avere una lunghezza di percorso
maggiore di (r), non puoi muoverti in diagonale, non puoi passare accanto a
un elemento già toccato... mi è venuta in mente solo la scena di un
paracadutista che cade in mezzo a una foresta (ai bordi) e deve percorrere
tot passi raccogliendo + valori possibile. L'algoritmo greedy non è ottimo
in questi casi (potrebbe farti sbagliare strada alla prima scelta) ma in
media è un buon algoritmo, no?
Comunque sono sempre alle prime armi :-)
Buone feste
Diego

 Diego
Ci avevo pensato anche io, pero' a priori non penso si possa dire se la 
soluzione greedy sia abbastanza buona. Visto che la scelta del cammino 
e' abbastanza vincolata, la scelta di una casella con valore basso 
all'inizio puo' costringere poi a scegliere un percorso con molte altre 
caselle di alto valore. Soprattutto se le caselle migliori sono 
adiacenti tra loro ( o in diagonale ) , per scegliere una casella buona 
magari mi impedisco di sceglierne due altrettanto buone.
L'altra alternativa che mi e' venuta in mente e' quella della 
programmazione dinamica, ma penso che sarebbe troppo dispendioso con 
grandi matrici.
Marco