Traveling Salesman
Znajdź najkrótszą trasę odwiedzającą każde miasto raz · klasyczny problem komiwojażera
O Komwojażerze
Komwojażer to zwięzła łamigłówka optymalizująca trasy, oparta na jednym z najsłynniejszych problemów informatyki · Problemie Komiwojażera (TSP). Garść miast jest rozrzucona po mapie, a Ty zaczynasz w domu. Twoim zadaniem jest zaplanowanie trasy, która odwiedzi każde miasto dokładnie raz i wróci do domu, używając najkrótszej możliwej całkowitej odległości. Dotknij miast w kolejności, w jakiej byś je przejechał, a trasa sama się narysuje; licznik odległości na żywo powie Ci, jak długa jest Twoja pętla.
Dlaczego trenuje Twój mózg. Znalezienie najkrótszej trasy to czyste rozumowanie przestrzenne i planowanie · musisz ważyć całe układy względem siebie, zauważać, kiedy trasa przecina się i marnuje odległość, oraz szukać układu, którego nie da się pobić. Nie ma wzoru do zastosowania; rozumujesz bezpośrednio o geometrii, co jest dokładnie tym rodzajem myślenia optymalizacyjnego, które TSP uczyniło sławnym.
Dopasuj optimum, aby wygrać. Każda mapa jest dokładnie rozwiązywana za kulisami, więc runda liczy się jako wygrana tylko wtedy, gdy Twoja pętla odpowiada prawdziwej najkrótszej trasie · równie krótkie trasy wszystkie się liczą. Jeśli Twoja trasa jest dłuższa, gra ujawnia optymalną trasę nad Twoją, abyś mógł zobaczyć skrzyżowanie, które powinieneś był rozplątać.
Mapa rośnie wraz z Twoim postępem. Wczesne rundy to cztery lub pięć miast · wystarczająco krótkie, aby ocenić wzrokowo. Co kilka poziomów mapa zyskuje kolejne miasto, a każdy dodatkowy przystanek zwielokrotnia liczbę możliwych tras, więc znalezienie najkrótszej pętli staje się trudniejsze, im dłużej trwa Twoja passa.
Część rodziny gier trenujących mózg PlayMemorize. Działa całkowicie w Twojej przeglądarce, działa offline jako progresywna aplikacja internetowa.
FAQ
-
Jak grać w Komwojażera?
Zaczynasz od znacznika domu. Dotykaj kolejnych miast jedno po drugim w kolejności, w jakiej byś je odwiedził · trasa rysuje się na bieżąco, a licznik odległości aktualizuje się. Gdy każde miasto znajdzie się na trasie, naciśnij Sprawdź. Jeśli Twoja pętla odpowiada najkrótszej możliwej trasie, wygrywasz rundę. -
Czym jest Problem Komiwojażera?
Jest to klasyczny problem optymalizacyjny: mając dany zbiór miast, znajdź najkrótszą możliwą trasę, która odwiedza każde z nich dokładnie raz i wraca do punktu początkowego. Jest on słynnie trudny, ponieważ liczba możliwych tras eksploduje wraz z dodawaniem miast · ta gra pozwala Ci ręcznie zmierzyć się z małymi, rozwiązywalnymi instancjami. -
Skąd gra wie, że trasa jest optymalna?
Każda mapa jest wystarczająco mała, aby gra obliczyła dokładnie najkrótszą trasę, sprawdzając każdą możliwą kolejność. Twoja pętla wygrywa, gdy jej długość odpowiada temu optimum. Jeśli dwie różne trasy mają taką samą najkrótszą długość, każda z nich liczy się jako wygrana. -
Co się stanie, jeśli moja trasa nie jest najkrótsza?
Runda liczy się jako przegrana, a gra rysuje prawdziwą optymalną trasę nad Twoją, abyś mógł porównać. Szukaj miejsc, w których Twoja pętla przecina się · rozplątanie prawie zawsze skraca trasę. Użyj Cofnij, aby usunąć ostatnie miasto, lub Wyczyść, aby rozpocząć trasę od nowa. -
Czy gra staje się trudniejsza w miarę postępów?
Tak. Każda udana runda podnosi Twój poziom, a co kilka poziomów mapa zyskuje kolejne miasto. Ponieważ każdy dodatkowy przystanek gwałtownie zwiększa liczbę możliwych tras, najkrótszą pętlę staje się coraz trudniej znaleźć, im dłużej trwa Twoja passa. -
Czy działa offline?
Tak. PlayMemorize to progresywna aplikacja internetowa. Zainstaluj raz, a Komwojażer działa wszędzie bez połączenia z internetem.