PROGRAMMA POSSIBILE O IMPOSSIBILE????

[micuin]

Chiedo aiuto a tutti i programmatori seri di questo forum,

mi hanno chiesto di realizzare un programma per l'ottimizzazione dell'utilizzo di un forno per lavorare pallet.

Il programma deve avere in input tutti i pallet che si vogliono inserire, in output la migliore disposizione per ottimizzare il volume di tutto il forno.

Per semplificare le cose mi hanno chiesto di gestire pallet di ogni dimensione e forma considerando anche il possibile incrocio tra due pallet.

Chiedo a tutti voi se questo è un programma fattibile e casomai qualche consiglio di implementazione.

Grazie.:P

p.s. io lo scrivo in java.

[brunino]

prima cosa: cosa piffero è una pallet??? e di che forno stai parlando??? ^^

cmq apparte gli scherzi tutti i programmi sono più o meno fattibili diciamo che è il farli per bene il difficile ^^

[piripicchio]

Ma chi ti ha chiesto di realizzare il software ti paga? Perché non sembra aver fatto un grande affare...

[Basch]

Io conosco il forno a pellet.. a pallet meno...

[dleonard]

ciao sono un amico di micuin...si, verrà retribuito per questo lavoro.

i pallet sono questi http://images.google.it/images?hl=it&q=pallet&btnG=Cerca+immagini&gbv=2

non so in che cosa consista la lavorazione in questo forno, però questa ditta ha fondamentalmente bisogno di ottimizzare lo spazio del forno per ogni lavorazione, dato che i pallet sono tutti di dimensioni differenti...ora il problema non è tanto calcolare il numero e i tipi di pallet che possono entrare nel forno ad ogni lavorazione, ma la cosa davvero difficile è calcolare la disposizione esatta degli stessi per ottimizzare il volume del forno...spero di essere stato chiaro...

[dleonard]

Perché non sembra aver fatto un grande affare...

i commenti del cavolo puoi anche risparmiarli...micuin non è un professionista e non verrà retribuito come tale...

[piripicchio]

i commenti del cavolo puoi anche risparmiarli...micuin non è un professionista e non verrà retribuito come tale...

Non è un commento del cavolo, è la realtà dei fatti. Lo pagheranno (non importa quanto, è piuttosto ovvio che sarà poco) per risolvere un problema che lo ha già mandato nel pallone tanto da chiedere aiuto nella sottosezione programmazione di un forum per Mac-user!

Ripeto, contenti loro.

[micuin]

A me sembra di avere fatto una domanda abbastanza semplice.

Si o no.

Se uno non sa cosa scrivere, puo anche non scrivere nulla.

[dleonard]

Non è un commento del cavolo, è la realtà dei fatti. Lo pagheranno (non importa quanto, è piuttosto ovvio che sarà poco) per risolvere un problema che lo ha già mandato nel pallone tanto da chiedere aiuto nella sottosezione programmazione di un forum per Mac-user!

Ripeto, contenti loro.

se viene chiamato un non-professionista, piuttosto che un professionista per risolvere dei problemi, si risparmia, ma ci sia accollano anche eventuali rischi di non essere soddisfatti...

detto questo, se secondo te il problema è semplice, aiutalo per quello che puoi altrimenti evita dei commenti inutili e presuntuosetti...(questa è una comunità virtuale, ci si aiuta, ci si scambiano opinioni e pareri, non si fa a gara a chi ce l ha più lungo e a chi è piu bravo)

[piripicchio]

A me sembra di avere fatto una domanda abbastanza semplice.

Si o no.

Se uno non sa cosa scrivere, puo anche non scrivere nulla.

Ma sei tu a non sapere cosa scrivere (il codice, intendo)!

E la domanda non è affatto semplice!

In bocca al lupo, comunque

[piripicchio]

se viene chiamato un non-professionista, piuttosto che un professionista per risolvere dei problemi, si risparmia, ma ci sia accollano anche eventuali rischi di non essere soddisfatti...

detto questo, se secondo te il problema è semplice, aiutalo per quello che puoi altrimenti evita dei commenti inutili e presuntuosetti...(questa è una comunità virtuale, ci si aiuta, ci si scambiano opinioni e pareri, non si fa a gara a chi ce l ha più lungo e a chi è piu bravo)

Non è una gara a chi ce l'ha più lungo, io non sono un'informatico e quindi mi tiro subito indietro.

Parlando seriamente, il problema del non-professionista è una peculiarità tutta italiana: piuttosto che pagare un buon lavoro (da un professionista, o presunto tale) si preferisce pagare due spiccioli e affidarsi al primo studente volenteroso che riesce a risolvere il problema.

Riguardo i miei commenti, mi dispiace ma non ho resistito!

[zzi_miei]

ti dico subito che la faccenda non e' banale...si tratta di un problema di ottimizzazione!

ci sono varie strade:

1) ricerca esaustiva=provi tutte le combinazioni possibili(es.:backtracking). ti dico subito che dipende tutto dal numero di pallet che devi trattare.la complessita' di backtracking (corregetemi se sbaglio) dovrebbe essere O(n!)(la prima scelta la fai tra n, la seconda tra n-1,n-2...ecc).in numeri se devi disporre 20 pallets devi effettuare 2432902008176640000 valutazioni (nel caso peggiore.se riesci a riempire il forno al primo colpo ti fermi subito).

2) algoritmi di programmazione dinamica: per nulla banale.implica dimostrazioni di sottostruttura ottima su carta prima di mettere mano al codice (a memoria dovresti ricavare tu l'algoritmo).in pratica devi trovare una funzione costo da minimizzare (o una funzione guadagno da massimizzare).

3)algoritmi approssimati: greedy,branch&bound ecc....ti devi accontentare di trovare una soluzione che potrebbe non essere quella ottima.

4)al momento non mi viene in mente altro...caso mai ti faccio sapere.

buon lavoro

p.s.:non so cosa intendi per "incrocio dei pallets" quindi non ne ho tenuto conto.

[napoleone1981]

Beh, se non ricordo male dagli esami Intelligenza Artificiale, gli algoritmi greedy (forse tra questi anche l'A*) sono la tua soluzione. Mentre dagli esami di Ricerca Operativa, potrebbe fare comodo il Knapsack o il branch & bound che già hanno citato.

Se metti questi nomi su wikipedia o google trovi spiegazioni e codici già fatti (da customizzare secondo le tue esigenze...)

[dleonard]

effettivamente un algoritmo di approssimazione sarebbe l'ideale...

l'incrocio tra 2 pallet consiste nel metterli "a forchetta", nel senso:

uno posto su piano, normalmente, e uno ribaltato sopra di esso.

non so se rendo l'idea...comunque non è affatto un ottimizzazione semplice...

[macsig]

Ciao,

anch'io consiglio un algoritmo greedy

Il tuo problema e' un tipico problema "dello zaino"

Dai un'occhiata qui: http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Greedy/knapscakFrac.htm

I pallets hanno sempre forma di parallelepipedi ???

PS NON ESISTONO PROBLEMI IMPOSSIBILI

:ciao:

[zzi_miei]

giusto una precisazione relativa al mio post precedente:

se riuscissi a trovare una funzione di scelta ottima, l'algoritmo greedy non sarebbe per nulla approssimato.

[micuin]

Data la difficolta' dell'algoritmo e l'infinita di variabili da gestire ho deciso di rinunciare alla creazione del programma.

Grazie a tutti lo stesso per l'aiuto.:P

[macsig]

Sinceramente non mi sembrava poi cosi' difficile

Ovviamnete oltre all'algoritmo in se devi valuatre le tue capacita' di sviluppo

:ciao:

[napoleone1981]

PS NON ESISTONO PROBLEMI IMPOSSIBILI

Su questo ho qualche dubbio... I problemi NP-completi come li classifichi??

[-skip-]

ti dico subito che la faccenda non e' banale...si tratta di un problema di ottimizzazione!

ci sono varie strade:

1) ricerca esaustiva=provi tutte le combinazioni possibili(es.:backtracking). ti dico subito che dipende tutto dal numero di pallet che devi trattare.la complessita' di backtracking (corregetemi se sbaglio) dovrebbe essere O(n!)(la prima scelta la fai tra n, la seconda tra n-1,n-2...ecc).in numeri se devi disporre 20 pallets devi effettuare 2432902008176640000 valutazioni (nel caso peggiore.se riesci a riempire il forno al primo colpo ti fermi subito).

2) algoritmi di programmazione dinamica: per nulla banale.implica dimostrazioni di sottostruttura ottima su carta prima di mettere mano al codice (a memoria dovresti ricavare tu l'algoritmo).in pratica devi trovare una funzione costo da minimizzare (o una funzione guadagno da massimizzare).

3)algoritmi approssimati: greedy,branch&bound ecc....ti devi accontentare di trovare una soluzione che potrebbe non essere quella ottima.

4)al momento non mi viene in mente altro...caso mai ti faccio sapere.

buon lavoro

p.s.:non so cosa intendi per "incrocio dei pallets" quindi non ne ho tenuto conto.

dove studi? pisa per caso? è il mio stesso esame... programmazione dinamica ecc.. insomma algoritmi e strutture dati

[-skip-]

Ciao,

anch'io consiglio un algoritmo greedy

Il tuo problema e' un tipico problema "dello zaino"

Dai un'occhiata qui: http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Greedy/knapscakFrac.htm

I pallets hanno sempre forma di parallelepipedi ???

PS NON ESISTONO PROBLEMI IMPOSSIBILI

:ciao:

esistono però problemi per i quali non è possibile individuare una soluzione ottima ma solamente una che vi si avvicina (ad esempio gli algoritmi ingordi/golosi come l'esempio del disporre i libri nello zaino, che hai citato te)

[marcopk]

Su questo ho qualche dubbio... I problemi NP-completi come li classifichi??

quoto

[macsig]

Su questo ho qualche dubbio... I problemi NP-completi come li classifichi??

Se non ricordo male (sono passati alcuni anni del quando ho dato Informatica Teorica ) non e' stato dimostrato che i problemi NP-completi non hanno soluzione. In ogni caso, con la mia frase, non volevo entrare nel difficile campo della complessita' computazionale ma solo esprimere la mia attitudine di fronte ad un problema che si presenta durante la progettazione di un'applicazione.

One example of an NP-complete problem is the subset sum problem which is: given a finite set of integers, determine whether any non-empty subset of them sums to zero. A supposed answer is very easy to verify for correctness, but no one knows a significantly faster way to solve the problem than to try every single possible subset, which is very slow.

:ciao:

[macsig]

Grazie per la precisazione ma questo lo sapevo gia'.

:ciao:

[Coniglione]

il mio nerdometro è schizzato alle stelle!!!

[iMaffo]

io avrei usato l'algoritmo del simplesso... è programmazione lineare o mi sono perso qualcosa?

edit: direi di si ora che lo rileggo non ne sarei più tanto sicuro..

[zzi_miei]

[-skip-]

eheh qui a pisa si fa in un unico blocco

[BlackICE]

Ma tu guarda... per la tesi ho sviluppato e implementato proprio un algoritmo di approssimazione per la risoluzione di un problema NP-Hard in tempo polinomiale.

Ciao,

anch'io consiglio un algoritmo greedy

Il tuo problema e' un tipico problema "dello zaino"

Dai un'occhiata qui: http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Greedy/knapscakFrac.htm

Un algoritmo greedy potrebbe essere una soluzione ma deve stare attento perchè a seconda del problema, del punto di partenza per la ricerca nello spazio delle soluzioni, e del metodo di ricerca potrebbe anche ottenere soluzioni molto lontane dall'ottimo in tempi non per forza polinomiali.

Con un algoritmo approssimato potrebbe invece ottenere una soluzione più "sicura" nel senso che può decidere il "livello di approssimazione" per il quale ottenere una soluzione soddisfacente in tempi soddisfacenti.

PS NON ESISTONO PROBLEMI IMPOSSIBILI

Ora qualche ricordo vago dei corsi di calcolabilità e complessità riaffiora a fatica... ma non ci giurerei su questa affermazione. Mi ricordo di funzioni calcolabili e non e della loro equivalenza con i problemi {P, NP} e le macchine di turing, algoritmi, ecc, ecc.. argomenti complicati...

Su questo ho qualche dubbio... I problemi NP-completi come li classifichi??

Problemi NP-completi = Problemi difficili, cioè non risolvibili in maniera deterministica in tempo polinomiale. I problemi NP-completi non sono affatto impossibili.

[macsig]

... ma non ci giurerei su questa affermazione.

In ogni caso, con la mia frase, non volevo entrare nel difficile campo della complessita' computazionale ma solo esprimere la mia attitudine di fronte ad un problema che si presenta durante la progettazione di un'applicazione.

I problemi NP-completi non sono affatto impossibili.

Allora non ricordavo male

:P