Skrollin toimituksen blogin helmikuun ohjelmointipähkinä saavutti valtavan suosion. Ongelmana oli jakaa luvut √1, √2, …, √100 kahteen joukkoon siten, että osien summat ovat mahdollisimman lähellä toisiaan.

Ongelman esitti tiedettävästi alun perin tietojenkäsittelytieteilijä Bob Floyd vuonna 1972 joukolle ensimmäinen vuoden tohtoriopiskelijoita Stanfordissa. Alkuperäinen muotoilu oli:

”The numbers √1, √2, … , √50 are to be partitioned into two parts whose sum is nearly equal; find the best such partition you can, using less than 10 seconds of computer time.”

Tällaisenaan ongelma ei sovi nykypäivään, koska prosessoreiden laskentateho on kasvanut niin paljon, että tämä ongelma on ratkottavissa täsmällisesti. Siispä blogia varten tuplasimme syötteen koon, joka kasvattaa hakuavaruuden taas mahdottoman suureksi.

Jos haluat miettiä ongelmaa ensin itse, lopeta lukeminen tähän!

Pulmaa kannattaa lähestyä muotoilemalle se uudelleen seuraavasti: etsi osajoukko, jonka summa on mahdollisimman lähellä kaikkien neliöjuurten summan puolikasta, joka on noin 335,7. Nyt ongelma muistuttaa tunnettua subset sum -ongelmaa, jossa on etsittävä annetusta lukujoukosta osajoukko, jonka summa on annettu luku. Subset sum on NP-vaikea ongelma, joten tehokasta algoritmia tuskin löytyy. Ongelma on kuitenkin hyvä harjoitus suurten hakuavaruuksien heuristiseen läpikäyntiin.

Donald Knuth kirjoittaa ongelmasta artikkelissaan ”Are Toy Problems Useful?” vuodelta 1977. Artikkeli löytyy tänä päivänä helpoiten Knuthin kirjasta Selected Papers on Fun and Games. Knuthin mielestä ongelma on täydellinen leluongelma: se on tarpeeksi yksinkertainen, että siinä ei juutu merkityksettömiin yksityiskohtiin, mutta siinä on silti tarpeeksi mielenkiintoista rakennetta, kuten esimerkiksi se, että √3 + √12 = √27.

Knuthin ratkaisu toimii pääpiirteittäin seuraavasti: otetaan sivuun ne luvut, joiden neliöjuuri on kokonaisluku: 1, 2, 4, 9, 16… Sen jälkeen etsitään jäljellä olevista luvuista osajoukko, jonka summan desimaaliosa on mahdollisimman lähellä kaikkien neliöjuurten summan puolikkaan desimaaliosaa. Lopuksi yritetään korjata kokonaislukuosa kohdalleen ottamalla sivuun laitetuista luvuista sopiva osajoukko mukaan. Knuthilla on myös käytössä arsenaali muita huomioita kuten se, että √8 = 2√2, √18 = 3√2, √32 = 4√2, ja niin edelleen. Yksityiskohdat on kirjoitettu hienosti auki Knuthin artikkelissa, joten emme käy niitä läpi tässä.

Lukijoiden ratkaisut

Toimitus seurasi jännityksellä, kun kommentteihin ilmestyi toinen toistaan parempia ratkaisuja. Ensin päästiin 32-bittisen floating point luvun tarkkuuden rajoille, sitten 64-bittisen, ja lopulta vielä pitemmälle. Parhaan ratkaisun löysi lopulta nimimerkki sisu tuloksella 3,54e-17, kuusi kertaluokkaa muita edellä! Sisun ratkaisu on seuraava ositus:

[1, 2, 3, 5, 6, 10, 11, 14, 15, 18, 22, 26, 28, 32, 33, 36, 37, 39, 41, 42, 44, 45, 46, 49, 50, 51, 54, 55, 62, 63, 64, 65, 67, 68, 69, 70, 73, 75, 78, 79, 80, 82, 85, 88, 89, 92, 93, 96, 97, 99]

[4, 7, 8, 9, 12, 13, 16, 17, 19, 20, 21, 23, 24, 25, 27, 29, 30, 31, 34, 35, 38, 40, 43, 47, 48, 52, 53, 56, 57, 58, 59, 60, 61, 66, 71, 72, 74, 76, 77, 81, 83, 84, 86, 87, 90, 91, 94, 95, 98, 100]

Miten tähän oli päädytty? Hakuavaruuden koko on 2¹⁰⁰, joten kaikkia vaihtoehtoja ei voi millään käydä läpi. Sen sijaan on keksittävä algoritmi, joka keskittyy jollain tapaa hakuavaruuden lupaavimpiin osiin. Tähän on olemassa tunnettuja metaheuristiikkoja kuten simuloitu jäähdyttäminen ja geneettiset algoritmit.

Sisun ratkaisu ei kuitenkaan käytä näitä, vaan se on yhdistelmä arpomista ja täsmällistä ratkontaa. Ratkaisu toimii kahdessa vaiheessa: ensin se arpoo jonkin osajoukon luvuista √51, …, √100 ja sitten täydentää osajoukkoa valitsemalla luvuista √1, …, √50 osajoukon siten, että arvotun ja valitun osajoukon summa on mahdollisimman lähellä kaikkien neliöjuurten summan puolikasta.

Sisu ratkaisee toisen osuuden täsmällisesti käyttämällä meet-in-the-middle-tekniikkaa. Se toimii seuraavasti: luodaan kaksi taulukkoa A ja B. Lasketaan taulukkoon A kaikki summat, jotka on mahdollista muodostaa luvuista √1, …, √25, ja taulukkoon B kaikki summat, jotka voidaan muodostaa luvuista √26, …, √50. Järjestetään molemmat taulukot suuruusjärjestykseen. Nyt voidaan etsiä paras kokonaissumma käymällä läpi taulukko A alusta loppuun ja taulukko B lopusta alkuun samanaikaisesti.

Yksityiskohtaisemmin sanottuna: Laitetaan osoitin taulukon A alkuun ja taulukon B loppuun. Jos osoittimien osoittamien summien summa on alle halutun, siirretään taulukon A osoitinta eteenpäin. Muussa tapauksessa siirretään taulukon B osoitinta taaksepäin ja toistetaan tätä kunnes jompikumpi osoitin menee ulos taulukosta.

Kunniamaininnan ansaitsee Veikko Sariola, joka oli kokeillut geneettistä algoritmia MATLABilla, mutta tulos oli vain 3,0997e-05. Osoittautui, että optimoitu raaka voimankäyttö oli paras lähestymistapa ongelmaan.

Jarno Niklas Alanko
Toimittaja, Skrolli

Voittajaratkaisun listaus verkkojatkoillamme: skrolli.fi/numerot.