Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Метод поиска в ширину

Читайте также:
  1. FAST (Методика быстрого анализа решения)
  2. I Методические указания к решению практических
  3. I. 2. 1. Марксистско-ленинская философия - методологическая основа научной психологии
  4. I. 2.4. Принципы и методы исследования современной психологии
  5. I. МЕТОДОЛОГИЧЕСКОЕ ВВЕДЕНИЕ
  6. I. Методы изучения фактического питания
  7. I. ОРГАНИЗАЦИОННО-МЕТОДИЧЕСКИЙ РАЗДЕЛ

При поиске в ширину (breadth-first search) сначала анализируются все соседи текущей вершины. Затем – соседи соседей соседей и т.д. Пока процедура не рассмотрит все вершины, находящиеся на расстоянии n ребер от стартовой, перехода к более далеким вершинам, длина пути до которых (в ребрах) равна n+1, не произойдет.

Если упрощенно записать текст программы на псевдокоде, то он будет выглядеть следующим образом:

Эта процедура застрахована от «застревания». Даже если какая-то вершина попадет в список просматриваемых соседей вторично, все равно ее приоритет окажется более низким по сравнению с вершинами, уже находящимися там.

Проблема поиска в ширину (часто делающая его непригодным на практике) заключается в солидных затратах памяти. На каждом шаге процедура сохраняет в списке все вершины, находящиеся на некоторой «глубине» от стартовой. Если граф, к примеру, имеет вид бинарного дерева (очень частая ситуация на практике), количество хранимых вершин растет экспоненциально. На первом шаге нам понадобится держать в памяти лишь стартовую вершину, затем – ее двух потомков, затем – четыре вершины и т.д. Уже на десятом шаге размер списка составит 1024 элемента, а на двадцатом - 1048576 элементов. А ведь двадцать вершин «вглубь» - это, в принципе, не так много для процедуры просмотра (особенно если речь идет всего лишь о бинарном дереве, а не о более ветвистой структуре данных). Кроме того, приведена упрощенная реализация, которая только ищет целевую вершину, но не строит маршрута от стартовой вершины до нее. Если также строить маршрут, придется потратить даполнительную память.

 

 


Дата добавления: 2015-08-05; просмотров: 73 | Нарушение авторских прав


Читайте в этой же книге: Метод наискорейшего подъема | Решение контрольных примеров и проверка правильности функционирования программы | Руководство пользователя | unit AppMain; |
<== предыдущая страница | следующая страница ==>
Введение| Метод поиска в глубину

mybiblioteka.su - 2015-2024 год. (0.006 сек.)