Кристиан Вулф-Нилсен е създал алгоритъм за изчисляване на най-краткия път

Кристиан Вулф-Нилсен е основал логаритъм за пресмятане на най-краткия път сред две точки
(снимка: University of Copenhagen)

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

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

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

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

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

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