Traveling Salesman
Najdi nejkratší trasu, která navštíví každé město jednou · klasický problém obchodního cestujícího
O Problému obchodního cestujícího
Problém obchodního cestujícího je stručná optimalizační hádanka postavená na jednom z nejznámějších problémů v informatice · Problému obchodního cestujícího (TSP). Několik měst je rozeseto po mapě a vy začínáte doma. Vaším úkolem je naplánovat cestu, která navštíví každé město přesně jednou a vrátí se domů, s použitím nejkratší možné celkové vzdálenosti. Klepněte na města v pořadí, v jakém byste je projeli, a trasa se sama nakreslí; živý počítadlo vzdálenosti vám ukáže, jak dlouhá je vaše smyčka.
Proč trénuje váš mozek. Nalezení nejkratší trasy je čistě prostorové uvažování a plánování · musíte porovnávat celá pořadí mezi sebou, všímat si, kdy se trasa kříží a plýtvá vzdáleností, a hledat uspořádání, které nelze překonat. Neexistuje žádný vzorec k aplikaci; uvažujete přímo o geometrii, což je přesně ten druh optimalizačního myšlení, které TSP proslavilo.
Vyrovnejte se optimu a vyhrajte. Každá mapa je přesně vyřešena v zákulisí, takže kolo se počítá jako výhra pouze tehdy, když se vaše smyčka shoduje se skutečnou nejkratší trasou · stejně krátké trasy se všechny počítají. Pokud je vaše trasa delší, hra odhalí optimální trasu přes vaši vlastní, abyste viděli křížení, které jste měli rozmotat.
Mapa roste, jak stoupáte. Raná kola jsou čtyři nebo pět měst · dostatečně krátká na to, abyste je odhadli. Každých několik úrovní mapa získá další město a každá další zastávka násobí počet možných tras, takže nalezení nejkratší smyčky je těžší, čím déle vaše série trvá.
Součást rodiny her pro trénink mozku PlayMemorize. Běží zcela ve vašem prohlížeči, funguje offline jako progresivní webová aplikace.
FAQ
-
Jak hraji Problém obchodního cestujícího?
Začínáte u značky domova. Klepněte na ostatní města jedno po druhém v pořadí, v jakém byste je navštívili · trasa se kreslí, jak postupujete, a počítadlo vzdálenosti se aktualizuje. Jakmile je každé město na trase, stiskněte Zkontrolovat. Pokud se vaše smyčka shoduje s nejkratší možnou trasou, vyhrajete kolo. -
Co je Problém obchodního cestujícího?
Je to klasický optimalizační problém: vzhledem k sadě měst najděte nejkratší možnou trasu, která navštíví každé z nich přesně jednou a vrátí se na začátek. Je proslule obtížný, protože počet možných tras exploduje s přidáváním měst · tato hra vám umožní řešit malé, řešitelné instance ručně. -
Jak hra ví, že je trasa optimální?
Každá mapa je dostatečně malá, aby hra vypočítala přesnou nejkratší trasu kontrolou každého možného pořadí. Vaše smyčka vyhrává, když se její délka shoduje s tímto optimem. Pokud se dvě různé trasy shodují v nejkratší délce, kterákoli z nich se počítá jako výhra. -
Co se stane, když moje trasa není nejkratší?
Kolo se počítá jako prohra a hra nakreslí skutečnou optimální trasu přes vaši vlastní, abyste mohli porovnat. Hledejte místa, kde se vaše smyčka kříží · rozmotání téměř vždy zkrátí trasu. Použijte Zpět k odstranění posledního města nebo Vymazat k restartování trasy. -
Ztěžuje se to, jak postupuji?
Ano. Každé úspěšné kolo zvýší vaši úroveň a každých několik úrovní mapa získá další město. Jelikož každá další zastávka výrazně zvyšuje počet možných tras, nejkratší smyčku je stále těžší najít, čím déle vaše série trvá. -
Funguje to offline?
Ano. PlayMemorize je progresivní webová aplikace. Nainstalujte jednou a Problém obchodního cestujícího hraje kdekoli bez připojení k internetu.