<
  • Главная
Статьи

WikiZero - Пошук в глибину

  1. Нерекурсивні варіанти [ правити | правити код ]
  2. Пошук в глибину з мітками часу. Класифікація ребер [ правити | правити код ]

open wikipedia design.

Пошук в глибину ( англ. Depth-first search, DFS) - один з методів обходу графа . Стратегія пошуку в глибину, як і випливає з назви, полягає в тому, щоб йти «вглиб» графа, наскільки це можливо. Алгоритм пошуку описується рекурсивно: перебираємо всі вихідні з даної вершини ребра. Якщо ребро веде в вершину, яка не була розглянута раніше, то запускаємо алгоритм від цієї нерозглянутих вершини, а після повертаємося і продовжуємо перебирати ребра. Повернення відбувається в тому випадку, якщо в даній вершині не залишилося ребер, які ведуть в нерозглянутих вершину. Якщо після завершення алгоритму не всі вершини були розглянуті, то необхідно запустити алгоритм від однієї з нерозглянутих вершин [1] .

нехай заданий граф G = (V, E) {\ displaystyle G = (V, E)} нехай заданий   граф   G = (V, E) {\ displaystyle G = (V, E)}   , Де V {\ displaystyle V}   - безліч вершин графа, E {\ displaystyle E}   - безліч ребер графа , Де V {\ displaystyle V} - безліч вершин графа, E {\ displaystyle E} - безліч ребер графа. Припустимо, що в початковий момент часу всі вершини графа пофарбовані в білий колір. Виконаємо такі дії:

  1. Пройдемо по всіх вершин v ∈ V {\ displaystyle v \ in V} .

Процедура DFS (параметр - вершина u ∈ V {\ displaystyle u \ in V} Процедура DFS (параметр - вершина u ∈ V {\ displaystyle u \ in V}   ) )

  1. Перефарбовувати вершину u {\ displaystyle u} в сірий колір.
  2. Для будь-якої вершини w {\ displaystyle w} , суміжній з вершиною u {\ displaystyle u} і пофарбованої в білий колір, рекурсивно виконуємо процедуру DFS (w) [2] .
  3. Перефарбовувати вершину u {\ displaystyle u} в чорний колір.

Часто використовують двоколірні мітки - без сірого, на 1-му кроці фарбують відразу в чорний колір.

Нерекурсивні варіанти [ правити | правити код ]

На великих графах пошук в глибину серйозно навантажує стек викликів . Якщо є ризик переповнення стека , Використовують нерекурсівние варіанти пошуку.

Перший варіант: можна симулювати стек виклику програмно: для кожної з сірих вершин в стеці буде зберігатися її номер u {\ displaystyle u} Перший варіант: можна симулювати стек виклику програмно: для кожної з сірих вершин в стеці буде зберігатися її номер u {\ displaystyle u}   і номер поточної суміжній вершини w {\ displaystyle w} і номер поточної суміжній вершини w {\ displaystyle w} .

Процедура DFS (параметр - вершина u ∈ V {\ displaystyle u \ in V} Процедура DFS (параметр - вершина u ∈ V {\ displaystyle u \ in V}   ) )

  1. Кладемо на стек пару (u, ∅) {\ displaystyle (u, \ varnothing)} . Перефарбовувати вершину u {\ displaystyle u} в сірий колір.
  2. Поки стік не порожній ...
    1. Беремо верхню пару (v, w) {\ displaystyle (v, w)} , Не витягуючи її з стека.
    2. Знаходимо вершину w '{\ displaystyle w'} , Суміжну з v {\ displaystyle v} і наступну за w {\ displaystyle w} .
      1. Якщо такої немає, витягаємо (v, w) {\ displaystyle (v, w)} з стека, перефарбовувати вершину v {\ displaystyle v} в чорний колір.
      2. В іншому випадку присвоюємо w: = w '{\ displaystyle w: = w'} , Прямо в стеці.

Другий варіант: можна в кожній з «сірих» вершин тримати поточний w {\ displaystyle w} Другий варіант: можна в кожній з «сірих» вершин тримати поточний w {\ displaystyle w}   і покажчик на попередню (ту, з якої прийшли) і покажчик на попередню (ту, з якої прийшли).

Третій варіант працює, якщо вистачає двоколірних міток.

Процедура DFS (параметр - вершина u ∈ V {\ displaystyle u \ in V} Процедура DFS (параметр - вершина u ∈ V {\ displaystyle u \ in V}   ) )

  1. Кладемо на стек вершину u {\ displaystyle u} .
  2. Поки стік не порожній ...
    1. Беремо верхню вершину v {\ displaystyle v} .
    2. Якщо вона біла ...
      1. Перефарбовувати її в чорний колір.
      2. Кладемо в стек всі суміжні з v {\ displaystyle v} білі вершини.

Пошук в глибину з мітками часу. Класифікація ребер [ правити | правити код ]

Для кожної з вершин встановимо два числа - «час» входу e n t r y [u] {\ displaystyle entry [u]} Для кожної з вершин встановимо два числа - «час» входу e n t r y [u] {\ displaystyle entry [u]}   і «час» виходу l e a v e [u] {\ displaystyle leave [u]} і «час» виходу l e a v e [u] {\ displaystyle leave [u]} .

Модифікуємо процедуру DFS так.

  1. Збільшуємо «поточний час» на 1. e n t r y [u] = t {\ displaystyle entry [u] = t} .
  2. Перефарбовувати вершину u {\ displaystyle u} в сірий колір.
  3. Для будь-якої вершини v {\ displaystyle v} , суміжній з вершиною u {\ displaystyle u} і пофарбованої в білий колір, виконуємо процедуру DFS (v).
  4. Перефарбовувати вершину u {\ displaystyle u} в чорний колір.
  5. Збільшуємо «поточний час» на 1. l e a v e [u] = t {\ displaystyle leave [u] = t} .

Вважаємо, що граф орієнтований. Очевидно, для будь-якої вершини, з якої ми не вийшли в момент t, e n t r y [u] ⩽ t <l e a v e [u] {\ displaystyle entry [u] \ leqslant t <leave [u]} Вважаємо, що граф орієнтований . Також неможливо скрёстное нерівність: e n t r y [u] <e n t r y [v] <l e a v e [u] <l e a v e [v] {\ displaystyle entry [u] <entry [v] <leave [u] <leave [v]} . Популярні на кроці 3 дуги uv можуть бути:

Ребра неориентированного графа можуть бути ребрами дерева і зворотними, але не прямими і перехресними. [3] Щоб розрізняти ребра неорієнтованого графа, досить зазначених вище трьох-або двоколірних відміток. Ребро, що йде в білу вершину, - ребро дерева. В сіру (чорну в двокольоровому варіанті) - зворотне. В чорну - такого не буває. [4]

алгоритм Косарайю вимагає сортування вершин в зворотному порядку за часом виходу. Метка входа і типи ребер потрібні в алгоритмах пошуку точок зчленування і мостів .

Пошук в глибину обмежено застосовується як власне пошук, найчастіше на деревовидних структурах: коли відстань між точками малó, пошук в глибину може «блукати» десь далеко.

Зате пошук в глибину - хороший інструмент для дослідження топологічних властивостей графів. наприклад:

Пошук в глибину - природний вибір, коли агент (людина або робот) особисто ходить по лабіринту і бачить те, що безпосередньо поруч з ним. «Правило лівої руки» (йти, ведучи лівою рукою по стінці) буде пошуком в глибину, якщо лабіринт деревовидний (немає кружним шляхів).



Новости
  • Виртуальный хостинг

    Виртуальный хостинг. Возможности сервера распределяются в равной мере между всеми... 
    Читать полностью

  • Редизайн сайта

    Редизайн сайта – это полное либо частичное обновление дизайна существующего сайта.... 
    Читать полностью

  • Консалтинг, услуги контент-менеджера

    Сопровождение любых интернет ресурсов;- Знание HTML и CSS- Поиск и обновление контента;-... 
    Читать полностью

  • Трафик из соцсетей

    Сравнительно дешевый способ по сравнению с поисковым и контекстным видами раскрутки... 
    Читать полностью

  • Поисковая оптимизация

    Поисковая оптимизация (англ. search engine optimization, SEO) — поднятие позиций сайта в результатах... 
    Читать полностью