Newsgroup: it.hobby.enigmi
Titolo: posizionare le locandine di un cinema

posizionare le locandine di un cinema
forse aiuta:
http://www.clacsrl.it/rapu/img.jpg
...non cerco qualcuno che lo risolva ma qualcuno che mi indichi la
strada da percorrere...
E' complicato ma immaginate di avere a che fare con le locandine di
un cinema. Ci sono locandine grandi e piccole.
C'e' una struttura che puo' contenere 4 locandine grandi e al massimo
8 locandine piccole.
Ho una tabella di questo tipo:
ID titolo	 vincolataalbox	tipobox	tipo	colore
1 MARIO       11               2           mostra	#CCCCCC
2 LUCA	        22               1           mostra	#99FF99
3 PAOLO      32               	mostra	#FF0000
4 ENZO	                                  	evento	#CC66FF
5 GIANNI                                      evento	#C2622F
Ho una pagina che dovete immaginare divisa in 4 contenitori.
Ogni contenitore contiene uno o due layer.
Il numero massimo di layer e' 8.
Questi 8 layer si chiamano:
11
12
21
22
31
32
41
42
Ogni riga della tabella e' un layer.
L'altezza di un layer e' definita dal campo tipobox.
Se tipobox=1 allora altezza=105px
Se tipobox=2 allora altezza=210px
La posizione di un layer puo' essere vincolata ad un contenitore,
specificando l'attributo vincolataalbox.
Posso lasciare liberi i campi 
vincolataalbox e tipobox
ovviamente il programma deve riempire in maniera "intelligente" lo
spazio libero.
Problema.
che logica devo usare per posizionare le locandine ?
Ho pensato questo:
1)uso un vettore di 8 elementi per tenere traccia degli spazi occupati
2)colloco prima i layer vincolati.
3)ogni volta che posiziono un layer vincolato se ne conosco il tipo
(grande o piccolo)
 "brucio" le posizioni occupate da quel layer sul vettore.
 
 ...e qui mi sono fermato perche' non so andare avanti...
l'ID=3 lo potrei posizionare su tipobox grande o piccolo
grande nel caso della tabella che abbiamo ma se ho altre righe potrei
valutare
di metterlo piccolo
...mi aiutate nel risolvere questo problema...?
grazie a tutti

il tuo è un problema di soddisfacimento di vincoli (CSP)
ciao ho studiato ad ingegneria quest otipo di problemi,
il tuo è un problema che si può risolvere attraverso l'uso di algoritmi di
backtracking:
ti faccio l'esempio classico che riguarda uno Zaino da riempire (tu poi
vedrai il nesso
con il tuo problema e modificherai relativamente al tuo problema)
C'è uno Zaino da riempire con alcuni oggetti
lo zaino non deve pesare più di 9Kg
ogni oggetto ha un peso ed un costo
oggetti      :   piatti /  collane     /  televisore
peso (kg)  :        4 /       1        /   5
guadagno  :        1 /       10      /   6
(i numeri son mess ia caso :-)
ora il ladro deve scegliere di portare il numero massimo di oggetti
con il vincolo del peso massimo portabile (9 Kg).
che dia anche il guadagno massimo...
Come si risolve?
un algoritmo fatto così:
conosci le funzioni? Bisogna progettare una funzione che richiama se stessa.
(Vedi algoritmi di backtracking)
si ordinano gli oggetti in base al guadagno l'algoritmo prova a scegliere il
primo oggetto,
se il peso è minore 9Kg allora sceglie il secondo.... se il peso è maggiore
torna indietro toglie il secondo e sceglie il terzo oggetto,
se il peso è minore di 9Kg sceglie il 4 oggetto....
è difficile da spiegare ma leggiti dispense su
BACKTRACKING
CSP
esistono anche delle ottimizzazioni più o meno importanti che permettono la
soluzione in tempi ragionevoli.
comunque il tuo problema è risolvibile anche senza ottimizzazioni facendo un
semplice algoritmo di backtracking e
provando tutte le possibili combinazioni, un computer moderno in pochi
secondi ti da il risultato...
A

ti ringrazio per la risposta, vorrei sapere se le domande che mi
vengono in mente posso postarle sul ng.
l'elenco delle locandine lo ricavero' da un database.
le locandine sono layer e verranno visualizzati in una pagina html
(php)

dalla tua o vostra esperienza e' possibile risolvere questo genere di
problemi usando un linguaggio di programmazione tipo ASP o PHP ?

hai il link dove scaricare le dispense ?

 problemi usando un linguaggio di programmazione tipo ASP o PHP ?
qui non saprei risponderti, ASP o PHP...
lavoro con linguaggio C++ ed altri...
ad occhio però potrei dirti di si.
qui ne trovi un po'
http://www.google.it/search?hl=it&q=backtracking++zaino+%22.pdf%22&meta=
se hai bisogno posta pure in quest opost già aperto
A.

Cominciamo ad analizzare il mio problema.
A prima vista mi e' difficile pensare a valore e peso come nel
problema dello zaino.
Ho 8 box piccoli che posso riempiere.
Ho delle locandine.
Le locandine possono essere piccole o grandi.
Posso collocare al massimo 4 locandine grandi.
Posso collocare al massimo 8 locandine piccole.
Il caso banale e' quando di una locandina ho il vincolo al box e il
tipo di box.
In questo caso posiziono la locandina con la data dimensione.
Il caso si complica quando:
- per una locandina vincolata non ho il tipo di box (puo' essere
grande o piccolo)
- per una locandina non ho la posizione e il tipo di box.
C'e' qualcuno che ragiona con me ??
ciao

 ha scritto nel messaggio 
news:djkn8o$8ov$1...@newsreader.mailgate.org...

ok, allora ti ripeto che il tuo problema è un problema di soddisfacimento di 
vincoli.
ovviamente per te il vincolo non è il peso! :-)
Prima di tutto ti ripeto di leggerti qualcosa sul backtracking,
perchè se no ci muori con i ragionamenti se poi non sai come imlpementarli 
sull'elaboratore.
ITi spiego un po' cosa fa il backtracking,
il backtracking (semplice senza ottimizzazione) non fa altro che provare 
tutte le soluzioni possibili
sino a raggiungere quella ottimale, oppure una soluzione che soddisfa tutti 
i vincoli.
Ragioniamo un po' come dici tu:
se tu non specifichi bene tutto il problema è un po' difficile, fammi un 
disegno magari su nua pagina web,
esattamente quali sono i vnicoli?
che 2 locandine grandi non possono andare in un solo box ?
quante locandine vanno in un box?
c'è il problema anche dell'ordine con cui devono andare nel box?
i box sono tutti uguali e quindi l'importante è solo mettere le locandine o 
le locandine devono
seguire un qualche tipo di ordine?
Se mi fai capire bene ti posso anche scrivere in parte il codice.
in pratica attraverso il backtracking il programma mette subito le locandine 
che sono vincolate ad un box,
poi inserisce nua per una le altre locandine negli altri box, se un vincolo 
non viene soddisfatto torna indietro
di un passo per volta e prova a mettere un'altra locandina nel box....
non posso spiegartelo in mail .-) .....
dovrei farti qualche disegno.
Hai mai sentito parlare dei grafi? Degli alberi? .....
Il tuo problema con questi algoritmi che ti dico si risolve in un batti 
baleno :-)
A.

ti ringrazio per l'aiuto, quando ho un attimo di calma cerco di
spiegare il problema.
grazie mille

i box sono tutti uguali e quindi l'importante è solo mettere le locandine o 
il problema e' mettere le locandine, per alcune e' fissata la
posizione e la dimensione per altre non e' fissato niente.
grazie

 ha scritto nel messaggio 
news:djl37a$p9o$1...@newsreader.mailgate.org...

vediamo se ho capito...
facciamo una matrice di caratteri, ogni carattere corrisponde ad un box.
il programma inizia mettendo tutte le locandine vincolate nella posizione 
corrispondente.
esempio matrici e corrispondenze:
 11 21       [  0  ,   0,
 12 22          0  ,   0  ]
  31 41     [   0  ,   0
 32 42          0  ,   0  ]
dopo la sistemazione delle locandine vincolate avrai:
 11 21       [  M  ,   0,
 12 22          M  ,   L  ]
  31 41     [   0  ,   0
 32 42          P  ,   0  ]
poi il programma lancia la funzione di backtracking che farà tutti i 
tentativi possibili
per riempire le rimanenti caselle vuote.
parametri d'ingresso dai le matrici riempite:
***** E' in pseudocodice!
funzioneBackTracking( matrice Box , vettore locandineRimasteDaInserire)
{
  if(LocandineRimastedaInserire=vuoto) return 0; //Il programma termina ha 
trovato la sozluzione
  for(int j =1; j< jnumeroBox ; j++){
  for(int i =1; i< inumeroBox ; i++){
   if( Box[i,j]= vuota)  {
                                  for(int 
loc=0;loc<locandinerimastedainserire;loc++){
                                      //toglie la prima locandina da 
inserire e prepara
                                      //una matrice temporanea ed un vettore 
temporaneo
                                      //inserendo la locandina nel box se 
possibile!!!
                                      //ed eliminando la locandina dal 
vettore locandineancora da niserire
                                       .......
                                       BoxTemp=Box;
                                       BoxTemp[i,j]=Locandinadainserire[loc]
                                       funzioneBackTracking( BoxTemp, 
locandineRimasteDaInserireTemp)
                                                //Questi passi vengono fatti 
per ogni locandina
                                  }
     }
  }
}
Si genera un albero in cui ogni ramo è nua locandina immessa nella 
soluzione.
In soldoni
Primo Passo il programma tenta di mettere in11 un'altra locandina
ma è già pieno il box, quindi va in 21 e prova amettere le n locandine 
rimaste si
creano così n istanze della funzione backtracking ed in ognuno di questi n 
casi
la posizione 21 c'è una locandina diversa.
 11 21       [  M  ,   0,
 12 22          M  ,   L  ]
  31 41     [   0  ,   0
 32 42          P  ,   0  ]
..... boh, non so se si riesce a capire il procedimento....
se non hai mai visto il backtracking devi assolutamente leggertelo un po'.

http://www.vyomworld.com/gate/cs/ada/Image21.gif
l'albero che si crea è di questo tipo:
ogni nodo corrisponde ad un tipo di disopsizione delle locandine,
ogni ramo corrisponde ad un 'altra locandina messa nel sistema.
in fondo agli ultimi posti ci sono le varie soluzioni,
cioè tutte le locandine disposte, se non è opssibile continuare
l'algoritmo torna indietro e prende un'altra strada.
A. 

http://kti.ms.mff.cuni.cz/~bartak/constraints/images/backtrack.gif
qui trovi una soluzione di come disposrre 4 regine su una scacchiera 4x4,
in modo che nessuna regina possa mangiarne un'altra
guarda bene cosa fa l'algoritmo....
prima mette una regina al primo posto,poi ne mette un'altra al secondo posto
ma questa è una disposizione che non va bene allora termina e sigenera 
un'altro ramo a destra..
A. 

parto sempre dalla tabellina della fotografia.
lo stato iniziale e' 
0 0
0 0
0 0
0 0 
posiziono le tre vincolate e la configurazione diventa
M 0
M L
0 0
P 0
(attenzione perche' quando posiziono PAOLO il tuo algoritmo considera
che sia di tipo piccolo)
Ora devo posizionare ENZO e GIANNI.
Supponendo che siano entrambi piccoli, semplicemente potrei scandire
la matrice, trovo un posto vuoto e lo occupo, idem per GIANNI.
Non capisco come prosegue il tuo algoritmo.

 ha scritto nel messaggio 
news:djlbhv$50v$1...@newsreader.mailgate.org...

prosegue richiamando la stessa funzione,
č una funzione ricorsiva hai presente come sono fatte?
se vai avanti come dici tu arrivi poi o alla fnie e quindi a sistemarli 
tutti oppure arrivi in un punto ni cui
non puoi piů sistemarli allora devi togliere l'ultimo e provare a 
scambiare.....
segui il ragionamento ad albero,
fai in modo che la funzione possa richiamare se stessa passandogli i 
parametri
in modo che questi via via cambiano a seconda del percorso che sta seguendo.
lo so hai ragione , non si puň capire bene solo parlando via mail...
cercherň una dispensa su backtracking e te la passo
A.

scambiare.....
non capisco quello che spieghi dopo "oppure".
sistemo le vincolate e poi prendo le restanti.
ciascuna la metto piccola e riempio i buchi
ovvio che se arrivo ad occupare 8 box poi non posso piu' aggiugere
altre locandine.
n.b. se le locandine non vincolate + le locandine vincolate sono in
totale maggiori di 8 e quindi non ci starebbero tutte, posizione le
vincolate sempre, e scelgo a caso le altre da mostrare.
Dato che tutto dovra' apparire in una pagina web, faccio in modo che
ad ogni visita le locandine non vincolate "girano a caso"

 ha scritto nel messaggio 
news:djleu4$a69$1...@newsreader.mailgate.org...

hai aggiunto delle cosuccie che non avevi detto :-)
ti capisco che non mi capisci (scusa il giro di parole)...
mettiamo un problema semplice per capirci:
Si hanno due tipi di locandine
Si hanno solo 2 locandine
Mario è piccola
Luca è piccola
si hanno solo 4 box (mettiamo per semplificare che sono in un vettore)
1  2  3  4
il caso iniziale è (vettore di caratteri  per semplificare....):
X  X  X  X
la funzione dev'essere ricorsiva!! questo è importante!
sistemaBox( char vetBox[4])
{
  if( vetBox[4]!='X') return; //Trovata soluzione
      copiavet(tempvetBox,vetbox)
      tempvetBox[posizionesuccessivavuota]=locandinapiccola;
      sistemaBox( tempvetBox , tempvetLocandine)   //Richiama funzione 
ricorsivamente
      copiavet(tempvetBox,vetbox)
      tempvetBox[posizionesuccessivavuota]=locandinagrande;
      sistemaBox( tempvetBox , tempvetLocandine)   //Richiama funzione 
ricorsivamente
  }
}
naturalmente ci sono dei controlli da fare:
finiscono le locandine.... etc...
in questo caso questa funzione crea ad ogni nodo due rami possibili,
prima esplora la parte sinitra dell'albero provando a mettere tutte 
locandine piccole
                                        0 0 0 0
                            /                                     \
                L 0  0  0                            M  0  0  0
                /         \                            /                \
    L  L  0   0       L M 0  0         M L 0  0      M M 0 0
naturalmente tu non hai due Luca.... etc..
ma è solo per farti capire come fnuziona il gioco
e così via il programma eslpora prima i rami a sinistra e via via sale in 
quelli di destra...
Tu devi aggiungere mano a mano i vari vincoli che hai,
questo è un esempio di partenza... e dovrai usare matrici al posto di 
vettori
FUNZIONI RICORSIVE
http://www.liuc.it/person/gbuonann/Info1/Materiale/13%20-%20Funzioni%20Ricorsive.pdf
alcune dispense sul backtracking:
http://ocw.mit.edu/NR/rdonlyres/Aeronautics-and-Astronautics/16-412JSpring2004/9FA57B35-FFE3-4494-BECA-29C865940976/0/reffdynbacktrack.pdf