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

[Vilda]

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!

[Reklama]

[sj]

Myslím že by mohlo pomoci Dynamické Programování (zagooglit, nebo wikipedia).

[kvr kvr]

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]

Metoda Monte Carlo.

[kokoko]

sort. opak merge na split a oscilace.

[Reklama]

[franta PH]

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]

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]

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č]

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č]

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.]

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

[ttt]

http://www.ams.org/samplings/feature-column/fcarc-links5

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]

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.

[gl]

https://ecommons.cornell.edu/bitstream/handle/1813/6326/82-486.pdf?sequence=1&isAllowed=y

[Jenda]

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.