Pakkausongelmat - Packing problems

Palloja tai ympyröitä pakattu löysästi (ylhäältä) ja tiheämmin (alhaalta)

Osa sarjasta
Palapelit
Tyypit Arvaaminen Arvoitus Tilanne Logiikka Leikkaus Induktio Looginen ruudukko Itseviittaus Mekaaninen Yhdistelmä Rakentaminen Erottaminen Lukko Mene ongelmia Taitto Puikko Laatoitus Kiertue Liukuva Shakki Sokkelo  ( logiikka sokkelo ) Sana ja numero Ristisanatehtävä Sudoku Pulmapeli videopelejä Sokkelot Meta -suuttimet
Aiheet Brain teaser Dilemma Optinen illuusio Pakkausongelmat Paradoksi Ongelmanratkaisu Puzzlehunt Syllogismi ajatella laatikon ulkopuolella
Luettelot Mahdotonta arvoituksia Maze -videopelit Nikoli -palapelityypit Pulmapeli videopelejä Palapelin aiheet
v t e

Pakkaus ongelmat ovat luokan optimointitehtäviä vuonna matematiikan , joihin liittyvät yrittää pakata esineitä yhteen astioihin. Tavoitteena on joko pakata yksi säiliö mahdollisimman tiheästi tai pakata kaikki esineet käyttämällä mahdollisimman vähän säiliöitä. Monet näistä ongelmista voivat liittyä tosielämän pakkaus- , varastointi- ja kuljetuskysymyksiin. Jokaisella pakkausongelmalla on kaksinkertainen peiteongelma , joka kysyy, kuinka monta samaa esinettä tarvitaan kattamaan kaikki säiliön alueet, joissa esineet saavat päällekkäin.

Vuonna bin pakkaus ongelma , sinulle annetaan:

• 'kontit' (yleensä yksi kaksi- tai kolmiulotteinen kupera alue tai ääretön tila)
• Joukko "esineitä", joista osa tai kaikki on pakattava yhteen tai useampaan säiliöön. Joukko voi sisältää erilaisia ​​objekteja, joiden koot on määritetty, tai yhden kiinteän ulottuvuuden objektin, jota voidaan käyttää toistuvasti.

Yleensä pakkauksen on oltava päällekkäin tavaroiden ja muiden tavaroiden tai kontin seinien välillä. Joissakin muunnelmissa tavoitteena on löytää kokoonpano, joka pakkaa yhden säiliön, jonka tiheys on suurin. Yleisemmin tavoitteena on pakata kaikki esineet mahdollisimman harvoihin astioihin. Joissakin muunnelmissa päällekkäisyys (esineiden keskenään ja/tai säiliön reunan kanssa) on sallittua, mutta se on minimoitava.

Pakkaus äärettömään tilaan

Monet näistä ongelmista, kun säiliön kokoa kasvatetaan kaikkiin suuntiin, vastaavat ongelmaa pakata esineitä mahdollisimman tiheästi äärettömässä euklidisessa tilassa . Tämä ongelma liittyy useisiin tieteenaloihin ja on saanut paljon huomiota. Kepler arveluja oletettu optimaalinen ratkaisu pakkaamiseen aloilla satoja vuosia ennen kuin se osoittautunut oikeaksi Thomas Callister Hales . Monet muut muodot ovat saaneet huomiota, mukaan lukien ellipsoidit, platoniset ja archimedealaiset kiinteät aineet, mukaan lukien tetraedrat , kolmijalat (kuutioiden liitokset kolmen positiivisen akselin suuntaisen säteen varrella) ja epätasaiset pallodimeerit.

Ympyröiden kuusikulmainen pakkaus

Ympyröiden kuusikulmainen pakkaus 2-ulotteisella euklidisella tasolla.

Nämä ongelmat eroavat matemaattisesti ympyrän pakkauslauseen ideoista . Tähän liittyvä ympyräpakkausongelma koskee mahdollisesti erikokoisia pakkausympyröitä pinnalla, esimerkiksi tasossa tai pallossa.

Kollegansa ympyrän muissa ulottuvuuksissa voida koskaan täynnä täysin tehokkuutta mitat suurempi kuin yksi (joka yksiulotteinen maailmankaikkeus, ympyrä analogi on vain kaksi pistettä). Toisin sanoen aina on käyttämätöntä tilaa, jos pakkaat vain ympyröitä. Tehokkain tapa pakata ympyröitä, kuusikulmainen pakkaus , tuottaa noin 91% hyötysuhteen.

Pallopakkaukset suuremmissa mitoissa

Kolmessa ulottuvuudessa tiiviisti pakatut rakenteet tarjoavat parhaan pallomaisen ristikkotiivisteen , ja niiden uskotaan olevan kaikkien pakkausten optimaalinen. Kolmen ulottuvuuden '' yksinkertaisilla '' pallopakkauksilla ("yksinkertainen" määritellään huolellisesti) on yhdeksän mahdollista määriteltävää pakkausta. 8-ulotteinen E8-hila ja 24-ulotteinen Leech-hila ovat myös osoittautuneet optimaalisiksi omassa todellisessa ulottuvuudessaan.

Pakkaukset Platonin kiintoaineita kolmessa ulottuvuudessa

Kuutiot voidaan helposti järjestää täyttämään kolmiulotteinen tila kokonaan, luonnollisin pakkaus on kuutiomainen hunajakenno . Mikään muu platoninen kiinteä aine ei voi laatoittaa tilaa yksinään, mutta joitakin alustavia tuloksia tiedetään. Tetrahedran pakkaus on vähintään 85%. Yksi parhaista säännöllisen dodekaedran pakkauksista perustuu edellä mainittuun kasvokeskeiseen kuutiometriin (FCC).

Tetrahedra ja oktaedra voivat yhdessä täyttää koko tilan järjestelyssä, joka tunnetaan nimellä tetraedrinen oktaedrinen hunajakenno .

Simulaatiot, joissa yhdistetään paikallisia parannusmenetelmiä satunnaisiin pakkauksiin, viittaavat siihen, että ikosahedran, dodekaedran ja oktaedrin ristikkopakkaukset ovat optimaalisia laajemmassa kaikkien pakkausten luokassa.

Pakkaus kolmiulotteisiin astioihin

Erilaiset kuutiot kuutioiksi

Määritä vähimmäismäärä kuutiomaisia ​​säiliöitä (laatikoita), jotka tarvitaan tietyn nimikekokoelman pakkaamiseen (3 ulottuvuista suorakulmioita). Pakattavia suorakulmaisia ​​neliöitä voidaan kääntää 90 astetta kullakin akselilla.

Palloista tulee euklidinen pallo

Ongelma löytää pienin pallo sellaiseksi, että sen sisälle voidaan pakata irrallisia avoimia yksikköpalloja, on yksinkertainen ja täydellinen vastaus -ulottuvuuteen perustuvassa euklidisessa tilassa , ja äärettömässä Hilbert -tilassa ilman rajoituksia. On syytä kuvata yksityiskohtaisesti täällä, jotta maku yleisestä ongelmasta. Tässä tapauksessa on saatavana kokoonpano parittain tangenttiyksikköpalloista. Aseta keskipisteet säännöllisen ulotteisen yksinkerroksisen pisteeseen, jonka reuna on 2; tämä on helppo toteuttaa ortonormaalista pohjasta. Pieni laskenta osoittaa, että jokaisen kärjen etäisyys barycenteristä on . Lisäksi millä tahansa muulla avaruuden pisteellä on välttämättä suurempi etäisyys ainakin yhdestä kärjestä. Mitä tulee pallojen sulkeutumiseen, avoimet yksikköpallot, joiden keskipiste on keskellä, sisältyvät palloon, jonka säde on vähäinen tässä kokoonpanossa. ${\ displaystyle k}$${\ displaystyle n}$${\ displaystyle k \ leq n+1}$${\ displaystyle k}$${\ displaystyle a_ {1}, \ pisteitä, a_ {k}}$${\ displaystyle (k-1)}$${\ texttyle {\ sqrt {2 {\ big (} 1-{\ frac {1} {k}} {\ big)}}}}$${\ displaystyle k}$${\ displaystyle k}$${\ displaystyle a_ {1}, \ pisteitä, a_ {k}}$${\ texttyle r_ {k}: = 1+{\ sqrt {2 {\ big (} 1-{\ frac {1} {k}} {\ big)}}}}$

Osoittaaksesi, että tämä kokoonpano on optimaalinen, anna olla erillisten avoimien yksikköpallojen keskipisteet, joiden säde on pallon keskellä . Harkitse kartan rajallisesta osaksi ottaen vastaavassa jokaiselle . Koska kaikki , tämä kartta on 1-Lipschitz ja jonka Kirszbraun lause se ulottuu 1-Lipschitz kartta, joka on maailmanlaajuisesti määritelty; erityisesti on olemassa sellainen kohta , että jokaisella on , niin myös . Tämä osoittaa, että säteessä olevassa pallossa on irrotettavia yksikköä avoimia palloja, jos ja vain jos . Huomaa, että äärettömässä Hilbert -avaruudessa tämä tarkoittaa sitä, että sädepallon sisällä on äärettömän paljon erillisiä avoimia yksikköpalloja silloin ja vain jos . Esimerkiksi, yksikkö pallot keskitetty , jossa on ortonormaali kanta, ovat erillisiä ja ne sisältyvät pallo, jonka säde on keskitetty alkuperää. Lisäksi säteellä r olevan pallon sisällä olevien erillisten avoimien yksikköpallojen enimmäismäärä on . ${\ displaystyle x_ {1}, \ pisteitä, x_ {k}}$${\ displaystyle k}$${\ displaystyle r}$${\ displaystyle x_ {0}}$${\ displaystyle \ {x_ {1}, \ pisteitä, x_ {k} \}}$${\ displaystyle \ {a_ {1}, \ pisteitä, a_ {k} \}}$${\ displaystyle x_ {j}}$${\ displaystyle a_ {j}}$${\ displaystyle 1 \ leq j \ leq k}$${\ displaystyle 1 \ leq i <j \ leq k}$${\ displaystyle \ | a_ {i} -a_ {j} \ | = 2 \ leq \ | x_ {i} -x_ {j} \ |}$${\ displaystyle a_ {0}}$${\ displaystyle 1 \ leq j \ leq k}$${\ displaystyle \ | a_ {0} -a_ {j} \ | \ leq \ | x_ {0} -x_ {j} \ |}$${\ displaystyle r_ {k} \ leq 1+ \ | a_ {0} -a_ {j} \ | \ leq 1+ \ | x_ {0} -x_ {j} \ | \ leq r}$${\ displaystyle k}$${\ displaystyle r}$${\ displaystyle r \ geq r_ {k}}$${\ displaystyle r}$${\ displaystyle r \ geq 1+{\ sqrt {2}}}$${\ displaystyle {\ sqrt {2}} e_ {j}}$${\ displaystyle \ {e_ {j} \} _ {j}}$${\ displaystyle 1+{\ sqrt {2}}}$${\ displaystyle r <1+{\ sqrt {2}}}$${\ texttyle {\ big \ lfloor} {\ frac {2} {2- (r-1)^{2}}} {\ big \ rfloor}}$

Pallot nelikulmaisena

Määritä halkaisijaltaan d pallomaisten esineiden määrä, jotka voidaan pakata neliöön , jonka koko on a × b × c .

Samat pallot sylinterissä

Määritä sylinterin vähimmäiskorkeus h , jolla on säde R , joka pakkaa n identtistä sädettä r (< R ). Pienellä säteellä R pallot järjestyvät tilattuihin rakenteisiin, joita kutsutaan pylväsrakenteiksi .

Polyhedra aloilla

Määrittää pienin säde R , joka pakkaus n identtinen, tilavuusyksikkö Polyhedra tietyn muodon.

Pakkaus 2-ulotteisiin astioihin

Optimaalinen 10 ympyrän pakkaus ympyrässä

Monivaihtoehtoisia 2-ulotteisia pakkausongelmia on tutkittu. Katso lisätietoja linkitetyiltä sivuilta.

Ympyröiden pakkaus

Sinulle annetaan n yksikköympyrää ja ne on pakattava pienimpään mahdolliseen säiliöön. Useita erilaisia ​​säiliöitä on tutkittu:

• Ympyrän pakkaus ympyrään - liittyy läheisesti yksikköympyrän hajautuspisteisiin tavoitteena löytää suurin minimietäisyys d _n pisteiden välillä. Optimaaliset ratkaisut on osoitettu n  ≤ 13 ja  n  = 19.
• Pakkausympyrät neliöön - liittyvät läheisesti neliöyksikön hajautumispisteisiin tavoitteena löytää suurin minimietäisyys d _n pisteiden välillä. Jos haluat muuntaa näiden kahden tehtävän muotoilun välillä, yksikköpiirien neliöpuoli on L  = 2 + 2/ d _n .
  

  Optimaalinen 15 ympyrän pakkaus neliössä
  Optimaaliset ratkaisut on osoitettu n  ≤ 30: lle.
• Pakkaus piireissä käytettäessä tasakylkinen suorakulmainen kolmio - hyvä arvioita tunnetaan n <300.
• Pakkausympyrät tasasivuiseen kolmioon - Optimaaliset ratkaisut tunnetaan n <13: lle ja arvelut ovat saatavilla n  <28: lle.

Neliöiden pakkaus

Sinulle annetaan n yksikköruutua ja ne on pakattava pienimpään mahdolliseen säiliöön, jossa säiliön tyyppi vaihtelee:

• Neliöiden pakkaaminen neliöön : Optimaaliset ratkaisut on osoitettu n  = 1–10, 14–16, 22–25, 33–36, 62–64, 79–81, 98–100 ja minkä tahansa neliön kokonaisluvulle. Hukattu tila on asymptoottisesti O ( a ^7/11 ).
• Neliöiden pakkaaminen ympyrään : Hyviä ratkaisuja tunnetaan n: stä 35: een.
  

  Optimaalinen 10 neliön pakkaus neliössä

Suorakulmioiden pakkaaminen

• Identtisten suorakulmioiden pakkaaminen suorakulmioon : Ongelma pakata useita esiintymiä yhdestä ( l , w ) kokoisesta suorakulmiosta , joka mahdollistaa 90 °: n kiertymisen, isommassa ( L , W ) suorakulmiossa on joitain sovelluksia, kuten laatikoiden lataaminen kuormalavoille ja erityisesti puumassan säilytykseen. Esimerkiksi on mahdollista pakata 147 (137,95) suorakulmion kokoiseen (1600,1230) suorakulmioon.
• Eri suorakulmioiden pakkaaminen suorakulmioon : Ongelma pakata useita eripituisia ja -korkuisia suorakulmioita sulkevaan suorakulmioon, jolla on vähimmäispinta -ala (mutta ilman rajoja sulkevan suorakulmion leveydelle tai korkeudelle), on tärkeä sovellus kuvien yhdistämisessä yhdeksi suureksi kuvaksi . Verkkosivu, joka lataa yhden suuremman kuvan, näyttää selaimessa usein nopeammin kuin sama sivu, joka lataa useita pieniä kuvia, koska jokaisen kuvan pyytäminen verkkopalvelimelta aiheuttaa kustannuksia. Ongelma on yleensä NP-täydellinen, mutta on olemassa nopeita algoritmeja pienten tapausten ratkaisemiseksi.

Aiheeseen liittyvät kentät

Laatoitus- tai tessellaatio -ongelmissa ei saa olla aukkoja eikä päällekkäisyyksiä. Monet tämän tyyppisistä arvoituksista sisältävät suorakulmioiden tai polyominoiden pakkaamisen suuremmaksi suorakulmioksi tai muuksi neliön muotoiseksi.

Suorakulmioiden (ja kuutioiden) laatoituksessa on merkittäviä teoreja suorakulmioissa (kuutiot), joissa ei ole aukkoja tai päällekkäisyyksiä:

X b suorakulmio voidaan pakata 1 x n nauhat, joss n jakaa tai n jakaa b .

de Bruijnin lause : Laatikko voidaan pakata harmonisella tiilillä a × ab × abc, jos laatikon mitat ovat ap × abq × abcr joillekin luonnollisille luvuille p , q , r (eli laatikko on tiilen monikerta.)

Polyomino -laattojen tutkimus koskee suurelta osin kahta ongelmaluokkaa: laatoitetaan suorakulmio yhteensopivilla laattoilla ja pakataan yksi jokaisesta n -minosta suorakulmioon.

Toinen klassinen palapeli on järjestää kaikki kaksitoista pentominoa suorakulmioiksi, joiden koko on 3 × 20, 4 × 15, 5 × 12 tai 6 × 10.

Epäsäännöllisten esineiden pakkaaminen

Epäsäännöllisten esineiden pakkaaminen on ongelma, joka ei sovi hyvin suljettuihin muotoratkaisuihin; soveltuvuus käytännön ympäristötieteeseen on kuitenkin varsin tärkeä. Esimerkiksi epäsäännöllisen muotoiset maaperän hiukkaset pakkautuvat eri tavalla, koska koot ja muodot vaihtelevat, mikä johtaa kasvilajien tärkeisiin tuloksiin juurimuodostumien mukauttamiseksi ja veden liikkumisen mahdollistamiseksi maaperässä.

Ongelma sen päättämisessä, mahtuuko tietty monikulmiojoukko tiettyyn neliöastiaan, on osoitettu täydelliseksi todellisuuksien eksistentiaalisessa teoriassa .

Katso myös

• Aseta pakkaus
• Säiliön pakkausongelma
• Slothouber – Graatsma -palapeli
• Conway -palapeli
• Tetris
• Ongelman peittäminen
• Reppu ongelma
• Tetraedrin pakkaus
• Ellipsoidipakkaus
• Leikkausongelma
• Kissing numero ongelma
• Tasaisten pallojen tiivistys
• Satunnainen pakkaus
• Nauhan pakkausongelma

Huomautuksia

Viitteet

• Weisstein, Eric W. "Klarnerin lause" . MathWorld .
• Weisstein, Eric W. "de Bruijnin lause" . MathWorld .

Ulkoiset linkit

• Kolmiulotteisen säiliön pakkauksen optimointi
• API 3D -säiliöiden pakkaamiseen
• 3D -laatikot ja sylinterit, joissa on teleskooppi

Monet pulmakirjat ja matemaattiset lehdet sisältävät artikkeleita pakkausongelmista.

• Linkit eri MathWorld -artikkeleihin pakkaamisesta
• MathWorld -muistiinpanot neliöiden pakkaamisesta.
• Erichin pakkauskeskus
• www.packomania.com Sivusto, jossa on taulukoita, kaavioita, laskimia, viitteitä jne.
• "Laatikkopakkaus" , Ed Pegg, Jr. , Wolfram Demonstrations Project , 2007.
• Tunnetuimmat yhden ympyrän pakkaukset ympyrässä, jopa 1100

• Ympyräpakkaushaasteongelma Pythonissa