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

Vilda

Algoritmus pro skládání kousků dřeva
« kdy: 08. 06. 2016, 15:16:16 »
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!


sj

Re:Algoritmus pro skládání kousků dřeva
« Odpověď #1 kdy: 08. 06. 2016, 15:24:55 »
Myslím že by mohlo pomoci Dynamické Programování (zagooglit, nebo wikipedia).

Re:Algoritmus pro skládání kousků dřeva
« Odpověď #2 kdy: 08. 06. 2016, 15:29:07 »
Na první pohled bych řekl, že jde o NP-úplný problém, takže rychlé a spolehlivé řešení neexistuje.

Nicméně celkem dobré výsledky bude dávat následující:

1. seřadit podle hodnoty
2. odebrat ze seznamu nejvyšší hodnotu a přičíst (pokud je aktuální suma záporná) či odečíst (je-li aktuální suma kladná)
3. loop until seznam empty

Karbous

Re:Algoritmus pro skládání kousků dřeva
« Odpověď #3 kdy: 08. 06. 2016, 16:18:14 »
Metoda Monte Carlo.

kokoko

Re:Algoritmus pro skládání kousků dřeva
« Odpověď #4 kdy: 08. 06. 2016, 16:22:17 »
sort. opak merge na split a oscilace.


franta PH

Re:Algoritmus pro skládání kousků dřeva
« Odpověď #5 kdy: 08. 06. 2016, 16:43:53 »
Možná, že to počítám špatně, ale místo
3 + 5 + 2 - 6 -> délka 10
by mělo být
3 + 5 + 2 - 6 -> délka 4
atd.

dffffffff

Re:Algoritmus pro skládání kousků dřeva
« Odpověď #6 kdy: 08. 06. 2016, 16:51:38 »
Možná, že to počítám špatně, ale místo
3 + 5 + 2 - 6 -> délka 10
by mělo být
3 + 5 + 2 - 6 -> délka 4
atd.

spatne pocitas. 3, 5, 2 Vedle sebe dava 10, tycka 6 polozena naopak delku nezmeni.

zdenek henek nereg

Re:Algoritmus pro skládání kousků dřeva
« Odpověď #7 kdy: 08. 06. 2016, 21:19:26 »
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!

Nejsem si uplne jisty, ale podivejte se na toto https://docs.jboss.org/drools/release/5.4.0.Final/drools-planner-docs/html_single/

Jinak pokud netrvate na tom nejlepsim, ale stacilo by nejake prijatelne reseni, tak se podivejte i na geneticke algortimy
Zakodovat plus a minus jako jedna a nula, fitness by pak provedla zjisteni delky...

Michal Kovačič

Re:Algoritmus pro skládání kousků dřeva
« Odpověď #8 kdy: 08. 06. 2016, 22:00:20 »
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ů.

Je možné, že jsem špatně pochopil zadání - ale nejmenší délka složeného útvaru bude rovna právě délce nejdelšího z kusů. Na to stačí max(...)

Michal Kovačič

Re:Algoritmus pro skládání kousků dřeva
« Odpověď #9 kdy: 08. 06. 2016, 22:07:58 »
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ů.

Je možné, že jsem špatně pochopil zadání - ale nejmenší délka složeného útvaru bude rovna právě délce nejdelšího z kusů. Na to stačí max(...)
Hmmm - nebo možná ne, jak tak nad tím přemýšlím - omlouvám se...

Radovan.

Re:Algoritmus pro skládání kousků dřeva
« Odpověď #10 kdy: 08. 06. 2016, 22:25:59 »
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).
V čem to generuješ? Nedávno kamarád řešil jeden problém v Matlabu, a pro srovnání rychlosti si to cvičně naprogramoval i ve Fortranu 90. Neřekl mi přesně kolikrát rychlejší ten Fortran byl, ale prý to číslo mělo pět nul 8)

ttt

Re:Algoritmus pro skládání kousků dřeva
« Odpověď #11 kdy: 08. 06. 2016, 23:37:30 »
http://www.ams.org/samplings/feature-column/fcarc-links5

Citace
What John Hopcroft, Deborah Joseph, and Sue Whitesides accomplished was to show that the ruler folding problem is NP-complete. This was done by showing that it was as easy or hard as the problem known as the set partition problem, which is known to be NP-complete. Set partition is the following problem: given n positive integer weights (which may not all be distinct), determine if the weights can be divided into two sets X and Y such that the sum of the elements in X is exactly equal to the sum of the elements in Y. By contrast, Hopcroft, Joseph, and Whitesides showed that the problem of determining whether a chain linkage with exactly m links and where each of the links is at most M units long will fit into a case of size at most K can be solved with an algorithm which takes a linear amount of time in the number of links!

TLDR: Je to NP-úplný problém. Omezíš-li maximální délku úseku, stane se z něj lineární v počtu úseků.

btcx2

Re:Algoritmus pro skládání kousků dřeva
« Odpověď #12 kdy: 09. 06. 2016, 00:24:28 »
Ja bych se vubec nebal normalniho backtrackingu, velice rychle se dostanete k nejakemu rozumnemu vysledku.
I pro tech 50 drivek klidne muzete projit vsecky za mesic na desktopu, kdyz to hodite na GPU tak za pul hodky.
Al pokud nepotrebujete absolutni minimum, tak rozumnej vysledek bude mnohem driv.


Jenda

Re:Algoritmus pro skládání kousků dřeva
« Odpověď #14 kdy: 09. 06. 2016, 05:17:19 »
I pro tech 50 drivek klidne muzete projit vsecky za mesic na desktopu, kdyz to hodite na GPU tak za pul hodky.

To se mi moc nezdá, pro GPU s 2048 jádry na 1 GHz to znamená, že máš 3 takty na pokus, ale jenom zjištění jak dobré to řešení je potřebuje 5-6 instrukcí. Na druhou stranu je pravda, že na GPU máš typicky 4x32b vektory (možná některé už umí i 8x32).

Mně ale přijde, že tohle je školní úloha a cílem má být nějaký pseudopolynomiální algoritmus (polynomiální ve velikosti vstupních čísel, nikoli v jejich bitové délce). Jsem na tohle ale strašná lama a nic mě nenapadlo.