Start
Badania
Studenci
Konkursy
Galeria
Gry/projekty
Linki
Kontakt
Historia
|
Zimne Piwnice to jedno z zadań na Obozie Naukowo-Treningowym im. Antoniego Kreczmara
w roku 2013. Mamy labirynt 20x15, w którym jest 6 skarbów i strażnik. Bajtur
i strażnik na przemian wykonują ruchy w 8 kierunkach, przy czym strażnik zawsze
rusza się tak, żeby zminimalizować euklidesową odległość od poszukiwacza (w przypadku
remisu stoi w miejscu). Oficjalnym zadaniem algorytmicznym było napisanie programu,
który dla danej planszy (w formacie ASCII) określi, ile ruchów Bajtur potrzebuje, by zebrać największą
możliwą liczbę skarbów i uciec z labiryntu. Dodatkowy konkurs polegał na tym, by stworzyć
taką planszę, na której
Bajtur będzie musiał wykonać jak największą liczbę ruchów.
Na tej stronie możesz wpisać własny labirynt i zobaczyć, jak Bajtur ucieka w nim przed strażnikiem. Pokazana jest najkrótsza możliwa trasa Bajtura (wśród takich, które zdobywają największą możliwą liczbę skarbów). Zachęcam do obejrzenia labiryntu, w którym potrzeba 1115 ruchów i spróbowania wymyślenia czegoś lepszego (jest możliwe ręczne wymyślenie czegoś lepszego). Zamierzam co jakiś czas patrzeć na wysyłane labirynty, także jak zobaczę coś ciekawego, to dodam do sekcji "rozwiązania" poniżej (można się podpisać pod labiryntem). # - ściana, A..Z - strażnik, $ - skarb, < - wejście, > - wyjście Rozwiązania: II miejsce na ONTAKu zajął Michał Zieliński (1115 ruchów) (plansza wygenerowana prostym algorytmem genetycznym). I miejsce na ONTAKu zajął Paweł Burzyński (1195 ruchów). Poprzez ulepszenia rozwiązania Pawła udało mi się uzyskać labirynt, na którym Bajtur musi wykonać 1636 ruchów. W sierpniu 2015 Tomek Czajka znalazł dużo lepsze rozwiązanie (4888 ruchów). Rozwiązanie zostało znalezione przy użyciu symulowanego wyżarzania (Simulated Annealing). Tweet |
Start
Research
Students
Contests
Gallery
Games & projects
Links
Contact
History