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

Метод поиска в глубину

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

При поиске в глубину (depth-first search) анализируется первый по списку сосед текущей вершины, затем – его первый сосед и т.д. Если у некоторой вершины нет соседей, аналогичным образом анализируется второй сосед вершины, рассмотренной до нее. Таким образом, процедура поиска сразу же устремляется к вершинам, далеким от стартовой (то есть «в глубину»), и, лишь достигнув вершины, не имеющей соседей, возвращается назад.

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

При вызове функции DepthFirstSearch() ей необходимо передать стартовую вершину и число 0:

Если в качестве результата функция вернула значение false, целевая вершина не найдена. В противном случае поиск закончился успешно; путь от стартовой вершины до целевой храниться в массиве Path.

Главный плюс процедуры поиска в глубину состоит в малом расходе памяти. На каждом шаге приходится хранить только вершины находящиеся на пути от стартовой вершины до текущей, да номера их просматриваемых в данный момент соседей; еще можно вспомнить о некоторых затратах на рекурсию.

 


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


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

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