Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Упражнения. о 18.61. Проанализируйте преимущества и недостатки обобщенной реализации поиска на графе, в основу которой положена следующая стратегия
|
|
о 18.61. Проанализируйте преимущества и недостатки обобщенной реализации поиска на графе, в основу которой положена следующая стратегия. " Перенести ребро из бахромы в дерево. Если вершина, к которой оно ведет, не посещалась, выйти на эту вершину и поместить в бахрому все инцидентные ей ребра".
РИСУНОК 18.28. РАЗМЕРЫ БАХРОМЫ В УСЛОВИЯХ ПРИМЕНЕНИЯ ПОИСКА ГЛУБИНУ, РАНДОМИЗИРОВАННОГО ПОИСКА И ПОИСКА В ШИРИНУ
Изображенные на рисунке диаграммы отображают наполнение бахромы во время поисков, представленных на рис. 18.13, 18.24 и 18.29, показывают, какое огромное влияние оказывает выбор структуры данных бахромы на поиск на графе. Когда используется стек в условиях поиска в глубину (верхняя диаграмма), происходит наполнение бахромы с самого начала поиска, поскольку мы находим новые узлы на каждом шаге, затем, когда поиск завершается, удаляем из бахромы все, что там было. Когда используется рандомизированная очередь (в центре), максимальный размер очереди намного меньше. В случае применения очереди FIFO в условиях поиска в ширину (внизу) максимальный размер очереди еще ниже, а в процессе поиска обнаруживаются новые узлы
Часть 5. Алгоритмы на графах
|
| РИСУНОК 18.29. РАНДОМИЗИРОВАННЫЙ ГРАФ ПОИСКА Данный рисунок служит иллюстрацией динамики развития процесса поиска на рандомизированном графе (слева), выполненной в том же стиле, что и рис. 18.13 и 18.24. Полученное дерево поиска по своей форме занимает место где-то между поиском в глубину и поиском в ширину. Динамические характеристики трех этих алгоритмов, которые отличаются только структурой данных, необходимой для того, чтобы работу можно было выполнить, вряд ли отличаются чем-то еще. |