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

Jenda

Re:Algoritmus pro skládání kousků dřeva
« Odpověď #30 kdy: 09. 06. 2016, 11:29:12 »
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.

Kód: [Vybrat]
+--------------> 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 :)


Re:Algoritmus pro skládání kousků dřeva
« Odpověď #31 kdy: 09. 06. 2016, 11:30:15 »
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...

Jenda

Re:Algoritmus pro skládání kousků dřeva
« Odpověď #32 kdy: 09. 06. 2016, 11:49:21 »
OK, už mi došlo, že počítám, kde může být konec, ne jaká je cestou maximální délka.

Karel

Re:Algoritmus pro skládání kousků dřeva
« Odpověď #33 kdy: 09. 06. 2016, 13:09:39 »
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?

Karbous

Re:Algoritmus pro skládání kousků dřeva
« Odpověď #34 kdy: 09. 06. 2016, 13:16:14 »
Neplati to pro zadani tazatele, rekl bych. 
Poradi dilku je imo dane a nelze je "prehazet".


Karel

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

ByCzech

  • *****
  • 1 806
    • Zobrazit profil
    • E-mail
Re:Algoritmus pro skládání kousků dřeva
« Odpověď #36 kdy: 09. 06. 2016, 16:39:51 »
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í ;-).

Logik

  • *****
  • 863
    • Zobrazit profil
    • E-mail
Re:Algoritmus pro skládání kousků dřeva
« Odpověď #37 kdy: 09. 06. 2016, 17:03:11 »
Citace
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])


« Poslední změna: 09. 06. 2016, 17:05:46 od Logik »

Logik

  • *****
  • 863
    • Zobrazit profil
    • E-mail
Re:Algoritmus pro skládání kousků dřeva
« Odpověď #38 kdy: 09. 06. 2016, 17:16:02 »
Teda stačí i kratší matice, bez záruky bych si tipnul 1.5*max(d[k])

Re:Algoritmus pro skládání kousků dřeva
« Odpověď #39 kdy: 09. 06. 2016, 20:31:44 »
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].

mareolan

Re:Algoritmus pro skládání kousků dřeva
« Odpověď #40 kdy: 09. 06. 2016, 23:03:59 »
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.

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/. Tato aproximace pro tvůj úvodní příklad optimální řešení nenalezne...
Kód: [Vybrat]
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/

gl

Re:Algoritmus pro skládání kousků dřeva
« Odpověď #41 kdy: 10. 06. 2016, 04:39:42 »
Implementace pseudopolynomiálního algoritmu z toho článku, který jsem postoval včera. Snad je to správně.

Kód: [Vybrat]
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)

gl

Re:Algoritmus pro skládání kousků dřeva
« Odpověď #42 kdy: 10. 06. 2016, 04:55:49 »
oprava, vypadl mi řádek.

Kód: [Vybrat]
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)


PetrM

Re:Algoritmus pro skládání kousků dřeva
« Odpověď #43 kdy: 10. 06. 2016, 09:26:24 »
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),...)

PetrM

Re:Algoritmus pro skládání kousků dřeva
« Odpověď #44 kdy: 10. 06. 2016, 09:32:51 »
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)