Un bilet — tot New York-ul: cel mai lung traseu în metrou fără repetări

Vă amintiți cum în copilărie încercam să mergem cu autobuzul până la capăt? Un dezvoltator pe nume John a mers mai departe și a creat un traseu optim care trece prin numărul maxim de stații ale metroului din New York, fără a repeta vreuna.

Ce a ieșit?

• Traseul include peste 200 de stații.
• Va dura aproximativ 14 ore.
• Folosește toate cele 24 de linii de metrou.

Proiectul SingleRide nu este doar o provocare distractivă, ci și o demonstrație excelentă a posibilităților algoritmilor pe grafuri. Practic, este o problemă de drum hamiltonian într-o rețea de transport — o problemă NP-completă clasică, pe care autorul a rezolvat-o euristic.

Pentru un specialist IT, acest proiect este un reminder cum algoritmii pot optimiza rutele nu doar pentru metrou, ci și pentru livrări, logistică sau chiar pentru planificarea acoperirii testelor în codul vostru.

Comentariul studioului METABYTE: Dacă credeați că grafurile sunt utile doar pentru interviuri, iată un exemplu viu al utilității lor practice. Vreți să vă optimizați procesele de afaceri cu ajutorul algoritmilor — știm cum s-o facem.