Uusi putkaposti on ilmestynyt:
https://www.ohjelmointiputka.net/postit/tehtava.
Tehtävä on peräisin tämän syksyn Datatähdestä.
Ratkaisua voi etsiä myös tämän sivun avulla:
Näen tuosta kilpailusta ja etenkin tuosta tehtävästä vieläkin painajaisia :(
Ratkesipa helposti käsin.
Ohjelma hyödyntää tietoa oikeasta siirtojen minimimäärästä, käyttää muistia noin 230 mt, ja ratkaisu löytyy yhdellä säikeellä noin 18 sekunnissa. Mitens teillä?
Mulla kesti aika kauan löytää toimiva heuristiikka A* haulle, kun en osaa ratkaista edes yksinkertaista tilannetta käsin :P
Tilan pisteyttämisessä oli itsellänikin suurimmat ongelmat. Puhdas A* jäi kokeilematta, koska en luottanut tuohon pisteytykseen tarpeeksi. Sen sijaan rajoitetun syvyyshaun ja parhaalta näyttävän haaran valinnan vuorottelu tuotti 16-ratkaisun noin vartin jauhettuaan. Kielenä Python (PyPy), algoritmin muistinkulutus muutama kilotavu.
Metabolixia lainaten: "Ratkesipa helposti käsin."
Triviaaliratkaisun (24 siirtoa) keksi vähän kokeilemalla, siitä putosi 4 siirtoa pois, kun muutti vähän siirtojen järjestystä. Viimeisten 4 ylimääräisen siirron poistaminen onnistui kuitenkin vasta, kun otti avuksi kynän ja paperia.
Löysin käsin 18-siirtoisen parissa minuutissa, mutta sen parantaminen ei vaikuttanut helpolta enkä ollut varma optimaalisuudesta. IDDFS-haku yksinkertaisella heuristiikalla löytää 16-siirtoisen 5 sekunnissa. Muistinkäyttö on olematon.
Sain muistinkäytön 32 megaan ja ajan noin 4.5 sekunttiin, mutta tulos löytyy vähän tuurilla. Muistia kuluu paljon noihin A* haun tiloihin...
msdos464 kirjoitti:
Mulla kesti aika kauan löytää toimiva heuristiikka A* haulle, kun en osaa ratkaista edes yksinkertaista tilannetta käsin :P
Manhattan distance?
jalski kirjoitti:
msdos464 kirjoitti:
Mulla kesti aika kauan löytää toimiva heuristiikka A* haulle, kun en osaa ratkaista edes yksinkertaista tilannetta käsin :P
Manhattan distance?
Mielestäni se antaa turhan paljon rangaistusta siitä että oikeat luvut ovat kivasti jonossa, mutta jos ne ovat väärässä paikassa. En ole varma että johtaako se väistämättä pidempään suoritusaikaan.
funktio kirjoitti:
Löysin käsin 18-siirtoisen parissa minuutissa
Taisi sitten käydä tuuri, kun 16 siirron ratkaisu löytyi yhdellä ensimmäisistä lähestymistavoista, joita keksin kokeilla. Oli sellainen kutina, että noin siisti alkuasetelma varmaankin ratkeaa jollain yllättävän yksinkertaisella sarjalla...
Mittasin 20 ajoa, ja tulokset olivat 334-611 ms. Mittasin Javan omalla metodilla System.currentTimeMillis().
Aihe on jo aika vanha, joten et voi enää vastata siihen.