Fórum Root.cz
Hlavní témata => Vývoj => Téma založeno: Vilda 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!
-
Myslím že by mohlo pomoci Dynamické Programování (zagooglit, nebo wikipedia).
-
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
-
Metoda Monte Carlo.
-
sort. opak merge na split a oscilace.
-
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.
-
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.
-
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...
-
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(...)
-
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...
-
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)
-
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ů.
-
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.
-
https://ecommons.cornell.edu/bitstream/handle/1813/6326/82-486.pdf?sequence=1&isAllowed=y
-
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 (http://www.geeksforgeeks.org/compute-the-minimum-or-maximum-max-of-two-integers-without-branching/) 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.
-
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ží)
-
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 :)
-
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
-
nestačí to překládat vždy v polovině?
-
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...
-
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...
-
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.
-
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 (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 (https://en.wikipedia.org/wiki/Genetic_algorithm), nebo pravidlový inferenční stroj případně jejich kombinaci.
-
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
-
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
-
mozno by sa tvoja uloha dala preformulavat na nieco taketo
https://en.wikipedia.org/wiki/Cutting_stock_problem (https://en.wikipedia.org/wiki/Cutting_stock_problem)
resp. niektore s rieseni prisposobit tvojej ulohe
doriesit by ju potom nemal byt problem
-
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...
-
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
-
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.
-
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.
-
Napadl mě algoritmus polynomiální ve velikosti součtu délek (tj. to čemu na Wikipedii říkají pseudo-polynomial).
Značení:
l_i .. délka dřívka i
N .. počet dřívek
M .. součet délek dřívek
Naalokuj si bitmapu MxN a nastav ji na nuly.
+--------------> M
|00000000000000
|00000000000000
|00000000000000
v
N
V bitmapě na souřadnicích [m,n] bude jednička, pokud se délky m dá dosáhnout použitím dřívek 1..n.
V prvním řádku tedy bude jednička na pozici l_1.
Ve druhém řádku bude jednička na pozicích abs(l_1-l_2) a abs(l_1+l_2).
Na i. řádku budou jedničky na pozicích abs(x-l_i) a abs(x+l_i) kde x jsou pozice jedniček na i-1. řádku.
Výsledek je nejlevější jednička na posledním řádku.
Složitost: NxM paměti i času. Podle konkrétního zadání se může stát, že bitmapa bude velmi řídká, a šlo by ji uložit nějak inteligentněji.
Podle j-ova pozorování nemusí být bitmapa široká M, ale stačí 3*max(l) a neperspektivní větve rovnou zahazovat.
...
Pokud by nám stačilo rychlé nalezení aproximace, zkusil bych prasárnu:
- Napíšeme to jako mixed-integer program
- Pustíme na to lineární optimizér
- Zaokrouhlíme
- Třeba to nějak dopadne :)
-
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
Já vím, že existují protipříklady, proto jsem "lineární obvykle fungující implementace v případě rozumné distribuce". Nelze (aspoň si to zatím celý svět myslí) vyřešit NP-úplný problém v rozumném čase.
Nicméně, jak podotknul "j", v zásadě by tento případ vylepšilo nastavení "end" na délku maximálního dílku. Nicméně některé zase zhorší: 1+1-4 místo 1-1+4. V zásadě jde o to před největším dílkem dostat se na 0 nebo na max...
-
OK, už mi došlo, že počítám, kde může být konec, ne jaká je cestou maximální délka.
-
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.
Máte pravdu.
Jen bych doplnil, že to dobré pořadí může být například +5 -4 +2. Jako první položím ten nejdelší. A pak odečtu ten druhý nejdelší. Tím se dostanu směrem k počátku. Pokud se mohou délky opakovat, tak v nejkrajnějším případě opět do počátku. Jako další opět přičtu. Tím se opět dostanu dopředu, ale ne dále, než odkud začínal ten druhý dílek. A opět odečtu atd.
Takže algoritmus je snadný:
1. Seřadím dílky podle délky vzestupně
2. U lichých dílků dám znaménko +, u sudých znaménko -
Tím jsem získal optimální řešení, kde celková délka použitého prostoru je rovna délce nejdelšího dílku.
Použitý prostor:
X1 až Xn jsou dílky
D1 až Dn jsou jejich délky
Un je pozice, kde začíná dílek Dn, respektive končí dílek D(n-1)
1. První dílek dám plusem od nuly, U1 = 0, U2 = D1
2. Sudý dílek Xn dám mínusem od dílku X(n-1). Počátek je na Un a konec na Un-Dn
3. Lichý dílek Xn dám plusem od dílku X(n-1). Počátek je Un a konec na Un+Dn
Pro všechna n>= 2 sudá platí, že U(n-1) <= U(n+1) < Un
Pro všechna n> 2 lichá platí, že Un < U(n+1) <= U(n-1)
Z toho vyplývá, že začátek dalšího dílku (ani konec) nemůže být mimo oblast, kde byl dílek předchozí.
Jinak řečeno, když to mám seřazené, tak se žádný dílek nemůže návratem dostat jinam, než kde už byl ten předchozí.
Najde někdo nějaké zadání, pro které by to neplatilo?
-
Neplati to pro zadani tazatele, rekl bych.
Poradi dilku je imo dane a nelze je "prehazet".
-
Neplati to pro zadani tazatele, rekl bych.
Poradi dilku je imo dane a nelze je "prehazet".
Máte pravdu. Tenhle zásadní detail mi utekl, že pořadí je dáno na vstupu a já jen mohu měnit znaménka, nikoliv pořadí. Tak to pak beru zpět, to jsme opravdu u NP úplné úlohy. Ale aspoň to bude zajímavější.
-
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á to samozřejmě pochopil, že záporná délka neexistuje a není ji proto možné aplikovat, snažil jsem se upozornit na nedostatky v zadání a nutnost pamatovat na takovéto věci v algoritmu, protože počítač neřeší dřívka, ale čísla a pro něj je co největší záporné číslo určitě nejmenší a proto správný výsledek, dle zadání, které není jednoznačné ;-). Dělám často analýzy zadání a tohle se děje běžně. To co je pro jednoho jasné, dává jinému hromadu možností ;-).
-
Napadl mě algoritmus polynomiální ve velikosti součtu délek (tj. to čemu na Wikipedii
říkají pseudo-polynomial).
To nefunguje - pokud se v posledním kroku vrátíš zpět, tak Ti vyjde délka kratší než máš mít. Musíš to modifikovat
Udělám matici n,m, kde
a_{n,m} udává nejmenší možnou délku pro konfiguraci kdy s n dřevy mi poslední končí na pozici m.
(Předpokládám přitom vždy že nějaký klacek v řešení dosáhne vlevo nuly - řešení zasahující do mínusu najdu správně zarovnané o políčko vpravo a naopak).
V nultém řádku začnu s a[n,m]= n.
V kroku k s dřevem délky d[k] pak nastavím
for(i = 0 to m):
if i+d[k] < m:
a[k+1,i+k[d],m] = max(a[k,i],i+d[k])
if i-d[k]>=0:
a[k+1,i-k[d],m] = min(a[k+1][i-k[d]], a[k,i])
Dál se to dá vylepšit tak, že některé kombinace jsou předem nesmyslné - konkrétně matice stačí být dlouhá 2*max(d[k]) a ne sum(d[k])
-
Teda stačí i kratší matice, bez záruky bych si tipnul 1.5*max(d[k])
-
Já to samozřejmě pochopil, že záporná délka neexistuje a není ji proto možné aplikovat, snažil jsem se upozornit na nedostatky v zadání a nutnost pamatovat na takovéto věci v algoritmu, protože počítač neřeší dřívka, ale čísla a pro něj je co největší záporné číslo určitě nejmenší a proto správný výsledek, dle zadání, které není jednoznačné ;-). Dělám často analýzy zadání a tohle se děje běžně. To co je pro jednoho jasné, dává jinému hromadu možností ;-).
Zadání je naprosto v pořádku. Pokud zákazníkovi běžně tvrdíte, že skřín měří 50cm a z druhého konce -50cm, bude problém někde jinde [než u zákazníka].
-
Jde o tzv. "The carpenter’s ruler folding problem" - viz např. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.65.3016&rep=rep1&type=pdf (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.65.3016&rep=rep1&type=pdf).
Skládání v 1-D, t.j. "na přímce", je NP-Complete, takže můžeš akorát zkusit brute-force. Pokud jsou délky kladná celá čísla, tak se výsledek pohybuje v rozmezí [M, 2*M-1], kde M je největší z délek. Příklad: [4,3,4,3,4,3,4] => 7
Jedna z nejjednodušších aproximací je v lineárním čase - začnu v bodě 0, pokud další délku dokážu položit doleva, aniž bych přešel do záporných čísel, tak ji tam položím, jinak ji položím doprava - https://jsfiddle.net/p4m1ta0h/1/ (https://jsfiddle.net/p4m1ta0h/1/). Tato aproximace pro tvůj úvodní příklad optimální řešení nenalezne...
var a = [3,5,2,6];
var len = a[0] || 0;
var pos = a[0] || 0;
var path = (a.length ? [a[0]] : []);
for (var i=1; i<a.length; ++i) {
if (pos - a[i] < 0) pos += a[i], path.push('+', a[i]);
else pos -= a[i], path.push('-', a[i]);
len = Math.max(len, pos);
}
console.log('Minimal length (approximation):', len);
console.log('Folding:', path.join(" "));
Ukázka brute-force: https://jsfiddle.net/wmxfxshL/ (https://jsfiddle.net/wmxfxshL/)
-
Implementace pseudopolynomiálního algoritmu z toho článku, který jsem postoval včera. Snad je to správně.
def table(k, ruler):
rows = [[False] * (ruler[0] - 1) + [True] * (k - ruler[0] + 1)]
for item in ruler[1:]:
newrow = [False] * k
for j in range(k):
if j - item >= 0 and rows[-1][j - item]:
newrow[j] = True
if j + item < k and rows[-1][j + item]:
newrow[j] = True
rows.append(newrow)
return rows
def bactrace(table, ruler):
last = table[-1].index(True)
res = []
for i, item in reversed(list(enumerate(ruler))[1:]):
if last - item >= 0 and table[i - 1][last - item]:
last = last - item
res.append((item, '+'))
else:
res.append((item, '-'))
res.append((ruler[0], '+'))
return list(reversed(res))
def find_folding(ruler):
maxlen = max(ruler)
for k in range(maxlen, maxlen*2 + 1):
t = table(k, ruler)
if any(t[-1]):
bt = bactrace(t, ruler)
return bt
if __name__ == '__main__':
ruler = [3, 5, 2, 6]
print find_folding(ruler)
-
oprava, vypadl mi řádek.
def table(k, ruler):
rows = [[False] * (ruler[0] - 1) + [True] * (k - ruler[0] + 1)]
for item in ruler[1:]:
newrow = [False] * k
for j in range(k):
if j - item >= 0 and rows[-1][j - item]:
newrow[j] = True
if j + item < k and rows[-1][j + item]:
newrow[j] = True
rows.append(newrow)
return rows
def bactrace(table, ruler):
last = table[-1].index(True)
res = []
for i, item in reversed(list(enumerate(ruler))[1:]):
if last - item >= 0 and table[i - 1][last - item]:
last = last - item
res.append((item, '+'))
else:
last = last + item
res.append((item, '-'))
res.append((ruler[0], '+'))
return list(reversed(res))
def find_folding(ruler):
maxlen = max(ruler)
for k in range(maxlen, maxlen*2 + 1):
t = table(k, ruler)
if any(t[-1]):
bt = bactrace(t, ruler)
return bt
if __name__ == '__main__':
ruler = [3, 5, 2, 6]
print find_folding(ruler)
-
Pokud je to jako skládací metr, tak jsou tři možnosti:
a) Rozloženo, potom je délka prostým součtem. Ten je komutativní a distributivní, takže na pořadí nějak nezáleží, že... Sečíst v cyklu a je to.
b) Složeno. Tam se dá předpokládat, že při minimu to bude po jednom a pak z toho vždycky bude trčet ten nejdelší. Takže projít v cyklu a najít nejdelší.
c) S upřesněním zadání, třeba že budou po dvojicích rozloženy a pak složeno a podobně*. Tam to tazatel nespecifikoval, takže se tím nemusíme zabývat. A tam už se musí trochu myslet, že.
*) Tam zase stačí úplně normálně setřidit seznam. Nejdelší bude trčet, za ním pro minimální délku bude nejkratší. Ale druhý nejkratší + druhý nejdelší může hodit větší číslo, takže tam by po setřídění platilo max((l1+ln), l2+ln-1),...)
-
Jo a mimochodem, znáte podobnou úlohu o psu a pánovi? V deset večer vyrazil muž z hospody domů rychlostí 5km/h. Domov je vzdálený 5km. Šel s ním jeho pes, který utíkal domů rychlostí 10km/h a když doběhl domů, otočil se a stejnou rychlostí běžel pánovi naproti. Když jej potkal, opět se otočil k domovu. Kolik kilometrů pes uběhl? 8)
-
Jo a mimochodem, znáte podobnou úlohu o psu a pánovi? V deset večer vyrazil muž z hospody domů rychlostí 5km/h. Domov je vzdálený 5km. Šel s ním jeho pes, který utíkal domů rychlostí 10km/h a když doběhl domů, otočil se a stejnou rychlostí běžel pánovi naproti. Když jej potkal, opět se otočil k domovu. Kolik kilometrů pes uběhl? 8)
Cokl je primitivni ... protoze beha tu hodinu ... co de pan domu ... ;D. Teda ... pokud pominu ze se asi nezvladne v nulovym case otocit pri tech 10km/h ... ;D
-
Pokud je to jako skládací metr, tak jsou tři možnosti:
a) Rozloženo, potom je délka prostým součtem. Ten je komutativní a distributivní, takže na pořadí nějak nezáleží, že... Sečíst v cyklu a je to.
b) Složeno. Tam se dá předpokládat, že při minimu to bude po jednom a pak z toho vždycky bude trčet ten nejdelší. Takže projít v cyklu a najít nejdelší.
c) S upřesněním zadání, třeba že budou po dvojicích rozloženy a pak složeno a podobně*. Tam to tazatel nespecifikoval, takže se tím nemusíme zabývat. A tam už se musí trochu myslet, že.
*) Tam zase stačí úplně normálně setřidit seznam. Nejdelší bude trčet, za ním pro minimální délku bude nejkratší. Ale druhý nejkratší + druhý nejdelší může hodit větší číslo, takže tam by po setřídění platilo max((l1+ln), l2+ln-1),...)
Možná by bylo dobré, než sem začnete dávat nějaké návrhy řešení, si třeba vytvořit nějaký (stačí velmi malý) praktický příklad. Pak byste hned viděli, že jste úplně mimo.
Takže třeba ten příklad: 4, 2, 5
-
Pokud je to jako skládací metr, tak jsou tři možnosti:
a) Rozloženo, potom je délka prostým součtem. Ten je komutativní a distributivní, takže na pořadí nějak nezáleží, že... Sečíst v cyklu a je to.
b) Složeno. Tam se dá předpokládat, že při minimu to bude po jednom a pak z toho vždycky bude trčet ten nejdelší. Takže projít v cyklu a najít nejdelší.
c) S upřesněním zadání, třeba že budou po dvojicích rozloženy a pak složeno a podobně*. Tam to tazatel nespecifikoval, takže se tím nemusíme zabývat. A tam už se musí trochu myslet, že.
*) Tam zase stačí úplně normálně setřidit seznam. Nejdelší bude trčet, za ním pro minimální délku bude nejkratší. Ale druhý nejkratší + druhý nejdelší může hodit větší číslo, takže tam by po setřídění platilo max((l1+ln), l2+ln-1),...)
To je blbost. zkuste si takhle složit metr o délkách 3 2 4
-
ještě snad už poslední oprava.
def table(k, ruler):
rows = [[False] * ruler[0] + [True] * (k - ruler[0])]
for item in ruler[1:]:
newrow = [False] * k
for j in range(k):
if j - item >= 0 and rows[-1][j - item]:
newrow[j] = True
if j + item < k and rows[-1][j + item]:
newrow[j] = True
rows.append(newrow)
return rows
def bactrace(table, ruler):
last = table[-1].index(True)
res = []
for i, item in reversed(list(enumerate(ruler))[1:]):
if last - item >= 0 and table[i - 1][last - item]:
last = last - item
res.append((item, '+'))
else:
last = last + item
res.append((item, '-'))
res.append((ruler[0], '+'))
return list(reversed(res))
def find_folding(ruler):
maxlen = max(ruler)
for k in range(maxlen, maxlen*2 + 1):
t = table(k, ruler)
if any(t[-1]):
bt = bactrace(t, ruler)
return k - 1, bt
def format_folding(res):
return ' '.join(['%s %s ' % (sign, item) for item, sign in res[1]])
if __name__ == '__main__':
ruler = [3, 5, 2, 6]
print format_folding(find_folding(ruler))
-
Skládání v 1-D, t.j. "na přímce", je NP-Complete, takže můžeš akorát zkusit brute-force.
V tom článku na který odkazujete je napsáno, že existuje pseudopolynomiální algoritmus se složitostí O(L^2n), kde L je délka nejdelší části. Je tam reference na článek, který jsem poslal já. Ten algoritmus dává narozdíl od vašeho vždy správný výsledek.
-
dokaze nekdo najit protipriklad k tvrzeni:
nejdelsi dva kousky se budou alespon dotykat nebo prekryvat
-
dokaze nekdo najit protipriklad k tvrzeni:
nejdelsi dva kousky se budou alespon dotykat nebo prekryvat
To tvrzení je pravdivé.
-
Skládání v 1-D, t.j. "na přímce", je NP-Complete, takže můžeš akorát zkusit brute-force.
V tom článku na který odkazujete je napsáno, že existuje pseudopolynomiální algoritmus se složitostí O(L^2n), kde L je délka nejdelší části. Je tam reference na článek, který jsem poslal já. Ten algoritmus dává narozdíl od vašeho vždy správný výsledek.
Ano, máte pravdu. Z nějakého důvodu jsem si (včera večer ;D) o NP úlohách myslel, že jdou řešit pouze pomocí brute-force, což samozřejmě neplatí.
Váš algoritmus mi přijde logicky správný, jen se mi v ukázce nezdá "return k - 1, bt" - asi by to mělo spíš vracet "k, bt" (jestli to čtu správně a má to vracet nalezenou délku, i když se to pak vlastně nezobrazí).
-
..., jen se mi v ukázce nezdá "return k - 1, bt" - asi by to mělo spíš vracet "k, bt" (jestli to čtu správně a má to vracet nalezenou délku, i když se to pak vlastně nezobrazí).
Na druhý pohled, beru zpět ::).
-
..., jen se mi v ukázce nezdá "return k - 1, bt" - asi by to mělo spíš vracet "k, bt" (jestli to čtu správně a má to vracet nalezenou délku, i když se to pak vlastně nezobrazí).
Na druhý pohled, beru zpět ::).
Psal jsem to narychlo a ten kod neni moc citelny. Za to se omlouvam. Je to k - 1, protoze k je pocet koncovych bodu a k -1 je tedy delka.
-
Skládání v 1-D, t.j. "na přímce", je NP-Complete, takže můžeš akorát zkusit brute-force.
V tom článku na který odkazujete je napsáno, že existuje pseudopolynomiální algoritmus se složitostí O(L^2n), kde L je délka nejdelší části. Je tam reference na článek, který jsem poslal já. Ten algoritmus dává narozdíl od vašeho vždy správný výsledek.
Ano, máte pravdu. Z nějakého důvodu jsem si (včera večer ;D) o NP úlohách myslel, že jdou řešit pouze pomocí brute-force, což samozřejmě neplatí.
Váš algoritmus mi přijde logicky správný, jen se mi v ukázce nezdá "return k - 1, bt" - asi by to mělo spíš vracet "k, bt" (jestli to čtu správně a má to vracet nalezenou délku, i když se to pak vlastně nezobrazí).
Záleží na tom, jaký je rozsah hodnot těch délek. Pokud by to byla velká čísla, tak to jde jen brute force. Podobným způsobem se dá řešit například problém batohu nebo problém dvou loupežníků.
-
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ží)
No, to není úplně pravda, zkus si složit 5, 4 a 5 -> to 5 nebude... (5 - 4 + 5 je 6)
-
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ží)
Dílky jsou spojené, jako metr. Tedy v zadání je dáno, že nelze měnit pořadí.
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.
Máte pravdu.
Jen bych doplnil, že to dobré pořadí může být například +5 -4 +2. Jako první položím ten nejdelší. A pak odečtu ten druhý nejdelší. Tím se dostanu směrem k počátku. Pokud se mohou délky opakovat, tak v nejkrajnějším případě opět do počátku. Jako další opět přičtu. Tím se opět dostanu dopředu, ale ne dále, než odkud začínal ten druhý dílek. A opět odečtu atd.
Takže algoritmus je snadný:
1. Seřadím dílky podle délky vzestupně
2. U lichých dílků dám znaménko +, u sudých znaménko -
Tím jsem získal optimální řešení, kde celková délka použitého prostoru je rovna délce nejdelšího dílku.
Použitý prostor:
X1 až Xn jsou dílky
D1 až Dn jsou jejich délky
Un je pozice, kde začíná dílek Dn, respektive končí dílek D(n-1)
1. První dílek dám plusem od nuly, U1 = 0, U2 = D1
2. Sudý dílek Xn dám mínusem od dílku X(n-1). Počátek je na Un a konec na Un-Dn
3. Lichý dílek Xn dám plusem od dílku X(n-1). Počátek je Un a konec na Un+Dn
Pro všechna n>= 2 sudá platí, že U(n-1) <= U(n+1) < Un
Pro všechna n> 2 lichá platí, že Un < U(n+1) <= U(n-1)
Z toho vyplývá, že začátek dalšího dílku (ani konec) nemůže být mimo oblast, kde byl dílek předchozí.
Jinak řečeno, když to mám seřazené, tak se žádný dílek nemůže návratem dostat jinam, než kde už byl ten předchozí.
Najde někdo nějaké zadání, pro které by to neplatilo?
-
V zadání se neříká, že můžeš změnit pořadí těch dřívek.
-
Nějak mi nesedí třetí řádek (resp. varianta skládání) původního zadání:
...
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 8
...
Vychází mi to 12.
-
Nějak mi nesedí třetí řádek (resp. varianta skládání) původního zadání:
...
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 8
...
Vychází mi to 12.
Je to opravdu 12. Je tam chyba.