Математици решиха 40-годишна задача за най-краткия път

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

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

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

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

[related-posts]

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

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

Също така, според авторите на изследването, разработката може да се използва за оптимизиране на обработката на данни – алгоритъмът ще намали времето и изчислителните ресурси, необходими за операции с информационни потоци. Изследването беше представено на IEEE симпозиум по основи на компютърните науки.