Forum » Programiranje » Object packing - kakšne ideje?
Object packing - kakšne ideje?
jeti51 ::
Skratka, kolegica me je prosila za pomoč pri seminarski nalogi, ker je ne zna rešiti (glede na nalogo se niti ne čudim). Naloga pa je, da imaš n trikotnikov različih velikosti, podanih z opisom njihovih stranic (a, b in c). Te trikotnike je treba zložiti skupaj tako, da jih zložene lahko postaviš skupaj v čim manjši kvadrat.
Skratka, to je ena izmed verzij t.i. bin-packinga, kot sem bral o tem na internetu. Problem je, da predmeti niso pravokotniki, ampak poljubni trikotniki, torej je nekako več možnosti za postavljanje (pravokotnikov najbrž ni smiselno rotirati za manj koz 90° - postavljati postrani). Gre za off-line varianto, se pravi, da so vsi predmeti znani vnaprej in jih lahko postavljamo v poljubnem vrstnem redu. Prav tako ne gre za "škatlo" s fiksno širino in neskončno višino, ampak za kvadrat. Četudi trikotnike zložiš v lep in zapolnjen pravokotnik, ti to ne pomaga kaj dosti, če ima le-ta zelo različno razmerje stranic.
Ideja bi morda bila, da si na začetku izbereš en dovolj velik kvadrat, noter namečeš trikotnike, potem pa vsakega po malo zavrtiš in premakneš. V naslednjem koraku kvadrat (prostor na voljo) zmanjšaš in ponoviš premikanje in rotiranje trikotnikov, le da je maksimalna dovoljena dolžina premikov zmanjšana. Nekakšno simulirano ohlajanje torej, ker delaš vedno manjše in vedno bolj fine premike trikotnikov, dokler energija sistema ne pade pod določeno raven in se trikotniki skorja ne premikajo več. Podobno kot bilijardni algoritem, samo da pač za trikotnike. Potem pa algoritem pač večkrat poženeš in nato vzameš najboljšo rešitev.
(mimogrede, rešite lahko tudi podobno nalogo z različno velikimi krogi - seminarska od kolegice od te kolegice
).
Ima morda kdo še kakšno drugo idejo, kakšen drug pristop? Recimo s kakšnimi evolucijskimi algoritmi (na kakšen način izvesti genetske operatorje)?
Če pa ima kdo kakšno pametno rešitev, bi bilo lepo, da jo kar napiše, da ne bomo tople vode odkrivali.
Skratka, to je ena izmed verzij t.i. bin-packinga, kot sem bral o tem na internetu. Problem je, da predmeti niso pravokotniki, ampak poljubni trikotniki, torej je nekako več možnosti za postavljanje (pravokotnikov najbrž ni smiselno rotirati za manj koz 90° - postavljati postrani). Gre za off-line varianto, se pravi, da so vsi predmeti znani vnaprej in jih lahko postavljamo v poljubnem vrstnem redu. Prav tako ne gre za "škatlo" s fiksno širino in neskončno višino, ampak za kvadrat. Četudi trikotnike zložiš v lep in zapolnjen pravokotnik, ti to ne pomaga kaj dosti, če ima le-ta zelo različno razmerje stranic.
Ideja bi morda bila, da si na začetku izbereš en dovolj velik kvadrat, noter namečeš trikotnike, potem pa vsakega po malo zavrtiš in premakneš. V naslednjem koraku kvadrat (prostor na voljo) zmanjšaš in ponoviš premikanje in rotiranje trikotnikov, le da je maksimalna dovoljena dolžina premikov zmanjšana. Nekakšno simulirano ohlajanje torej, ker delaš vedno manjše in vedno bolj fine premike trikotnikov, dokler energija sistema ne pade pod določeno raven in se trikotniki skorja ne premikajo več. Podobno kot bilijardni algoritem, samo da pač za trikotnike. Potem pa algoritem pač večkrat poženeš in nato vzameš najboljšo rešitev.
(mimogrede, rešite lahko tudi podobno nalogo z različno velikimi krogi - seminarska od kolegice od te kolegice
).Ima morda kdo še kakšno drugo idejo, kakšen drug pristop? Recimo s kakšnimi evolucijskimi algoritmi (na kakšen način izvesti genetske operatorje)?
Če pa ima kdo kakšno pametno rešitev, bi bilo lepo, da jo kar napiše, da ne bomo tople vode odkrivali.
Thomas ::
north by northwest smo gledal
Zdej pa k zadevi! Najprej razdeliš en dovolj velik kvadrat, tak da gredo vsi trikotniki gor, na fine majhne kvadratke. Recimo na k krat k njih.
Kar delaš zdaj je tole:
Evo to je bruta forca algoritem, ki pa dobro deluje za eno zmerno stevilo trikotnikov in za ne preveč natančno razdelitev kvadrata.
Could be enhanced, however!
Zdej pa k zadevi! Najprej razdeliš en dovolj velik kvadrat, tak da gredo vsi trikotniki gor, na fine majhne kvadratke. Recimo na k krat k njih.
Kar delaš zdaj je tole:
for (i0=0;i0<k;i0++) {
for (j0=0;j0<k;j0++) {
for (i1=0;i1<k;i1++) {
for (j1=0;j2<k;j2++) {
for (i2=0;i2<k;i2++) {
for (j2=0;j2<k;j2++) {
if tocke pridejo na oglišča enega od trikotnikov (z neko toleranco t), dodaj te tri pare v listo položajev!
}
}
}
}
}
}
for (i0=0;i0<polozajev;i0++)
for (i1=0;i1<polozajev;i1++)
for (i2=0;i2<polozajev;i2++)
for (i3=0;i3<polozajev;i3++)
for (i4=0;i4<polozajev;i4++)
if trikotniki se ne pokrivajo & gredov v se manjsi kvadrat - izpisi!
}
}
}
}
Evo to je bruta forca algoritem, ki pa dobro deluje za eno zmerno stevilo trikotnikov in za ne preveč natančno razdelitev kvadrata.
Could be enhanced, however!
Man muss immer generalisieren - Carl Jacobi
Thomas ::
Se reče, najprej zgeneriramo vse možne položaje vseh trikotnikov v gridu, potem pa z zadostikrat gnezdeno for zanko spet vse te položaje preizkušamo. Vsak for ima seveda svoj break, kadarkoli je stranica obsegajočega kvadrata večja od minimuma, kadar se trikotnika prekrivata ...
Potem, ko je zadeva bruta forca tako diskretno rešena, bi se pa dalo narest fine tuning, da bi se liki lepo prilegali.
Potem, ko je zadeva bruta forca tako diskretno rešena, bi se pa dalo narest fine tuning, da bi se liki lepo prilegali.
Man muss immer generalisieren - Carl Jacobi
snow ::
Zanimiv problem. 
Kak preverim, da se dva trikotnika ne prekrivata?
Zaenkrat je ideja da bi pogledal secisca funkcij nosilk stranic...
Za kroge pač gledaš da je razdalja med radijema večja od vstote radijev, genom si napišeš kot pozicijo središča...in potem po mutaciji pogledaš če je pač sedaj manjši kvadrat (maximum od (višina,širina)).
Guliš pač nekaj genomov dost časa, če potem dolgo ni spremembe -> rerun.
Trikotniki so mi malo težji...
Bomo gruntal, dobra vaja za on contest a ne Thomas
Kak preverim, da se dva trikotnika ne prekrivata?
Zaenkrat je ideja da bi pogledal secisca funkcij nosilk stranic...
Za kroge pač gledaš da je razdalja med radijema večja od vstote radijev, genom si napišeš kot pozicijo središča...in potem po mutaciji pogledaš če je pač sedaj manjši kvadrat (maximum od (višina,širina)).
Guliš pač nekaj genomov dost časa, če potem dolgo ni spremembe -> rerun.
Trikotniki so mi malo težji...
Bomo gruntal, dobra vaja za on contest a ne Thomas
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins
snow ::
> najprej zgeneriramo vse možne položaje vseh trikotnikov v gridu
To je dost velik...
(stevilo moznih tock)n * 2
Stevilo moznih tock bi blo stranica kvadrata / natančnost postavljanja.
Me zanima na kako natancnost je treba podati rezultat? So lahko tocke npr (21.32144213,23.321355) ... ?
a,b,c so cela števila al realna? (Sicer nima to veze ampak vseeno :))
Najvecja stranica kvadrata na katerem se nam se spaca iskat je vsota najvecjih stranic trikotnika... right?
To je dost velik...
(stevilo moznih tock)n * 2
Stevilo moznih tock bi blo stranica kvadrata / natančnost postavljanja.
Me zanima na kako natancnost je treba podati rezultat? So lahko tocke npr (21.32144213,23.321355) ... ?
a,b,c so cela števila al realna? (Sicer nima to veze ampak vseeno :))
Najvecja stranica kvadrata na katerem se nam se spaca iskat je vsota najvecjih stranic trikotnika... right?
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins
Thomas ::
Absolutno snow! Mi je pa en tipo pokazal tudi 1 MB praktičnih "vaj", ki jih ima v svoji mašineriji. Presenetljivo podobne contestom in takelim seminarskim! Good!
Man muss immer generalisieren - Carl Jacobi
Thomas ::
Ajd ... bomo tole postavljanje trikotnika zdejle rešili in dali na Crittical site, če nam bo ratalo!
Man muss immer generalisieren - Carl Jacobi
Thomas ::
Postavljanje trikotnika a=5, b=6, c=7 na grid 8x8.
Če (ko) mu bo uspelo kaj optimizirat ...
Anyway najprej naredimo tole, potem pa lahko dodamo še x in y translacije, ki so tudi legalne pozicije na gridu. Iz teh pozicij za razne trikotnike potem poženemo bruta forca zanko. Vsak problem se lahko reši z zaporedjem bruta forca programskih segmentov. Ki jih pa lahko na vsaki točki podvržemo (avtomatski) optimizaciji.
$declareint i j k xi yi xj yj xk yk dxij dxik dxjk dyij dyik dyjk dij dik djk three four five edge upto index zero
$dimension positions[10000]
$retvar positions[] index
$sound on
three=5;four=6;five=7;zero=0;
//$enhancing off
edge=8;upto=edge*edge;
for (i=zero; i<upto; i++) {
xi=i/edge; yi=i%edge;
for (j=zero; j<upto; j++) {
xj=j/edge; yj=j%edge;
dxij=xi-xj;dyij=yi-yj;dxij=dxij*dxij;dyij=dyij*dyij;dij=dxij+dyij;dij=sqrt(dij);
if (dij==three) {
for (k=zero; k<upto; k++) {
xk=k/edge; yk=k%edge;
dxik=xi-xk;dyik=yi-yk;dxik=dxik*dxik;dyik=dyik*dyik;dik=dxik+dyik;dik=sqrt(dik);
if (dik==four) {
dxjk=xj-xk;dyjk=yj-yk;dxjk=dxjk*dxjk;dyjk=dyjk*dyjk;djk=dxjk+dyjk;djk=sqrt(djk);
if (djk==five) {
positions[index]=xi;index++;
positions[index]=yi;index++;
positions[index]=xj;index++;
positions[index]=yj;index++;
positions[index]=xk;index++;
positions[index]=yk;
}
}
}
}
}
}
Če (ko) mu bo uspelo kaj optimizirat ...
Anyway najprej naredimo tole, potem pa lahko dodamo še x in y translacije, ki so tudi legalne pozicije na gridu. Iz teh pozicij za razne trikotnike potem poženemo bruta forca zanko. Vsak problem se lahko reši z zaporedjem bruta forca programskih segmentov. Ki jih pa lahko na vsaki točki podvržemo (avtomatski) optimizaciji.
Man muss immer generalisieren - Carl Jacobi
jeti51 ::
@snow: Dolžine stranic trikotnikov so cela števila, število trikotnikov pa ni večje od 100. Rezultat pa je seznam koordinat trikotnikov + ena grafična slikica.
Glede krogov pa: kako napisati genom, je trivialno. Bolj me zanimajo ideje za mutacijo in crossover in pa sam globalen pristop. Lahko naredimo en kvadrat in potem poskušamo kroge postavit not, fitnes funkcija pa meri stopnjo mesebojnega prekrivanja krogov. Če najdemo konfiguracijo s fitnessom 0 (ni prekrivanj), je problem rešen in ga poskusimo še enkrat rešiti na malo manjšem kvadratu... kvadrat tako manjšamo, dokler lahko. Pri tem načinu sta crossover in mutacija enostavna (pač malo se igraš s središči krogov), ker pač ni treba skrbeti, da se krogi ne prekrivajo in za to skrbi fitness funkcija.
Drug pristop pa bi bil, da direktno poskušamo najti najmanjši kvadrat. Kroge malo razmečemo po ravnini, fitness pa je ploščina najmanjšega kvadrata, ki te kroge vsebuje. Pri crossoverjih in mutacijah je sedaj malo večji problem, saj je treba paziti, da dobivaš feasible rešitve oz. dobljene rešitve po potrebi sproti popravljati...
Še malo offtopic razmišljanja: to je nenazadnje samo seminarska naloga. Prebral sem si nekaj disertacij na temo object packinga in glede na to, da ljudje iz tega delajo cele doktorate, dvomim, da bi tudi sam profesor znal kar iz rokava na nek hudo dober način tele naloge rešiti (
), kaj šele "navadne študentke". Zadostoval bi že kakšen relativno preprost algoritem, samo da je pa malo že boljši od naivnega. Ker to nalogo bo treba tudi zagovarjati in če se študentka tam pojavi z nekim super hudim algoritmom... ji bo profesor seveda verjel, da ga je sama naredila. Razni genetski algoritmi so tako že praktično na robu "dovoljenega" (čeprav bi se jaz poslužil ravno česa takega), medtem ko bi bil kakšen bilijardni algoritem (za kroge) kar fina zadeva - enostaven in za seminarsko čisto v redu.
Toliko zaenkrat.
P.S.: Seveda pa mene osebno zelo zanima, kaj bo izpljunil Critticall in kako bi se tega problema on lotil.
Glede krogov pa: kako napisati genom, je trivialno. Bolj me zanimajo ideje za mutacijo in crossover in pa sam globalen pristop. Lahko naredimo en kvadrat in potem poskušamo kroge postavit not, fitnes funkcija pa meri stopnjo mesebojnega prekrivanja krogov. Če najdemo konfiguracijo s fitnessom 0 (ni prekrivanj), je problem rešen in ga poskusimo še enkrat rešiti na malo manjšem kvadratu... kvadrat tako manjšamo, dokler lahko. Pri tem načinu sta crossover in mutacija enostavna (pač malo se igraš s središči krogov), ker pač ni treba skrbeti, da se krogi ne prekrivajo in za to skrbi fitness funkcija.
Drug pristop pa bi bil, da direktno poskušamo najti najmanjši kvadrat. Kroge malo razmečemo po ravnini, fitness pa je ploščina najmanjšega kvadrata, ki te kroge vsebuje. Pri crossoverjih in mutacijah je sedaj malo večji problem, saj je treba paziti, da dobivaš feasible rešitve oz. dobljene rešitve po potrebi sproti popravljati...
Še malo offtopic razmišljanja: to je nenazadnje samo seminarska naloga.
Prebral sem si nekaj disertacij na temo object packinga in glede na to, da ljudje iz tega delajo cele doktorate, dvomim, da bi tudi sam profesor znal kar iz rokava na nek hudo dober način tele naloge rešiti ( ), kaj šele "navadne študentke". Zadostoval bi že kakšen relativno preprost algoritem, samo da je pa malo že boljši od naivnega. Ker to nalogo bo treba tudi zagovarjati in če se študentka tam pojavi z nekim super hudim algoritmom... ji bo profesor seveda verjel, da ga je sama naredila. Razni genetski algoritmi so tako že praktično na robu "dovoljenega" (čeprav bi se jaz poslužil ravno česa takega), medtem ko bi bil kakšen bilijardni algoritem (za kroge) kar fina zadeva - enostaven in za seminarsko čisto v redu.Toliko zaenkrat.
P.S.: Seveda pa mene osebno zelo zanima, kaj bo izpljunil Critticall in kako bi se tega problema on lotil.
snow ::
Thomas, tole ti vrne int... recimo bi pa bilo 7,9 kar ni ravno 7. At least i think so?
> dij=sqrt(dij);
Mogoce bi moral resolucija grida povecat za 10 krat... potem je napaka ze manjsa.
> dij=sqrt(dij);
Mogoce bi moral resolucija grida povecat za 10 krat... potem je napaka ze manjsa.
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins
Thomas ::
Ja, v bistvu smo naredili že nekaj kitov (to kot strict C source, Critticall potem "normalno" dela na tem), ki bi kazali, kako se zevoluira rešitev problema. Nisem še preveč zadovoljen. Zaradi enostavnosti uporabe ne. Bom pa, mislim.
Man muss immer generalisieren - Carl Jacobi
snow ::
Mam že zadevo za kroge narejeno... mal še treba optimirat.
Recimo ugotovi pa da če mamo 4 kroge z radijem 1, da jih spravi v 4x4 kvadrat.
Ali pa en krog 50 pa 4 krogce po 1... tud spravi skupaj v 100x100 kvadrat.
Za ostale bo treba se mal optimirat.
A grid za trikotnike tud morajo bit realna stevila? Hmm...
Recimo ugotovi pa da če mamo 4 kroge z radijem 1, da jih spravi v 4x4 kvadrat.
Ali pa en krog 50 pa 4 krogce po 1... tud spravi skupaj v 100x100 kvadrat.
Za ostale bo treba se mal optimirat.
A grid za trikotnike tud morajo bit realna stevila? Hmm...
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins
jeti51 ::
Hm, jaz sem bolj skeptičen do tega, da bi takole kam daleč prišel. Namreč krogi so tudi naključno veliki (za kroge tudi nisem prepričan, da morajo biti radiji le cela števila
) in najbrž se tako prevečkrat zgodi, da "štirih krogov z radijem ena" sploh ni na voljo in marsikaterega pravila tako sploh ne bi bilo možno uporabiti. Pa tudi sicer je že zlaganje samo enako velikih krogov težka naloga, kolikor sem gledal. Za več kot 50 krogov skoraj ni znanih dokazano optimalnih rešitev. Pa recimo za 49 krogov proti pričakovanjem optimalna rešitev ni več kvadrat (7x7 krogov v kvadrat postavljenih), kot je to pri nižjih kvadratih naravnih števil (36, 25, ...).
Stvar je veliko bolj zapletena, kot se zdi na prvi pogled.
) in najbrž se tako prevečkrat zgodi, da "štirih krogov z radijem ena" sploh ni na voljo in marsikaterega pravila tako sploh ne bi bilo možno uporabiti. Pa tudi sicer je že zlaganje samo enako velikih krogov težka naloga, kolikor sem gledal. Za več kot 50 krogov skoraj ni znanih dokazano optimalnih rešitev. Pa recimo za 49 krogov proti pričakovanjem optimalna rešitev ni več kvadrat (7x7 krogov v kvadrat postavljenih), kot je to pri nižjih kvadratih naravnih števil (36, 25, ...).Stvar je veliko bolj zapletena, kot se zdi na prvi pogled.
Thomas ::
Dostikrat gnezdena for zanka, da vedno pravilen odgovor. Da bi jo vrgli v Critticall, da jo zoptimizira - gre (samo!) po kosih, sicer predolgo traja.
Kar se mi zdi pa realno reševanje (vsakega) problema.
Kar se mi zdi pa realno reševanje (vsakega) problema.
Man muss immer generalisieren - Carl Jacobi
snow ::
A kroge se postavlja na grid iz realnih števil?
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins
Vredno ogleda ...
| Tema | Ogledi | Zadnje sporočilo | |
|---|---|---|---|
| Tema | Ogledi | Zadnje sporočilo | |
| » | Resne težave z razumevanjem osnov programiranja (strani: 1 2 )Oddelek: Programiranje | 16548 (13060) | RatedR |
| » | Digitalna evolucija (strani: 1 2 3 4 … 26 27 28 29 )Oddelek: Znanost in tehnologija | 75449 (25618) | pietro |
| » | Python iskanje podvojenih vrednostiOddelek: Programiranje | 1485 (1198) | BlueRunner |
| » | Površina kroga brez pi (strani: 1 2 )Oddelek: Znanost in tehnologija | 10958 (9047) | CHAOS |
| » | [visual c++] Rabim nasvet, razbijanje števila na števkeOddelek: Programiranje | 3031 (2398) | hexor |