algoritmo di scaglionamento della cucitura del pavimento in legno

1

Presto installerò parquet in legno nella mia casa. E solo per divertimento, sto pensando di scrivere un algoritmo per fare un uso efficiente delle assi di legno che ho.

Ecco il problema:

  • Ho assi di lunghezze diverse sufficienti a coprire la superficie.

  • La stanza è rettangolare (in seguito mi piacerebbe espandere l'algoritmo per tenere conto degli oggetti / muri nella stanza)

  • Le assi nelle file adiacenti devono avere le giunture / giunture sfalsate (almeno 20 cm tra le giunture adiacenti) Come scaglionare le assi del pavimento in legno
  • Ogni nuova riga deve essere avviata con il resto del cut-off della riga precedente. Preferirei non iniziare nuove righe con un resto inferiore a 20 cm
  • L'obiettivo: voglio che il disegno delle giunture / giunzioni sia il più casuale possibile e allo stesso tempo ridurre al minimo le assi di taglio e ovviamente avere la minore perdita possibile.
  • Sono uno sviluppatore .NET C # con una certa conoscenza di F # e vorrei utilizzarli per risolvere il problema.

La mia domanda è stata: ho iniziato a cercare ispirazione su quali algoritmi di base si adattassero meglio al mio problema? L'impilamento di scatole, l'accatastamento di contenitori, l'impilamento lineare ...? O meglio, qualcuno ha già risolto questo: -)?

    
posta Stif 03.09.2016 - 15:09
fonte

1 risposta

1

Posso darti un algoritmo molto generale utile per questi tipi di problemi. Questo algoritmo è utile principalmente per il tuo problema specifico perché hai uno spazio di ricerca relativamente piccolo. Se il tuo spazio di ricerca fosse enorme, avresti bisogno di alcune ottimizzazioni complesse.

Seleziona un numero fisso di scelte casuali per la prossima plancia da stabilire. Per tutte quelle scelte, fai un altro insieme di scelte casuali, ecc. Questo è simile ad un algoritmo di scacchi. Ad un certo punto, ti preoccuperai della memoria o dell'utilizzo della CPU, dal momento che il tuo albero si sta espandendo. Puoi eseguire una ricerca fino a una certa profondità, quindi selezionare il ramo migliore tra quelli, quindi continuare la ricerca dell'albero da lì.

    
risposta data 07.09.2016 - 01:40
fonte

Leggi altre domande sui tag