Кристиан Вулф-Нилсен е създал алгоритъм за изчисляване на най-краткия път между две точки
(снимка: University of Copenhagen)
Датски изследовател от Университета в Копенхаген и двама негови колеги създадоха алгоритъм, който е в състояние да намери най-краткия път между две точки във всяка ситуация по оптимален начин. Изследователите се борят с тази задача от 40 години.
Как да съставя най-краткия маршрут, ако ситуацията на движение постоянно се променя? В отговор на това предизвикателство Кристиан Вулф-Нилсен и колегите му са създали алгоритъм, който е в състояние да вземе предвид всички промени и ефективно да обработва входящата информация, изразходвайки по-малко време и ресурси от всички съвременни програми. Изследването е публикувано в arxiv.org.
Една от класическите алгоритмични задачи включва изчисляване на най-краткия път между две точки. Изглежда, че това трябва да е съвсем просто, но програмите имат проблеми, ако маршрутът пресича променяща се мрежа – било то пътен възел или информационни потоци. Мнозина са се сблъсквали с факта, че навигаторите понякога водят водача не по най-краткия маршрут, поради което виртуалните помощници се превръщат в смущаващ софтуер.
Сега датските учени са разработили нов алгоритъм, който е в състояние да намери оптималния път между две точки. Оптимален е алгоритъмът, който изразходва възможно най-малко време и компютърна памет за изчисляване на най-добрия маршрут в мрежата. Това се отнася не само за пътни и транспортни мрежи, но също така и за интернет или друг вид мрежа.
Изследователите представят мрежата като динамичен граф. Това е абстрактно представяне на мрежа от ребра и възли. В контекста на транспорта ръбовете ще бъдат пътища, а възлите – пресечни точки. Динамичният граф може да се променя с течение на времето, така че новият алгоритъм отчита такива промени.
Като изразходва минималното количество изчислителни ресурси, програмата определя най-бързия път, отчитайки например промяната в дължината на ребрата на графа с течение на времето. За транспортната мрежа това е еквивалентно на образуването на задръствания.
Също така, според авторите на изследването, разработката може да се използва за оптимизиране на обработката на данни – алгоритъмът ще намали времето и изчислителните ресурси, необходими за операции с информационни потоци. Изследването беше представено на IEEE симпозиум по основи на компютърните науки.
благодаря за статията!