Problem škatel

Akademsko al komercialno vprašanje?

Mora biti rešitev dokazljivo najboljša?

Tole je težek problem. NP, kokr vidim.

knapsack???

Sam sem tudi razmišljal o uporabi algoritma Nahrbtnika. Vendar je problem v tem, da nimamo dane največje dane vrednosti oziroma volumna. Prav tako nahrbtnik deluje (vsaj osnovna različica) z eno dimenzijo, tukaj pa je pomembna tudi oblika. Nekako pa ga bom skušal implementirati. S tem vprašanjem sem bolj mislil na nasvete o primernih algoritmih. Lahko pa bi naredil tudi en brute force algoritem, ki bi pač enkrat šel skozi množico škatel in upošteval samo dolžino ali pa kaj podobnega.

Sam sem nekako izpostavil te oporne točke:
- Primerjati bom moral ploskve škatel
- Za prvo sortiranje škatel bi uporabil volumen.
- Hkrati bo potrebno graditi drevo najbolj optimalne rešitve.

Tako na hitro.

**Število škatel, katerim se ne bi uspelo uvrstiti v množici mora biti minimalno. Lahko mešamo velikost, dolžino in širino med seboj. **

kaj to točno pomeni?

@mia

to pomeni, da ti ni potrebno zapakirati vseh skatel.

Thomas: tvoj algoritem je čisto v redu. Toda je malo preveč splošen. Seveda se bo tudi moj poznejši algoritem držal tvojega. Sam sem mislil. da mogoče obstaja že matematično dokazan najboljši algoritem za tak problem. Ker ne študiram matematike, sem pač prosil za nasvet, da ne bom izumljal tople vode in se matral z "home made" algoritmom, ki bi ga potem posekal en zelo enostaven matematičen algoritem.

Pri mešanju dolžine, višine in širine sem mislil na zapis škatle (ai,bi,ci), kjer je ai dolžina, bi širina in ci višina škatle. No zdaj bi lahko privzeli da naloga ne dovoljuje rotacije škatle po x,y in z osi. To bi bila pač trivialna naloga, kjer bi samo primerjal ploskve (ai in bi) in izbiral naslednjo škatlo tako da bi bila razlika med ploskvama minimalna. Prav tako ne gre pozabiti, da se volumen strukture spreminja oziroma ni fiksen.


Sicer pa bo prvi korak iskanje najbolj prostorne škatle. Nekako tako si zamišljam še bolj podroben algoritem:

1.) Iskanje največje škatle (izračun ploskve po ai in bi, ai in ci, ci in bi)
2.) Grobo sortiranje škatel po volumnu oziroma po ploskvah
3.) Iskanje najbolj ustreznega kandidata za naslednjo škatlo
4.) Odstranjevanje neprimernih škatel iz množice rešitev (recimo zelo dolga in ozka škatla bi lahko pokvarila celo množico)
5.) Množica odstranjenih škatel mora biti minimalna
6.) Sprotno grajenje drevesa rešitve
7.) Primerjanje trenutno najboljšega drevesa rešitev s trenutnim drevesom

Tako na grobo se mi zdi.

mas prav owca

1. Greš skozi vse škatle in gledaš, katera gre samo ona sama v katerokoli drugo. Če jo najdeš, jo izločiš, tisto ki gre not in tisto, v katero gre najbolj natesno - in začneš s tem postopkom znova.


2. Zdej probaš z dvema, kot prej z eno.

3. S tremi.

..

..

Prešteješ škatle, ki so ti ostale.

Tisto z vsebovanostjo ni tako dobro. Ker vsebovanostnih matrik je več različnih, pa miajin algoritem ne določa, kateri potem najti usmerjeni graf.

ja in če gre ena škatla v 7?
je torej iz ene škatle 7 puščic.. in?

in NE, matrika totalne vsebovanosti(z tranzitivnimi povezavami) je samo ENA, karkšnakoli okleščena matrika tranzitivnih povezav, bo pa tudi enako dobra, samo hitrejše bo deloval algoritem iskanja najdalše poti

Ni vseeno, katerih 7 (ali N) škatel zapakiramo v katero škatlo. Izid je lahko potem precej različen.

Moram narisat?

NI unikatne matrike vsebovanosti. V eno škatlo v splošnem lahko daš alternativne množice škatel. Ti jih lahko potem več/manj ostane.

Štekaš?

Evolucijski algoritem.

Encoding nekaj v stilu:
zunanja skatla: notranja skatla&rotacija; notranja skatla2&rotacija2... (saj rotacij/postavitev je 6(3!) a ne?)

Npr:
1: 3,0 4,2
2: 1,5
3:
4:

Mutacije:
mal prestavljaš škatle iz eno v drugo in jih sučeš...
osebke v evoluciji lahko med sabo tudi mal križaš.. ampak mal treba pazit.

Fitness:
Število škatel, ki ni v nobeni škatli.

aha 7 škatel v 1..
no torej gre iz vsake točke izmed teh 7 ena puščica v to točko.. in?

ta graf ne predstavlja rešitve.. ta graf samo pove možno vsebovanost.
Rešitev je pa najdaljša možna pot v grafu(po usmerjenih povezavah)..torej največje število škatel, ki drugo drugo lahko vsebujejo, in torej največja vsebuje vse.

haha thomas, lol.. ??

dejte brisat post k je neargumentiran

za vajo pa lah ti pošlješ mail prof Batagelju ki je nalogo zastavil in se prepričaj, kot pa da tu pišeš neresnice , ki izhajajo iz tvoje nesposobnosti logičnega razmišljanja

Dost si šorf za svoje neznanje mia-.

> Da bi bila optimalna rešitev vedno pakiranje v samo eno škatlo niti slučajno ni očitno (pravzaprav je kar narobe ).

A OwcAtov stavek mogoče pa razumeš? Naj ti ga ilustriram dodatno?

Lej, za kakšno škatlo imaš alternative, katere škatle boš spakiral notri eno zraven druge. Niso vse te alternative enakovredne. Pri nekaterih morda nazadnje ostane več škatel zunaj. V splošnem je tako.

Narobe.

Škatle lahko dajemo po več v eno. Pa v vsaki od njih jih je lahko po več, ali nobene.

NI potem enoznačno, kje, v kateri je lahko katera škatla.


p.s.

Celo če je, zadeva še NI taka. Ampak o tem kasneje, nej se zmenimo najprej tole.

Če bi uprabil glavo, bi vedel da ni res.

VEČ škatel naenkrat je lahko v škatli X. Škatli A in B naprimer, ALI pa škatli C in D sta lahko v X. Vendar potem A ni več, pa gre C lahko tudi v A.

ITD...

Ali drugače rečeno. Če neko škatlo damo nekam, potem mnoge druge tja ne gredo več.

Ja?

Thomas: graf vsebovanosti nam pove kako lahko sestavimo škatle. To hoče povedati mia-. Primer z enoštevilčnimi vrednostmi.
A = 5
B = 6
C = 7
D = 4

Matrika 4x4 vsebovanosti pa bi zgledala takole. Predpostavimo, da je škatla lahko vsebovana sami sebi

A 1 1 1 0
B 0 1 1 0
C 0 0 1 0
D 1 1 1 1

To nam samo pove kandidate kako sestavljati škatle skupaj. Tvoj algoritem bi vzel škatlo D in jo primerjal z vsemi v množici. Miin bi pa poiskal najdaljšo pot.

v tvojem primeru bi torej slo C v A in B v X..
sedaj opažam da so navodila dvolična in si jih jas drugače intepretiram kot ti, zato tudi nasprotovanja

jas si interpretiram tako da dajes eno v drugo in potem drugo spet v tretjo, itd.. ti pa mislim da dopuscas tut da gresta 2 skatli v eno, druga zraven druge, ne ena v drugi

torej je sedaj odvisno od naloge, kako tocno je zastavljena..

Thomas: Poglej, tisto je samo zemljevid, ki nam pove katere škatle lahko daš skupaj. To ne pomeni, da lahko gresta v škatlo X tako A kot B. Zato pa moraš sproti graditi drevo rešitev, ki ga primerjaš s trenutno najboljšim drevesom rešitev. Itak ne greš samo enkrat čez to matriko ampak večkrat in primerjaš med seboj različice.

Hm... zdaj vidim da je mogoče tudi na tak način Da sta lahko dve različni škatli, druga ob drugi. Jaz sem mislil, da je naloga takšna, da vstavljaš eno škatlo v drugo in tisto kar ostane zunaj te "velike" škatle, spet urediš v novi škatli.

Ne, ne. Naloga je čisto OK, moj algoritem pa zelo dober.

Ima še en popravek, ki ga pa ne bom dal. Ne zaslužite si.

> Mislm, da je naloga, da morajo biti škatle ena v drugi.

Prima. Prima. Hehe ...

Besides. ČETUDI - ni enolične linije vsebovanosti, še vedno ne.

!!!