Algoritmo riempimento superfici

[Iperion]

Non so se è il newsgroup giusto, comunque mi è sorto recentemente il
seguente problema:

Mi viene fornita solo una dimensione di un rettangolo (la seconda devo
calcolarla io) e le dimensioni di una serie di rettangoli più piccoli.
Quello che devo fare è definire un algoritmo che mi calcola la
disposizione migliore dei rettangoli più piccoli in modo tale da
minimizzare lo spazio occupato, così da minimizzare la seconda
dimensione del rettangolo iniziale.

Non sono interessato al codice dell'algoritmo (che posso scrivere da
solo) bensì all'algoritmo stesso. L'idea che mi è venuta in mente è
molto similie ad un attacco di forza bruta, e quindi non è proprio uno
spettacolo dal punto di vista prestazionale. Qualcuno ha qualche idea o
qualche link di riferimento?

Stavo pensando se poteva essere considerato un problema di
programmazione lineare, ma non mi pare il caso (o almeno ora come ora
non mi viene in mente come costruire il vettore dei vincoli).

Inoltre volevo un consiglio sull'esistenza di qualche risorsa in rete
che tratti appunto di algoritmi, anche senza implementazione, per
risolvere problemi generici di questo tipo (o, per fare altri esempi,
algoritmi per individuare i due punti più vicini tra loro, e via dicendo).

[Njc]

Non che questo non sia il posto giusto, ma se fossi in te cercherei anche
negli ambienti (newsgroup?) di intelligenza artificiale e ricerca
operativa... credo che i primi ne sarebbero pure contenti :)

[--==M=M==--]

Post by Iperion
Non so se è il newsgroup giusto, comunque mi è sorto recentemente il
Mi viene fornita solo una dimensione di un rettangolo (la seconda devo
calcolarla io) e le dimensioni di una serie di rettangoli più piccoli.
Quello che devo fare è definire un algoritmo che mi calcola la
disposizione migliore dei rettangoli più piccoli in modo tale da
minimizzare lo spazio occupato, così da minimizzare la seconda dimensione
del rettangolo iniziale.

HAHAH e' un classico :)

Puoi usare uno di questi algoritmi
a) Algoritmi di ricerca locale (soluzioni scarse pero)
b) Montecarlo local search
c) Simulated annealing
d) Tabu' search
e) Algoritmi genetici.

Sulla rete trovi un mare di informazioni, i punti a,b,c,d sono facilmente
implementabili. I genetici richiedono un pizzico piu' di esperienza.

Il problema che hai posta mi pare sia noto in letteratura anche come:
"il problema delle scatole", fai una ricerchina, credo esistano altri
algoritmi oltra a quelli da me indicati.

Per quanto rigurada la forza bruta se proprio vuoi trovare la soluzione
migliore puoi ricorrere ad un "branch and bound", ma solo per piccoli
problemi, altrimenti puoi aspettare alche qualche migliaio di anni :)

[Iperion]

Grazie!

cerco subito per quanto mi hai detto

Post by --==M=M==--

Post by Iperion
Non so se è il newsgroup giusto, comunque mi è sorto recentemente il
Mi viene fornita solo una dimensione di un rettangolo (la seconda devo
calcolarla io) e le dimensioni di una serie di rettangoli più piccoli.
Quello che devo fare è definire un algoritmo che mi calcola la
disposizione migliore dei rettangoli più piccoli in modo tale da
minimizzare lo spazio occupato, così da minimizzare la seconda dimensione
del rettangolo iniziale.

HAHAH e' un classico :)
Puoi usare uno di questi algoritmi
a) Algoritmi di ricerca locale (soluzioni scarse pero)
b) Montecarlo local search
c) Simulated annealing
d) Tabu' search
e) Algoritmi genetici.
Sulla rete trovi un mare di informazioni, i punti a,b,c,d sono facilmente
implementabili. I genetici richiedono un pizzico piu' di esperienza.
"il problema delle scatole", fai una ricerchina, credo esistano altri
algoritmi oltra a quelli da me indicati.
Per quanto rigurada la forza bruta se proprio vuoi trovare la soluzione
migliore puoi ricorrere ad un "branch and bound", ma solo per piccoli
problemi, altrimenti puoi aspettare alche qualche migliaio di anni :)