TiraLabra/TiraLabra — pull request #342 by ilcca (2014-08-10 21:03:24+00:00)
Title: Ongelman koodausta, havaintoja, määrittelyn tarkennusta

Lähin liikkeelle rakentaa ensiksi algoritmia joka käy kaikki vaihtoehdot läpi järkevässä järjestyksessä eli ei käy samoja pakettikombinaatioita usean kerran ts. eliminoi pakettien järjestyksen kussakin kokoonpanossa. Tälläisen kaikkien kombinaatioiden etsiminen n-määrästä paketteja osoittautui yllättävänkin haastavaksi. Löysin siihen kuitenkin rakaisun ja onnistuin sen myös koodaamaan. Vielä parannettaavaa ratkaisussa on mm. kombinaatioiden symmetrisyyden hyödyntäminen, jolla läpikäytävien kombinaatioiden määrä voidaan puolittaa.
Ratkaisua tehdessä kävi ilmi, että siinä syntyy helposti todella suuuria taulukoita, jotka varaavat muistia eksponentiaalisesti n:n kasvaessa. Näitä taulukoita ei ole kuitenkaan pakko pitää yllä, kun etsitään parasta tai ensimmäistä kelvollista ratkaisua (koodissa pidetään vielä näitä taulukoita yllä, osin koodausteknisistä syistä, osin algoritmien testauksen takia, mutta loullisessa ratkaisussa niitä ei ole enää)

Jatkan kombinaatioalgoritmin hiomisella sekä algoritmin ajamiseen liittyvän koodin rakentamisella, jonka jälkeen pitäisi pystyä tehdä jo tilastollisia testejä algoritmin suorituskyvystä. tämän jälkeen jatkan branch and bound -menetelmään perustuvan algoritmin kehittämisellä.