English version  zmień styl strony

© Eryk Kopczyński  strona domowa 

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).




chce dac sie szpiegowac serwisom spolecznosciowym
(udostepnij na Facebook/Twitter/Google+)



Start

Research

Students

Contests

Gallery

Games & projects

Links

Contact

History