Tein ohjelman, jolla aikaansain mahdollisimman suuria ympyröitä kuvaan siten, että ne eivät mene toistensa päälle. Mielestäni tein oivaltavaa matemaattista abstraktia taidetta :) Näyttävät vähän saippuakuplilta laatikossa.
http://petke.info/isotympyrat2.png
http://petke.info/isotympyrat2.png
Vastaukset 11
Vanhimmat
Keksit lisää ruutia. Asiasta on julkaistu ties vaikka kuinka paljon:
http://scholar.google.com/scholar?q=packing unequal circles
https://www.google.com/search?q=packing unequal circles
Kappas, kiitos. Löytyy varmaan mielenkiintoista luettevaa minulle...Tuohan ei poistanut minulta ollenkaan sekä ongelman miettimisen että siihen oman ratkaisun keksimisen iloa, että joku muukin oli asiaa pohdiskellut. Varmasti sillekin, joka keksi ruudin kiinalaisten jälkeen, ollen tietämätön kiinalaisten saavutuksista, tuotti yhtä paljon iloa ruudin keksiminen.
No enpä löytänytkään kylläkään yhtäkään ratkaisua ja edes täsmälleen saman aiheen käsittelyä: "Kuinka täyttää annettu suorakaiteen muotoinen alue mahdoillisimman suurilla ympyröilä". Anna yksi linkki.
Olen nyt googlaillut aika monta tuntia, mutta en ole löytänyt yhtäkään artikkelia, jossa aihetta oltaisiin käsitelty. Yhden sellaisen artikkelin löysin, jossa käsiteltiin kuinka piirtää kaksi mahdollisimman suurta ympyrää suorakaiteeseen:
http://math.stackexchange.com/questions/938487/how-to-maximize-area-of-two-circles-inside-a-rectangle-without-overlapping
mutta ei siinäkään käsitelty sitä, kuinka piirtäisi mahdollisimman suuria tietty määrä. Joten jos asiasta on julkaistu ties miten paljon, niin voisitko ystävällisesti auttaa minua löytämään edes yhden artikkelin, jossa aiheesta on julkaistu? Kiinnostaisi todella lukea.
Voi olla, että juuri tuollainen artikkeli on vaikea löytää, sillä useimmat ongelmat käsittelevät optimaalista pakkaamista tai materiaalinkäyttöä. Silloin ympyrän kokoja on tietty, rajallinen sarja.
Tuollaisesta sarjasta saa tietenkin hyvän likiratkaisun, kun ottaa suurimman ympyrän halkaisijaksi suorakaiteen pienemmän sivun mitan sekä sen ja pienimmän piirrettavän ympyrän väliin ympyrät esim. millimetrin portain.
Mutta yritän vielä etsiä, kunhan paremmin ehdin. Luulisin jonkun matemaatikon tuollaisenkin ongelman ratkaisseen.
Tämä alkaa olla lähellä, kun määrittää ehdokaspopulaation edellä kertomallani tavalla:
.
http://www.econbiz.de/archiv/ha/fuha/winformatik/algorithms_packing_circles.pdf
En tiedä, kuinka hyvin yleensä tunnet kombinatorisen optimoinnin juttuja, joita tämä ympyröiden asettelukin on. Vihjeenä voin kertoa, etteivät ahneet algoritmit, eli menetelmät, jotka hetkellisesti maksimoivat peittoa, tuota alueelle maksimipeittoa.
Maksimipeitto saadaan, kun otetaan mukaan syvyys, eli tämänhetkisen valinnan vaikutus tuleviin. Täydellinen haku vaatinee edelleenkin maailman koko tietokonetehon valjastamista tehtävän ratkaisuun, jos ehdokkaita on paljon ja alue 14laaja.
Tehtävänä ei ollut saavuttaa maksimipeittoa, vaan piirtää kuvaan ensin mahdollisimman suuri ympyrä, sen jälkeen toinen mahdollisimman suuri ympyrä jne...
Eli eipä tuo julkaisu ollut lähelläkään.
Tuo on juuri se yksinkertainen ahne algoritmi.
Aha, hyvä, kiitos. Täytyy tutustua tarkemmin. Ehkä se on nopeampikin algoritmi. Mun oma on tooosi hidas.
Tos on mun raakaan laskuvoimaan perustuva tyhmä algoritmi:
http://petke.info/isojaympyroita.r