Algoritmus pro skládání kousků dřeva

mrtn

Re:Algoritmus pro skládání kousků dřeva
« Odpověď #15 kdy: 09. 06. 2016, 06:04:06 »
sorry, ale asi jsem nepochopil, v čem je problém

jestli ty kusy navazují jako skládací metr, tak celek bude dlouhý jako nejdelší kus, ostatní kusy se složí "tam a zpět" (tedy - + - + a na jejich pořadí už nezáleží)


Karbous

Re:Algoritmus pro skládání kousků dřeva
« Odpověď #16 kdy: 09. 06. 2016, 07:56:07 »
Vymyslel jsem 2 algoritmy -
1)Teoreticky nejmensi reseni je stejne dlouhe jako nejdelsi drivko tedy:
- nalezt nejdelsi drivko - rozdeli problem na 2 casti - vlevo a vpravo od tohoto drivka.
 - v kazde casti najit opet nejdelsi drivko a zase rozdeli problem kazdou stranu na dalsi 2 casti
  - pokracovat dale az se problem zjednodusi a pujde spocitat rozume a pak z nalezenych min delek slozit vysledek.

2) Eliminacni postup - mensi drivko mezi dvema vetsimi jde vzdy slozit tak, aby nepridalo delku tedy je ho mozne eliminovat.  Takto postupovat az zbyde nejaka kratsi posloupnost drivek a tu pak vyresit.

Obe metody resit bud bruteforce anebo tim Monte Carlem, pokud by toho bylo moc... pripadne zkombinovat..

Pokud moje predpoklady vyse neplati tak sorry :) Ale aspon jsem to zkusil :)


Michal Kovačič

Re:Algoritmus pro skládání kousků dřeva
« Odpověď #17 kdy: 09. 06. 2016, 08:12:46 »
sorry, ale asi jsem nepochopil, v čem je problém

jestli ty kusy navazují jako skládací metr, tak celek bude dlouhý jako nejdelší kus, ostatní kusy se složí "tam a zpět" (tedy - + - + a na jejich pořadí už nezáleží)

To jsem si myslel taky - zkuste kusy o velikosti 5, 2, 4 v tomto poradí - výsledek bude 6

newbie

Re:Algoritmus pro skládání kousků dřeva
« Odpověď #18 kdy: 09. 06. 2016, 08:24:15 »
nestačí to překládat vždy v polovině?

aydx\as

Re:Algoritmus pro skládání kousků dřeva
« Odpověď #19 kdy: 09. 06. 2016, 08:32:30 »
Nechápu tvůj problém?

a) Když je to jak skládací metr, pak je nejdelší dřívko vždy minimální a maximální délka.

b) jak je rovnice co má výsledek 2, pak je to opět jednoduché, kdy od postupuješ od nejdelšího k nejkratšímu a jenom měníš známínka.  (6-5+3-2)=2

Jaksi buď nechápu co vlastně dostáváš (=metr) nebo mám pocit, že hledáš nějakou složitou rovnici místo jenom seřazení a změny znamének...


aydx\as

Re:Algoritmus pro skládání kousků dřeva
« Odpověď #20 kdy: 09. 06. 2016, 08:38:23 »
Ještě pokud to musí být skládáno vpořadí jako metr, pak nezáleží ani tak "na rovnici", ale spíše otrockém počítání v cyklu a pomocí "if" počítat jak přeložit následující dřívko. "Rovnice" bude jiná pokaždé pro jiné soubor dřívek...

Tak jako tak, ve třech "případech" co mě napadli na tvojem příkladu mi stále vychází, že rovnici nedostaneš a je blbost ji hledat, pokud hledáš universální řešení a hlavně je to lukem na slona...

Rcz

Re:Algoritmus pro skládání kousků dřeva
« Odpověď #21 kdy: 09. 06. 2016, 09:09:06 »
sorry, ale asi jsem nepochopil, v čem je problém

jestli ty kusy navazují jako skládací metr, tak celek bude dlouhý jako nejdelší kus, ostatní kusy se složí "tam a zpět" (tedy - + - + a na jejich pořadí už nezáleží)

To jsem si myslel taky - zkuste kusy o velikosti 5, 2, 4 v tomto poradí - výsledek bude 6
No jasně, ale co ti brání to vzít v dobrém pořadí? tedy od největšího po nejmenší?
Tedy:
setřídit dřívka podle velikosti a poskládat jako skládací metr. Délka bude délka toho nejdelšího, ale "výška" metru optimální nebude.

TomasJ

Re:Algoritmus pro skládání kousků dřeva
« Odpověď #22 kdy: 09. 06. 2016, 09:13:35 »
Z prvního pohledu se zdá jako úloha pro celočíselné programování. ( google: integer programming ). Již kdosi přede mnou přesně odhadl, tak to bude NP složité. Myslím, že to přímo jeden z Karpových problémů. https://en.wikipedia.org/wiki/Karp's_21_NP-complete_problems. Až přijdete na nějaké algoritmické řešení, tak se určitě pochlubte. Já bych asi zkoušel buď genetické algoritmy https://en.wikipedia.org/wiki/Genetic_algorithm, nebo pravidlový inferenční stroj případně jejich kombinaci.

Re:Algoritmus pro skládání kousků dřeva
« Odpověď #23 kdy: 09. 06. 2016, 09:44:55 »
Teď koukám, že jsem zprvu nepochopil zadání - pořadí je pevně dané, což?

V tom případě by mohl algoritmus vypadat následovně (opět je jen lineární obvykle fungující implementace v případě "rozumné" distribuce dílků):

1. Nadefinovat left=0 (levá hranice), right=0 (pravá hranice), current=0 (aktuální pozice konce)
2. Vzít následující element, porovnat current-element-left a current+element-right a podle toho, který z nich bude větší, umístit element doleva či doprava. Minimalizuje buď přesah nebo není-li žádný, maximalizuje prostor pro další krok
3. Podle předchozího kroku upravit current = current+-element a pokud překročí left/right hranice, tak i ty
4. Loop to (2) until input empty

ByCzech

  • *****
  • 1 848
    • Zobrazit profil
    • E-mail
Re:Algoritmus pro skládání kousků dřeva
« Odpověď #24 kdy: 09. 06. 2016, 09:48:55 »
Představte si následující problém:
mám kousky dřeva různých délek (např. 3, 5, 2 a 6 cm) spojených na svých koncích (podobně jako skládací metr). Úkolem je najít rovnici, která povede k nejmenší délce složených kousků.
Jedno z možných řešení je sestavit všechny možné rovnice a spočítat složenou délku:
3 + 5 + 2 + 6 -> délka 16
3 + 5 + 2 - 6 -> délka 10
3 + 5 - 2 + 6 -> délka 8
3 + 5 - 2 - 6 -> délka 8
3 - 5 + 2 + 6 -> délka 8
3 - 5 + 2 - 6 -> délka 9
3 - 5 - 2 + 6 -> délka 7
3 - 5 - 2 - 6 -> délka 13
Hledaná rovnice (která nemusí být jen jedna) je tedy 3 - 5 - 2 + 6.
Generování všech rovnic zabere poměrně dost času (například při padesáti kouscích to vyjde na nějakých 2 500 let). Existuje algoritmus (případně s kódem), jak najít požadovanou rovnici ještě během mého života :-)
Díky!

Nevím jestli chápu zadání správně, ale podle podmínek je řešení vzít nejmenší kousek a ostatní v libovolném pořadí odečíst, tím vyjde záporná délka :-D.

2-3-5-6 = -12

a vlastně proč neodečíst už i první číslo?

-2-3-5-6 = -14

Problem solved :-D

Laky

Re:Algoritmus pro skládání kousků dřeva
« Odpověď #25 kdy: 09. 06. 2016, 10:21:49 »
mozno by sa tvoja uloha dala preformulavat na nieco taketo
https://en.wikipedia.org/wiki/Cutting_stock_problem
resp. niektore s rieseni prisposobit tvojej ulohe
doriesit by ju potom nemal byt problem

Karbous

Re:Algoritmus pro skládání kousků dřeva
« Odpověď #26 kdy: 09. 06. 2016, 10:42:38 »
Hmm tak muj algoritmus c. 2 je blbost... srry

Nicmene snad je mozne rychleji eliminovat spatna reseni predpokladem, ze nejmensi delka bude vzdy mensi nez soucet delky dvou nejdelsich drivek.
Tzn, vypocet varianty stopnout, kdyz tuto delku prekroci a nasledne preskocit ty, ktere maji stejnou posloupnost... 


Re:Algoritmus pro skládání kousků dřeva
« Odpověď #27 kdy: 09. 06. 2016, 10:50:11 »
V tom případě by mohl algoritmus vypadat následovně (opět je jen lineární obvykle fungující implementace v případě "rozumné" distribuce dílků):

1. Nadefinovat left=0 (levá hranice), right=0 (pravá hranice), current=0 (aktuální pozice konce)
2. Vzít následující element, porovnat current-element-left a current+element-right a podle toho, který z nich bude větší, umístit element doleva či doprava. Minimalizuje buď přesah nebo není-li žádný, maximalizuje prostor pro další krok
3. Podle předchozího kroku upravit current = current+-element a pokud překročí left/right hranice, tak i ty
4. Loop to (2) until input empty
Protipříklad:
Váš algoritmus: 1-3+1+4=5
Správné řešení: 1-3-1+4=4

Jenda

Re:Algoritmus pro skládání kousků dřeva
« Odpověď #28 kdy: 09. 06. 2016, 11:03:50 »
Soucítím s tazatelem jak ho skoro nikdo nechápe… Zkusil bych se kouknout na https://en.wikipedia.org/wiki/Knapsack_problem#Dynamic_programming_in_advance_algorithm

Nechápu tvůj problém?

a) Když je to jak skládací metr, pak je nejdelší dřívko vždy minimální a maximální délka.

Není, například pro zadání "100 1 100" je nejdelší dřívko 100, minimální délka 101 a maximální 201.

Ještě pokud to musí být skládáno vpořadí jako metr, pak nezáleží ani tak "na rovnici", ale spíše otrockém počítání v cyklu a pomocí "if" počítat jak přeložit následující dřívko.

Problém je v tom, že zkoušet to hrubou silou je výpočetně neúnosné.

"Rovnice" bude jiná pokaždé pro jiné soubor dřívek...

Tazatel IMHO "rovnicí" myslí seznam znamének, prostě řešení toho problému.

No jasně, ale co ti brání to vzít v dobrém pořadí?

Zadání.

Nevím jestli chápu zadání správně, ale podle podmínek je řešení vzít nejmenší kousek a ostatní v libovolném pořadí odečíst, tím vyjde záporná délka :-D.

2-3-5-6 = -12

a vlastně proč neodečíst už i první číslo?

-2-3-5-6 = -14

Problem solved :-D

Nechápeš to správně, tohle znamená, že jsi našel řešení s délkou 14.

j

Re:Algoritmus pro skládání kousků dřeva
« Odpověď #29 kdy: 09. 06. 2016, 11:07:15 »
Takze ...

1) nebude to kratsi nez nejdelsi
2) rozhodne to nebude delsi nez trojnasobek nejdelsiho (muzou tam byt dva nejdelsi dilky vedle sebe a pak to samo muze prelizt i dvojnasobek jejich dylky proste proto, ze pred nimam mam jeste dalsi dilek ...)
3) v idealnim pripade to nebude delsi nez nejdelsi

Vemu dylku nejdelsiho a pokusim se ostatni skladat tak, aby tu dylku neprelezly (coz se asi nepovede) => pocet iteraci odpovidajicih maximalne poctu dilku. Jenoduse pokud by polozeni dilku melo prelizt stanovenou dylku, tak ho polozim opacne.

Ve druhym kroku (pripadne se to da udelat i v prubehu prvni iterace v okamziku, kdy uz nenajdu reseni pro kratsi variantu, ale to mi samo znemozni preskladat uz poskladany dilky) tu dylku prodlouzim (pokud sou soucasti po centimetru tak trebas o ten centimetr nebo nasobek) a zopaknu hledani.

Nenajdu tak mozna idealni reseni, ale najdu reseni pomerne rychle. A navic vim predem do jaky dylky se vejdu.