Учен от университета в Копенхаген, заедно с двама свои колеги, създаде алгоритъм, който е в състояние да намери най-краткия път между две точки по оптимален начин във всяка ситуация. Изследователите се борят с тази задача в продължение на 40 години.

Как да се състави най-краткият маршрут, ако ситуацията на движение постоянно се променя? Сега ученият е създал алгоритъм, който е в състояние да вземе предвид всички промени и ефективно да обработва входящата информация, изразходвайки по-малко време и ресурси от всички съвременни програми.

Една от класическите алгоритмични задачи включва изчисляване на най-краткия път между две точки. Изглежда, че това трябва да е съвсем просто, но програмите имат проблеми, ако маршрутът минава през променяща се мрежа - било то пътища и кръстовища или потоци от информация.

Мнозина са се сблъсквали с факта, че навигаторите понякога водят водача по не най-краткия маршрут, поради което тези програми се превръщат от помощ в пречещ софтуер.

Датският учен е разработил нов алгоритъм, който е в състояние да намери оптималния път между две точки. В този контекст оптимален е алгоритъмът, който изразходва възможно най-малко време и компютърна памет за изчисляване на най-добрия маршрут в мрежата. Това се отнася не само за пътни и транспортни мрежи, но също така и за Интернет или друг вид мрежа.

Изследователите представиха мрежата като така наречената динамична графика. Това е абстрактно представяне на мрежа от ръбове и възли. Ако преведем това в транспортна аналогия, тогава ръбовете ще бъдат пътища, а възлите - пресечни точки. Динамичната графика може да се променя с течение на времето, така че новият алгоритъм може да отчита такива промени.

Разширявайки минималното количество изчислителни ресурси, програмата определя най-бързия път, като отчита например промяната в дължината на ръбовете на графиката с течение на времето. За транспортната мрежа това е еквивалентно на образуването на задръствания. Също така, според авторите на изследването, разработката може да се използва за оптимизиране на обработката на данни - алгоритъмът ще намали времето и изчислителните ресурси, необходими за операции с информационни потоци.

Изследването беше представено на IEEE Symposium on Foundations of Computer Science.

Превод: БЛИЦ