262
правки
Изменения
→Ссылки
Во время фазы отладки мы заботимся о точности, а не о скорости, поэтому не добавляем новых сокращающих рёбер и используем точный алгоритм.
Поэтому, время работы алгоритма как минимум <tex>\Omega(\delta^{2})</tex>
==Итог==
{| border="1" cellspacing="0" cellpadding="5"
|+ Сравнение различных эвристик для поиска кратчайшего пути на карте США
! Метод !! Время препроцессинга, м !! Память для препроцессинга, MB !! Сканируемые запросом вершины, шт !! Время запроса, мс
|-
| Алгоритм Дейкстры || - || 536 || 11 808 864 || 5440,5
|-
| ALT(16 ориентиров) || 18 || 2563 || 187 968 || 295,45
|-
| Reach || 28 || 893 || 2 405 || 1,77
|-
|}
==Ссылки==
