[OT] Jak narezat trubky?

[Slavomir Skopalik]

Ano, ale tohle jiz neni hrubou silou kompletni prohledani vsech kombinaci.
Resil jsem to podobne, na zacatku jsem vybral nejvetsi dil (mel jsem
jednotny prostor,
coz byla velke vyhoda) a k nemu se hledala kombinace stehnych, nebo mensich.

U optimalizatoru baliku mam pak zcela pravidlovy algoritmus, jenz postupne
iteruje.
Pokud v ramci iterace nedokaze provest presun, jenz by vedl k lepsi
ohodnocovaci funkci,
tak iterovani konci. Cele to bylo doplneno editorem pro lidsky zasah (ruzne
specialni pozadavky
na baleni, ...). Charakter ulohy zajistuje, ze slozitost neroste rychleji,
nez n^2.

U ulohy slucovani kratkych rezu jsem si na nic nehral a udelal to uplne
jednoduse.
Ukol: 
  pospojovat kratke rezy tak, aby je zvladla automatika s tim, ze se pak
narezou rucne. Cil optimalizace, minimum zmetku, minimum lidske prace.

Reseni:
 setridit kratk rezy od nekratsiho po nejdelsi a doplnovat k nejdelsimu
nejkratsi do doby, nez bude splnovat minimalni delku.

V realu to bylo trochu slozitejsi (zakazka na jeden kratky rez a podobne).
Hlavni vyhoda je zde obrovska rychlost, jenz byla take jednim z dulezitych
kriterii.

Slavek

Ing. Slavomir Skopalik
Jednatel spolecnosti
Elekt Labs s.r.o.
Sber a vyhodnoceni dat ze stroju a laboratori 
systemem MASA (http://www.elektlabs.cz/m2demo)
----------------------------------------------
Adresa:
Elekt Labs s.r.o.
Chaloupky 158
783 72 Velky Tynec
Czech Republic
----------------------------------------------
Mobil: +420 724 207 851
icq:199 118 333
e-mail:skopalik na elektlabs.cz
http://www.elektlabs.cz
 


> Neni to tak zle. Tohle jsem jednou resil (a zdrojak nemuzu 
> najit, jinak bych to poslal). Algoritmus jsem si "vycucal z 
> prstu", nejak se tam nahodne sestavovaly ty prirezy a kdyz 
> byl jeden polotovar skoro dobre tak se slo na dalsi, kdyz se 
> to nedarilo tak se nejaky nahodne rozboural a zkouselo se to 
> jinak. Obvykle se behem par vterin az minut naslo prijatelne 
> reseni velmi blizke optimalnimu a vyrazne lepsi nez co byli 
> schopni rucne sestavit na dilne. A taky slo o desitky tyci a 
> stovky prirezu.
> 
> Ales Prochaska
> 
> >> Jste si jisty? Podle me staci O(n^k). Nepotrebuju zkouset
> >> vsechny permutace, ale staci mi treba nerostouci delka kusu 
> >> (prehazeni mi nic
> >> neprinese)
> 
> > Ano zde mate pravdu.