Kaikkien testien ajamisen jälkeen kaikista parhaimman keskimääräisen tuloksen saavutti Algoritmi 2 pistemäärällä 396,7. Tästä kovin kauaksi ei jäänyt Algoritmi 1 pistemäärällä 395,3. Hieman huonompaan tulokseen jäivät Algoritmit 3 ja 4, jotka kuitenkin olivat kes-kenään melko tasaväkisiä. Hill climbing -tekniikkaan perustuva Algoritmi 3 vei kuitenkin voiton Algoritmista 4 keskimääräisellä pistemäärällä 372,9. Algoritmin 4 parhaaksi tulok-seksi jäi 366,2. On toisaalta hieman erikoista, että hill climbing -tekniikkaan perustuva al-goritmi päihitti simuloituun jäähdytykseen perustuvan alal-goritmin. Voi tosin olla, että reunatäsmäyspelien ongelman ratkaisuavaruus on niin valtava ja hajanainen, että yksin-kertaisella ahneella algoritmilla saavutetaan parempia tuloksia kuin hieman edistyneem-mällä algoritmilla.
Evoluutioon perustuvat algoritmit olivat siis tämän tutkielman perusteella tehok-kaampia kuin tutkielmassa käsitellyt paikalliseen etsintään perustuvat algoritmit. Evolu-tiiviset algoritmit mahdollistavat laajan etsintäavaruuden tutkimisen suuren populaation-sa takia, ja ilmeisesti tästä syystä nämä algoritmit myös populaation-saavuttivat korkeimmat pistemää-rätkin.
Algoritmien parametreja voisi yrittää muokata vielä pitkäänkin, jolloin parasta tulosta voisi ehkä hieman vielä parantaa. Pelkällä parametrien varioinnilla tuskin saavutetaan kuitenkaan enää merkittäviä uudistuksia algoritmien tuloksiin. Näkisin, että parametrien variointiin verrattuna käytettävän algoritmin rakenteellisilla uudistuksilla on paljon mer-kittävämpi osuus pistemäärän muodostamisessa. Jatkokehitysidana voisi olla esimerkiksi algoritmien muokkaaminen siten, että yksittäisen pelilaudan sisäiseen rakenteeseen kiin-nitettäisiin jonkinlaisen heuristiikan avulla enemmän huomiota pelkän satunnaisen muuntelun sijasta.
Parhain näkemäni tieteellisessä julkaisussa esitetty Eternity II -pistemäärä on Schausin ja Devillen [2008] julkaisema 458 pisteen tulos. Tämä saavutus on jo melko lähellä Eternity II:n 480 pisteen maksimitulosta, joten jään mielenkiinnolla seuraamaan, saavutetaanko tu-levaisuudessa vielä parempia tuloksia. Vai pysyykö Eternity II kenties ikuisesti ratkeamat-tomana?
Viiteluettelo
[Abraham et al., 2005] Ajith Abraham, Lakhmi Jain and Robert Goldberg, Evolutionary Multiobjective Optimization: Theoretical Advances and Applications. Springer Verlag, 2005.
[Ansótegui et al., 2008] Carlos Ansótegui, Ramón Bèjar, César Fernàndez and Carles Ma-teu, Edge matching puzzles as hard SAT/CSP benchmarks. In: Proc. of the 14th International Conference on Principles and Practice of Constraint Programming, Lecture Notes in Computer Science 5202, 560–565.
[Antoniadis and Lingas, 2010] Antonios Antoniadis and Andrzej Lingas, Approximability of edge matching puzzles. Lecture Notes in Computer Science 5901, 153–164.
[Benoist and Bourreau, 2008] Thierry Benoist and Eric Bourreau, Fast global filtering for Eternity II™. Constraint Programming Letters 3, 36–49. Available as http://www.cs.brown.edu/people/pvh/CPL/Papers/v3/BenoistBourreau.pdf. Checked 17.11.2010.
[Berger, 1966] Robert Berger, The Undecidability of the domino problem. Memoirs of the American Mathematical Society 66.
[Černý, 1985] V. Černý, Thermodynamical approach to the traveling salesman problem:
an efficient simulation algorithm, Journal of Optimization Theory and Applications 45, 1 (Jan.
1985), 41–51.
[Cook, 1971] Stephen A. Cook, The complexity of theorem proving procedures. In: Pro-ceedings of the 3rd Annual Symposium on Theory of Computing, 151–158. ACM, 1971.
[Cormen et al., 2007] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, 2nd ed., MIT Press, 2007.
[Davis, 2003] Lawrence Davis, Genetic algorithms and their applications. Available as http://www.informatics.indiana.edu/fil/CAS/PPT/Davis. Checked 13.4.2011.
[Deb et al., 2002] Kalyanmoy Deb, Amrit Pratap and Sameer Agarwal, A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation 6, 2 (Apr. 2002), 182–197.
[Demaine and Demaine, 2007] Erik D. Demaine and Martin L. Demaine, Jigsaw puzzles, edge matching, and polyomino packing: connections and complexity. Graphs and Combina-torics 23 (June 2007), 195–208.
[Eternity, 2002] Eternity. MathWorld – A Wolfram Web Resource. Available as http://mathworld.wolfram.com/Eternity.html. Checked 25.3.2011.
[Eternity II, 2007] About Eternity II. Available as http://uk.eternityii.com/about-eternity2. Checked 5.11.2010.
[Gasarch, 2002] William I. Gasarch, Guest column: The P=?NP poll. ACM SIGACT News 33, 2 (June 2002), 34–47.
[Guyton and Hall, 2000] Arthur C. Guyton and John E. Hall, Textbook of Medical Physiology.
W. B. Saunders Company, 2000.
[Holland, 1975] John. H. Holland, Adaptation in Natural and Artificial Systems. University of Michigan Press, 1975.
[Kirkpatrick et al., 1983] S. Kirkpatrick, C. D. Gelatt Jr. and M. P. Vecchi, Optimization by simulated annealing, Science 220, 4598 (May 1983), 671–680.
[Kujala, 2008] Tuomas Kujala, Reunatäsmäyspeleistä. Teoksessa Erkki Mäkinen (toim.), Pieniä tietojenkäsittelytieteellisiä tutkimuksia (Syksy 2008). Tampereen yliopisto, Tieto-jenkäsittelytieteen laitos, Raportti D-2008-12, Joulukuu 2008, 67–84. Saatavana osoitteesta:
http://www.cs.uta.fi/reports/dsarja/D-2008-12.pdf. Tarkistettu 9.4.2011.
[Matsumoto and Nishimura, 1998] Makoto Matsumoto and Takuji Nishimura, Mersenne Twister: A 623-dimensionally equidistributed uniform pseudo-random number generator.
ACM TOMACS 8, 1 (Jan. 1998), 3–30.
[McAdam, 2004] Puzzle history. American Jigsaw Puzzle Society. Available as http://www.jigsaw‐puzzle.org/jigsaw‐puzzle‐history.html. Checked 29.10.2010.
[Metropolis et al., 1953] N. Metropolis, A.W. Rosenbluth, A.H. Teller, M.N. Rosenbluth, and E.Teller, Equation of state calculations by fast computing machines. Journal of Chemical Physics 21, 6 (1953), 1087–1092.
[Mitchell, 1996] Melanie Mitchell, An Introduction to Genetic Algorithms. MIT Press, 1996.
[Monckton, 2007] Christopher Monckton, US $2 million EternityII prize competition rules.
Available as http://replay.waybackmachine.org/20090330135402/http://uk.eternityii.com/
Download.ashx?id=19934. Checked 25.3.2011.
[Muñoz et al., 2009] Jorge Muñoz, German Gutierrez and Araceli Sanchis, Evolutionary techniques in a constraint satisfaction problem: Puzzle Eternity II, In: Proceedings 2009 IEEE Congress on Evolutionary Computation, 2985–2991. Also available as:
http://e-archivo.uc3m.es/bitstream/10016/9915/3/evolutionary_gutierrez_2009.pdf.
Checked 20.3.2011.
[Savelsbergh and van Emde Boas, 1984] Martin W. P. Savelsbergh and Peter van Emde Boas, Bounded tiling, an alternative to satisfiability?, In: Proceedings, 2nd Frege Conference, vol. 20, 354–363.
[Sbalzarini et al., 2000] Ivo F. Sbalzarini, Sibylle Müller and Petros Koumoutsakos, Multi-objective optimization using evolutionary algorithms, In: Proceedings of the Summer Pro-gram, Center of Turbulence Research, 63–74.
[Schaus and Deville, 2008] Pierre Schaus and Yves Deville, Hybridization of CP and VLNS for Eternity II, Actes JFPC 2008.
[Selby, 2001] Alex Selby, Description of method. Available as http://www.archduke.org/eternity/method/desc.html. Checked 25.3.2011.
[Stegmann, 2007] Rob Stegmann, Rob’s puzzle page. Available as http://home.comcast.net/~stegmann/pattern.htm. Checked 19.11.2010.
[Takenaga and Walsh, 2006] Yasuhiko Takenaga and Toby Walsh, Tetravex is NP‐
complete. Information Processing Letters 99, 5 (September 2006), 171–174.
[Tetravex, 2008] Tetravex – GNOME Live! Available as http://live.gnome.org/Tetravex.
Checked 17.11.2010.
[The Sunday Times, 2005] The Sunday Times, £1m says this really is the hardest jigsaw.
Available as http://www.timesonline.co.uk/tol/news/uk/article745506.ece. Checked 25.3.2011.