Newsgroup: it.comp.programmare
Titolo: [OT, x/post e f/up] Dividere rettangolo

 inferiore
[OT] x/post e f/up su it.comp.programmare
  non credo che saprei rispondere _comunque_, ma la formulazione del
  problema e' un po' troppo ellittica... spiegaci almeno se
  - gli n rettangoli sono tutti eguali tra loro, o hai una lista, e.g,
    [(4,7),(4,9),...,(3,5)] in cui sono specificati i lati dei
    rettangoli?
  - i rettangolini puoi ruotarli di 90 gradi? ovvero, e' indifferente
    se un rettangolo ha b=10, h=20 oppure ha b=20, h=10?
   (se l'applicazione fosse tagliarli da un tessuto (ortotropo), la
    risposta potrebbe essere NO)
-- 
termy prende per fatica, attento.                     -- PLS, in IFQ

   problema e' un po' troppo ellittica...
anche il mio cut&paste e' troppo ellittico... l'OP vuole soprattutto
sapere come piazzare il maggior numero di rettangolini nel
rettangolone col minimo sfrido (se ho capito, cosa di cui dubito ;)


     se un rettangolo ha b=10, h=20 oppure ha b=20, h=10?
si e' indifferente, possono ruotare di 90 gradi ma l'importante č che la
loro posizione ottimizzi il piů possibile lo spazio rimanente.
Ti ringrazio della risposta.
Saluti.
--
mtofa
mt...@iol.it


Mi sono perso i messaggi iniziali, cmq se ho capito devi posizionare il
maggior numero di rettangolini su un rettangolo piu' grande cercando di
*minimizzare* lo sfrido.
In tal caso il problema e' noto con diversi nomi, problema del sacco,
problema dello zaino, problema del ladro ecc..
Non e' un problema risolvibile, devi appogiarti ad un buon algoritmo
euristico, per esperienza personale i piu' efficaci sono:
1) algoritmi evolutivi
2) algoritmi genetici
3) simulated annealing
4) taboo search
5) Tecniche di search, pittosto scadenti pero', come Hill Climbing
6) Qualche euristico ad oc per il tuo preblema mi pare sia stato
   realizzato, ma non sono sicuro fai una ricerca.
Spero di essere stato di aituo, happy coding 
P.S.: Mi pare di aver capito che stai usando Python, in tal caso se ti
      interessano le prestazione ti consiglio di passare a Fortran o C,
      perche' per avere ottimi risultati occorrono tempi notevoli.

       perche' per avere ottimi risultati occorrono tempi notevoli.
Non prima di aver provato Psyco, o Pyrex, o magari aver scritto
un'estensione in C. Non farmi citare un'altra volta Knuth, su. :^)
- --
"I would certainly not want to code business or templating logic
in a static language like C++ or Java. In that space servlets/JSP
are a three legged dog, a sideshow at best."  Bill de hÓra
Nicola Larosa - nico...@m-tekNico.net
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.2 (GNU/Linux)
iD8DBQE/HFGmXv0hgDImBm4RAqFQAJ0bvNWVOcKzRjBAj4958hD+Dx/RlQCbBkWa
3j6yzC/Jk3zXvHHN4+U0Qw4=
=DEBp
-----END PGP SIGNATURE-----

       perche' per avere ottimi risultati occorrono tempi notevoli.
Addirittura?
Grazie della risposta.
--
mtofa
mt...@iol.it

scusate una considerazione:
Ma questo non e' il problema dello zaino "travestito"?
Ma non e' NP-completo?
ciao,
Nids
ps: se ho ragione usa l'approcci greedy che ti conviene. Non avrai l'ottimo
ma te la cavi alla svelta, molto alla svelta rispetto ai tempi esponenziali
dati dalla NP-completezza :)

 un'estensione in C. Non farmi citare un'altra volta Knuth, su. :^)
Mhh non cono Psyco o Pyrex, sono fermo a scipy e chaco, cosa sono?
Per Knuth cita cita che e' sempre un piacere :)
Ciao

 Per Knuth cita cita che e' sempre un piacere :)
"Premature optimization is the root of all evils." E la scelta di un
linguaggio di livello non abbastanza alto è la regina di tutte le
ottimizzazioni premature. :^)
- --
"The unemployed programmer had a problem.
"I know", said the programmer, "I'll just learn Perl."
The unemployed programmer now had two problems."
  Erik Naggum
Nicola Larosa - nico...@m-tekNico.net
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.2 (GNU/Linux)
iD8DBQE/IFbCXv0hgDImBm4RAkwaAJ9imZo5H9F9knei9ukfRI980ITrUQCdEu5E
ocjrBEoj4mpNuASfs9iqQGk=
=uFqJ
-----END PGP SIGNATURE-----

 ha scritto nel messaggio
news:4lOTa.8334$Df5.2...@news1.tin.it...

Proverò come dici tu, ma non sono sicuro di riuscire a realizzare qualcosa
di funzionante...  :-//
C'è da tener conto che nel caso in questione si tratta di posizionare in
modo ottimale delle figure geometriche (rettangoli) in funzione della
lunghezza dei loro lati e della lunghezza lati del rettangolo che li deve
contenere.
Grazie per i tuoi consigli.
--
mtofa
mt...@iol.it

 
ahhh ti riferivi a questa :)
Non ho detto di pensare a come ottimizzare ma solo di usare strumenti
che *dovrebbero* garantire una velocita' d'esecuzione migliore.
Per il resto il Fortran90 e' un ottimo compromesso tra linguaggio ad
alto livello (piu' del f77 o C) e ottimizzazioni implementate in modo 
trasparente dal compilatore. 

 trasparente dal compilatore.
Non conosco bene il Fortran, ma dal poco che so (qualche articolo, anche sul
'90) non mi sembra una scelta interessante.
- --
"After having used Python intensively for six years, Industrial Light
& Magic has yet to run into significant bugs or portability issues
with the language. [...] Since its adoption in 1996, the use of Python
has also been reviewed numerous times. Each time, ILM failed to find
a more compelling solution."  Tim Fortenberry
Nicola Larosa - nico...@m-tekNico.net
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.2 (GNU/Linux)
iD8DBQE/JjRnXv0hgDImBm4RAm/cAKChStzJRUshsdMLMYiHJ9HG2xnnXQCeJagO
w08HRIFUouGwu+Mcct8ioQY=
=ln9G
-----END PGP SIGNATURE-----