Почему BFS дает разное время выполнения для разных позиций узлов на одном графике?
У меня есть линейный график, который состоит из 100 узлов, которые помечены от 0 до 99.
Который выглядит примерно так:
0--1--2--3....98--99
И я использую алгоритмы BFS, DFS, Dijkstra, чтобы найти кратчайший путь от узла 0 ко всем остальным узлам в первом случае, и я делаю то же самое для узла 55 (начального узла) во втором случае и узла 99 для третьего.
Но в BFS время, затрачиваемое в последнем случае, вдвое больше времени, затрачиваемого в первом случае, но в обоих случаях положение узла графически одинаково. Я приложил время работы в 
.
Циклы for и while в BFS посещаются одинаковое количество раз, я хотел бы знать, почему это занимает разное время в трех случаях?
Кстати, он реализован на C ++, а вектор векторов используется для хранения графа.
Заранее большое спасибо.
Решение
Прежде всего: вы запускали его несколько раз? Результаты могут сильно отличаться.
В любом случае, есть большая вероятность, что это связано с проблемами кеширования. Компьютеры обычно работают достаточно хорошо, когда вы обращаетесь к массиву с 0, потому что они немедленно кэшируют (часть) массив из индекса, к которому вы обращаетесь. Но если вы начнете с конца массива, он не будет иметь весь массив в быстром кеше. (это не отличается для вектора, так как вектор — это просто динамический размерный массив)
Кроме того, вы не должны тестировать скорость алгоритма таким образом, вы не можете сравнивать их вот так. Потому что если вы впервые запустите BFS, он просто еще не кэширует весь массив. Но когда вы запустили DFS, весь массив, вероятно, находится в быстром кеше для процессора. Я бы порекомендовал взять более крупный график и проверить наличие разреженных и плотных графиков. Кроме того, я хотел бы написать отдельные программы для каждого алгоритма, чтобы проверить с помощью такой утилиты, как time,
Другие решения
Других решений пока нет …