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

[j]

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? 

Cokl je primitivni ... protoze beha tu hodinu ... co de pan domu ... . Teda ... pokud pominu ze se asi nezvladne v nulovym case otocit pri tech 10km/h ...

[Reklama]

[.]

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((l₁+l_n), l₂+l_n-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

[gl]

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((l₁+l_n), l₂+l_n-1),...)

To je blbost. zkuste si takhle složit metr o délkách 3 2 4

[gl]

ještě snad už poslední oprava.

Kód: [Vybrat]

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))


[gl]

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.

[Reklama]

[kokoko]

dokaze nekdo najit protipriklad k tvrzeni:

nejdelsi dva kousky se budou alespon dotykat nebo prekryvat

[gl]

dokaze nekdo najit protipriklad k tvrzeni:

nejdelsi dva kousky se budou alespon dotykat nebo prekryvat

To tvrzení je pravdivé.

[mareolan]

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 ) 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í).

[mareolan]

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

[gl]

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

[gl]

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 ) 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ů.

[Vilda]

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)

[Vilda]

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?

[gl]

V zadání se neříká, že můžeš změnit pořadí těch dřívek.

[JardaA]

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.