Автор работы: Пользователь скрыл имя, 11 Января 2014 в 04:39, реферат
1. Графы являются моделью представления данных, основанных на отношениях между элементами множеств.
2. Для представления графов используется несколько способов: список ребер, матрица смежности, матрица инцидентности.
3. Для организации поиска на графах используются обходы в глубину и в ширину.
4. Реализацию обходов можно осуществлять рекурсивными и нерекурсивными алгоритмами.
5. От вида графа и способа его представления зависит временная сложность выполнения алгоритма.
Введение………………………………………………………………………... 3
1 Алгоритмы обхода графа……………………………………………………. 5
1.1 Поиск в глубину…………………………………………………….. 6
1.2 Поиск в ширину……………………………………………………... 7
2 Алгоритмы нахождения кратчайшего пути………………………………... 9
2.1 Алгоритм Дейкстры………………………………………………… 10
2.2 Алгоритм Флойда…………………………………………………… 12
2.3 Переборные алгоритмы…………………………………………….. 15
Заключение…………………………………………………………………….. 20
12. Переборные алгоритмы являются алгоритмами поиска оптимального решения.
13. Волновой алгоритм является переборным алгоритмом, который основан на поиске в ширину и состоит из двух этапов: распространение волны и обратный ход.
14. Перебор методом поиска в ширину, по сравнению с перебором с возвратом, требует больше вспомогательной памяти для хранения информации, однако, он работает быстрее, так как исключается посещение одной и той же вершины более чем один раз.