Двама програмисти нарисуваха най-дългия земен и морски път на Земята

През 2012 г. потребител на Reddit публикува карта, която претендира, че показва най-дългата права линия, която минава само по вода, без да докосва земната повърхност. Заинтригувани от тази идея, двама компютърни специалисти разработиха алгоритъм, който потвърждава този маршрут. В добавка те начертават и най-дългата права линия по суша.

Това са изследователите Роан Чабуксоур от Обединения технологичен център на Ирландия и Кушал Мукарджи от Изследователсткия институт към IBM в Индия. Те създадоха алгоритъма към картата на потребителя kepleronlyknows, който в реалния живот всъщност е Патрик Андерсън. Маршрутът от 32 000 км тръгва от крайбрежието на Пакистан и преминава покрай най-южните точки на Африка и Южна Америка, за да завърши транс-тихоокеанското си пътуване до Сибир. На традиционна 2D карта пътеката не изглежда като права линия, но причината е, че формата на земята все пак не е плоска.

Когато Андерсън публикува картата, той не предоставя никакви доказателства, че става дума действително за права линия и как точно изчислява маршрута. Затова и Чабуксуор и Мукарджи започват изследването си, за да проверят как точно може да се изпълни заданието – най-дълъг маршрут по права линия, в близост до сушата, но не и през нея. Резултатът е на лице.

За начин за изчисляване на правата линия използват т. нар. метод на грубата сила (brute force methode), генериращ всички възможни разстояния на дадена точка в океана и отдалечеността й от сушата. Двамата изследователи са работили с карта от Американската метеорологична администрация, с размер на пиксела от 1,8 км. Принципът е бил следният – всичко, над морското равнище, се считало за земя и всичко под вода – за вода.

За да изчислят оптималния път е имало 233 280 000 генерирани цикли и изумителния брой от 5 038 848 000 000 точки, които начертават този път.

Всъщност задачата им прилича на т. нар. Travelling salesman problem – или проблема на пътуващия търговец – една от най-известните задачи в комбинаториката, която изисква търсенето на най-добрия маршрут, чрез който да се обиколи по веднъж и по най-краткия път всяка дадена точка в определено пространство. Знаменитият ирландски математик  Уилям Хамилтън (1805–1865) пуска в продажба своеобразна главоблъсканица като правилен додекаедър (дванадесетостен с 20 върха и стени правилни петоъгълници), направен от дърво. Всеки връх на хамилтъновия додекаедър означава някой голям град върху земното кълбо. Така наречената задача за пътуващият търговец се състои в това да се обиколят градовете по веднъж и да се върне в първоначалния град, т.е. търси се т. нар. хамилтънов цикъл върху додекаедъра.

Тъй като задачата на Чабуксуор и Мукарджи се оказва твърде сложна за изчисление, те я оптимизират с т. нар. технология „branch-and-bound“. Компютърните учени използват алгоритми с разклонения и връзки, за да оптимизират задачата – тя е разделена на по-малки задачи, а всяка решена задача елиминира резултатите от останалите.

Въоръжени с тази техника и лаптоп Чабуксуор и Мукарджи изчисляват морския маршрут само за 10 минути. И завладяващо, техният алгоритъм стигна до същия отговор като този, показан в картата на Андерсън, показващ права линия, която се простира от Пакистан до Русия по 32 089,7 км. път.

Със същия алгоритъм изследователите също изчислиха възможно най-дългата права линия на сушата, без да засягат големи водни басейни, като например езеро или море. Пътят, който компютърът начерта за 45 минути, започва от Китай, минава през Монголия, Казахстан и Русия, продължава през Полша, Чехия, Германия, Австрия, Лихтенщайн, Швейцария, Франция, Испания и накрая завършва близо до Сагреш в Португалия. Това са общо 15 държави и едва 11 241 километра разстояние.

Чабуксуор и Мукарджиго наричат ​​“път за каране“, но това е много малко вероятно, като се имат предвид многобройните препятствия, като планините и горите, които със сигурност ще срещнете по него. Също така правата линия пресича редица реки, които изследователите изключват като променлива. Най-вероятно ще са необходими някои големи заобикалки, за да се намерят мостове или да се избегнат някои опасни и труднодостъпни терени.

Същото се отнася и за морския път – макар и права линия, вероятно не е най-безопасният или най-идеалният маршрут, тъй като пресича през коварните води край Антарктика. Нещо повече, най-бързият морски маршрут от Пакистан до Сибир ще включва пътуване през индонезийските води и Филипинско море. Както изследователите заключават в своето изследване: Това е само математическо упражнение, а авторите му не препоръчват каране или плаване по така начертаните маршрути.

Решение на проблема на амбулатния търговец

Хамилтън

Роан Чабуксоур                              Кушал Мукарджи

{module [180]}