+ Rispondi al messaggio
Visualizzazione dei risultati da 1 a 6 su 6

Calcolo della disposizione delle confezioni all'interno dei sacchi

  1. #1
    Post
    1,000
    Blogs
    2
    Like Inviati  
    0
    Like Ricevuti  
    0
    Vi "giro" il quesito, così come me l'hanno posto:

    Ho una serie di confezioni standard (nella fattispecie, di bianchera - lenzuola, tovaglie, tovaglioli, federe, asciugamani, teli da bagno ecc, imbustate nel celofan termosaldato) di cui si conoscono volume e peso, e una serie di sacchi con un volume di riempimento "standard" e un limite di peso per sacco; devo riempire il minor numero di sacchi con una regola di "priorità" (in basso le confezioni più grosse, in alto quelle più piccole) e una regola di "omogeneità" (cerco di non mettere, nello stesso sacco, lenzuola, tovaglioli e asciugamani), senza ovviamente superare il peso limite.
    Le confezioni potrebbero "entrare" sia in orizzontale che in verticale...

    Sicuramente, per i più, è uno di quegli algoritmi triti e ritriti.

    Vi chiedo quindi, da programmatore-artigiano che modella con scalpello e martello, dove poter andare a sbattere la testa per trovare qualche informazione...

    Grazie!

  2. #2
    L'avatar di bottomap
    bottomap non è in linea Amanuense
    Post
    4,130
    Like Inviati  
    0
    Like Ricevuti  
    0
    Ciao,

    Dai un occhiata al "problema dello zaino" (Problema dello zaino - Wikipedia) o "Knapsack problem" (Knapsack problem - Wikipedia, the free encyclopedia) ... quello che proponi mi pare sia esattamente il problema in questione.

    Il problema è NP-completo (http://it.wikipedia.org/wiki/NP-completo), ma è molto studiato e si può ottenere una buona soluzione in tempo ragionevole adottando ad esempio la tecnica del Branch And Bound (http://it.wikipedia.org/wiki/Branch_and_bound). In ogni caso, con questo o altri sistemi (vedi l'algoritmo greedy citato nell'articolo) hai un algoritmo che non garantisce che la soluzione sia ottimale, ma solo una buona soluzione calcolata in un tempo decente.

    Ciaociao
    Ultima modifica di bottomap; 18-06-2010 13:46 
    ℹ️ Leggi di più su bottomap ...

  3. #3
    Post
    1,000
    Blogs
    2
    Like Inviati  
    0
    Like Ricevuti  
    0
    L'occhiata l'ho data, ma ho qualche difficoltà a portare il problema dello zaino al mio, dove gli "zaini" sono tanti e dove il fattore "omogeneità" ha la sua importanza.
    Se non ho capito male il senso degli articoli, è inutile cercare la soluzione ottimale in tempi accettabili, ci si deve accontentare di una soluzione accettabile in tempi ottimali, "provando" le prime possibili soluzioni che possono soddisfare il quesito.
    Tornando a scalpello e martello, immagino si tratti di iterare in cicli di "insaccamento" e verificare i risultati. Mi sembra una questione un po' complessa da applicare a del codice, però, e sinceramente credevo si trattasse di un problema solo matematico, quindi applicabile con formule.
    Non credo quindi che riuscirò a trasformare in pseudo-codice quegli interessantissimi articoli, e non ho idea di dove infilare la variante "omogeneità".
    Cercherò qualcosa di "pratico" sulla base della teoria che mi hai suggerito.

    Intanto grazie per le informazioni

  4. #4
    L'avatar di sLaSh17
    sLaSh17 non è in linea Scolaretto
    Post
    351
    Like Inviati  
    0
    Like Ricevuti  
    0
    Quote Originariamente inviato da cyberlaundry Visualizza il messaggio
    L'occhiata l'ho data, ma ho qualche difficoltà a portare il problema dello zaino al mio, dove gli "zaini" sono tanti e dove il fattore "omogeneità" ha la sua importanza.
    Il problema dello zaino è la base del tuo. Potresti dividere il tuo problema in tanti problemi dello zaino quanti sono i tuoi sacchi, aggiungendo il weak constraint dell'omogeneità.

    Quote Originariamente inviato da cyberlaundry Visualizza il messaggio
    Se non ho capito male il senso degli articoli, è inutile cercare la soluzione ottimale in tempi accettabili[...]
    Un problema NP-completo, come avrai letto negli articoli che ti sono stati suggeriti, è un problema risolvibile in tempo polinomiale da una macchina non deterministica (NP -> nondeterministic polynomial time).
    In realtà, nessuno ha ancora dimostrato che non sia (o sia) possibile risolverlo in tempo polinomiale anche con una macchina deterministica (il famoso problema P = NP?), ma sicuramente, nessuno è riuscito a risolvere un problema di questa complessità in tempo polinomiale, proprio per questo, non ha molto senso cercare la soluzione ottima, per la quale potrebbe essere necessario un tempo esageratamente lungo (esponenziale rispetto all'input).

    In genere, si cerca una soluzione ottimale, quindi vicina all'ottimo, oppure una buona soluzione, calcolabile in tempi ragionevoli, tramite algoritmi particolari o euristiche ad hoc.

    Quote Originariamente inviato da cyberlaundry Visualizza il messaggio
    Tornando a scalpello e martello, immagino si tratti di iterare in cicli di "insaccamento" e verificare i risultati. Mi sembra una questione un po' complessa da applicare a del codice, però, e sinceramente credevo si trattasse di un problema solo matematico, quindi applicabile con formule.
    Non credo quindi che riuscirò a trasformare in pseudo-codice quegli interessantissimi articoli, e non ho idea di dove infilare la variante "omogeneità".
    Come detto, non esiste alcun algoritmo deterministico in grado di risolvere il problema in tempo polinomiale.
    Ci sono diversi approcci che puoi usare per cercare di ottenere una soluzione buona in tempi ragionevoli; puoi ad esempio basarti sull'algoritmo del backtracking, o come giustamente consigliato da bottomap, sull'algoritmo Branch&bound, o ancora puoi sviluppare un tuo algoritmo di programmazione dinamica ad hoc.

    Un approccio molto più rapido per il programmatore, ma generalmente più costoso per il calcolatore (non sempre è detto che il calcolo termini in tempi umani), può essere quello di affidarsi alla programmazione logico-disgiuntiva (vedi Smodels).
    Il programma logico disgiuntivo che risolve il tuo problema sarebbe di pochissime righe e soprattutto molto semplice da scrivere:
    Guess: ad ogni confezione assegni un sacco
    Check: verifichi che ogni sacco non superi il peso massimo (strong constraint);
    preferisci che le confezioni più grosse siano in basso (weak constraint con penalità per ogni confezione grossa in alto);
    preferisci che in uno stesso sacco ci siano il minor numero di confezioni diverse (weak constraint con penalità moltiplicata per il numuero di confezioni diverse presenti nello stesso sacco)

    Purtroppo non ti è garantito che il programma termini in tempi ragionevoli, anche se ci sono diversi "trucchetti" che è possibile usare in base al linguaggio scelto, tramite i quali si può diminuire il tempo di calcolo.
    ℹ️ Leggi di più su sLaSh17 ...

  5. #5
    Post
    1,000
    Blogs
    2
    Like Inviati  
    0
    Like Ricevuti  
    0
    Quote Originariamente inviato da sLaSh17 Visualizza il messaggio
    Potresti dividere il tuo problema in tanti problemi dello zaino quanti sono i tuoi sacchi, aggiungendo il weak constraint dell'omogeneità.
    ...il numero di sacchi devo calcolarlo io, e deve essere il numero minore possibile in base alle regole di omogeneità, distribuzione e peso massimo...

    Un approccio molto più rapido per il programmatore [...] può essere quello di affidarsi alla programmazione logico-disgiuntiva (vedi Smodels).
    Ho dato un'occhio, ma non basta. Ci dedicherò il tempo necessario - da profano ci metterò dieci volte il tempo che serve...

    Purtroppo non ti è garantito che il programma termini in tempi ragionevoli
    Ragionevole, per me, è 3 secondi per una decina di sacchi.
    Esagero?

    Grazie!

  6. #6
    L'avatar di sLaSh17
    sLaSh17 non è in linea Scolaretto
    Post
    351
    Like Inviati  
    0
    Like Ricevuti  
    0
    Quote Originariamente inviato da cyberlaundry Visualizza il messaggio
    Ragionevole, per me, è 3 secondi per una decina di sacchi.
    Esagero?
    L'input del tuo problema non sono solo i sacchi (con le rispettive capacità massime) ma anche le confezioni.

    Come detto, il tempo necessario non è predicibile a priori.
    In genere si parte da una implementazione molto intuitiva e dichiarativa, come quella che ti ho descritto nel post precedente, e se il tempo di calcolo è esagerato si procede cercando di migliorare usando vari trucchetti, che però dipendono strettamente dal tipo di linguaggio che si sta utilizzando.

    Ho lavorato su programmazione logico-disgiuntiva soltanto a scopi didattici, e con un linguaggio proprietario di cui non conosco i dettagli tecnici; nella mia esperienza su istanze piccole di problemi NP-completi classici (appunto Knapsack, k-Colorabilità, vertex covering, clique, 3-SAT etc) i tempi di risoluzione erano quasi sempre inferiori al secondo, a volte con qualche piccola accortezza nella scrittura (come dicevo prima).

    Resta però il fatto che questo approccio non garantisce che i tempi siano quelli sperati.

    Ti ho parlato di programmazione logico-disgiuntiva più che altro per completezza, e perchè trova senso soprattutto (o solo) in applicazioni del genere (problemi "difficili").

    Personalmente cercherei di integrare un euristica ad hoc che punta a trovare una soluzione buona o (meglio) ottimale, in tempi ragionevoli, in un algortimo classico come il branch&bound, o usando la tecnica del backtracking.
    ℹ️ Leggi di più su sLaSh17 ...

+ Rispondi al messaggio

Potrebbero interessarti anche ...

  1. Calcolo Somma all'interno di una gridview
    Da maurizio75 nel forum C#
    Risposte: 2
    Ultimo Post: 16-12-2020, 10:46
  2. Nuova disposizione grafica delle informazioni utente
    Da sistemista nel forum Comunicazioni
    Risposte: 4
    Ultimo Post: 04-11-2015, 11:30
  3. calcolo delle ore tra 2 date
    Da Giosci nel forum Microsoft Word
    Risposte: 5
    Ultimo Post: 17-02-2011, 21:30
  4. [CSS]Scrollbar all'interno delle DIV
    Da BrandonHeat nel forum HTML, CSS e JavaScript
    Risposte: 7
    Ultimo Post: 13-10-2006, 12:52
  5. muoversi all’interno delle maschere
    Da elettrolince nel forum Microsoft Word
    Risposte: 3
    Ultimo Post: 02-09-2004, 15:15