Posted By: Xyster (X! [({})]) on 'CZriddles'
Title:     Re: Algoritmus na idealni obsazeni plochy
Date:      Wed Jun  7 18:22:23 2000

> 
> Jeste upresneni problemu (resp. co potrebuji):
> Nepotrebuji tak uplne definitivni algoritmus, jako spis mozny zpusob reseni
> ci
> hledani reseni.
> Velikosti nejsou vzajemne v zadnem pomeru a nevim jak jinak hledat
> vysledek, nez postupnym pokladanim obdelniku. (Zatim vzdy polozim nejaky
> obdelnik a prepocitam si volne misto - pak zjistim, co se tam vejde a znovu
> neco polozim...)
> Akorat, ze druhu podlozek a obdelniku jsou desitky a jejich pocet muze byt
> nekolik tisic, takze zkouset vsechny kombinace proste nezvladam (kdyz se na
> desku vejde treba 30 obdelniku, kterych je jich 10 druhu...)
> Jestli nekoho napada lepsi zpusob reseni (a prozradi ho), budu vdecen.
Jestli je to teoreticka uloha, tak je to proste NP-uplny problem. Tudiz reseni 
najdes pro relativne male n brutalni silou. 

Pokud je to prakticka uloha, tak to potom nepotrebujes optimalni rozmisteni, 
staci pouze nejake dost dobre. Pro to by se snad dala najit nejaka rozumna 
heuristika, jak prohledavat strom reseni. Nebo zjistit vic o vstupnich 
datech, mozna by i kompletni prohledavani mohlo byt za urcitych podminek 
pouzitelne). 

 > > v
> Ceny 
Xyster

42