Рубрики

Итеративный углубленный поиск (IDS) или Итеративный углубленный поиск в глубину (IDDFS)

Существует два распространенных способа обхода графа: BFS и DFS . Учитывая дерево (или график) огромной высоты и ширины, BFS и DFS не очень эффективны по следующим причинам.

  1. DFS сначала пересекает узлы, проходящие через одно смежное с корнем, затем следующее смежное. Проблема этого подхода заключается в том, что если есть узел, близкий к корню, но не в первых нескольких поддеревьях, исследованных DFS, то DFS достигает этого узла очень поздно. Кроме того, DFS может не найти кратчайший путь к узлу (с точки зрения количества ребер).
  2. BFS идет уровень за уровнем, но требует больше места. Пространство, требуемое DFS, составляет O (d), где d — глубина дерева, но пространство, требуемое BFS, — O (n), где n — количество узлов в дереве. (Почему? Обратите внимание, что последний уровень дерева может иметь около n / 2 узла и второй последний уровень n / 4 узла, и в BFS мы должны иметь каждый уровень один за другим в очереди).

IDDFS сочетает в себе эффективность поиска в глубину и быстрый поиск в ширину (для узлов ближе к корню).

Как работает IDDFS?
IDDFS вызывает DFS для разных глубин, начиная с начального значения. В каждом вызове DFS ограничен выходом за пределы данной глубины. Так что в основном мы делаем DFS в стиле BFS.

Алгоритм:

// Returns true if target is reachable from
// src within max_depth
bool IDDFS(src, target, max_depth)
    for limit from 0 to max_depth
       if DLS(src, target, limit) == true
           return true
    return false   

bool DLS(src, target, limit)
    if (src == target)
        return true;

    // If reached the maximum depth, 
    // stop recursing.
    if (limit return false;   

    foreach adjacent i of src
        if DLS(i, target, limit?1)             
            return true

    return false

Важно отметить, что мы посещаем узлы верхнего уровня несколько раз. Последний (или максимальная глубина) уровень посещается один раз, второй последний уровень посещается дважды, и так далее. Это может показаться дорогим, но оказывается не так дорого, поскольку в дереве большинство узлов находятся на нижнем уровне. Так что это не имеет большого значения, если верхние уровни посещаются несколько раз.

Ниже приведена реализация вышеуказанного алгоритма.

C / C ++

// C ++ программа для поиска, если целевой узел доступен из
// источник с заданной максимальной глубиной.
#include<bits/stdc++.h>

using namespace std;

  
// Графовый класс представляет ориентированный граф с использованием смежности
// представление списка.

class Graph

{

    int V;    // Количество вершин

  

    // Указатель на массив, содержащий

    // списки смежности

    list<int> *adj;

  

    // Функция, используемая IDDFS

    bool DLS(int v, int target, int limit);

  

public:

    Graph(int V);   // Конструктор

    void addEdge(int v, int w);

  

    // Обход IDDFS по вершинам, достижимым из v

    bool IDDFS(int v, int target, int max_depth);

};

  

Graph::Graph(int V)

{

    this->V = V;

    adj = new list<int>[V];

}

  

void Graph::addEdge(int v, int w)

{

    adj[v].push_back(w); // Добавить w в список v.

}

  
// Функция для выполнения поиска с ограниченной глубиной
// из данного источника 'src'

bool Graph::DLS(int src, int target, int limit)

{

    if (src == target)

        return true;

  

    // Если достигнута максимальная глубина, остановить повторение.

    if (limit <= 0)

        return false;

  

    // Повторение для всех вершин, смежных с исходной вершиной

    for (auto i = adj[src].begin(); i != adj[src].end(); ++i)

       if (DLS(*i, target, limit-1) == true)

          return true;

  

     return false;

}

  
// IDDFS для поиска, если цель достижима из v.
// Использует рекурсивный DFSUtil ().

bool Graph::IDDFS(int src, int target, int max_depth)

{

    // Повторный поиск по глубине до

    // максимальная глубина

    for (int i = 0; i <= max_depth; i++)

       if (DLS(src, target, i) == true)

          return true;

  

    return false;

}

  
// Код драйвера

int main()

{

    // Давайте создадим Направленный граф с 7 узлами

    Graph g(7);

    g.addEdge(0, 1);

    g.addEdge(0, 2);

    g.addEdge(1, 3);

    g.addEdge(1, 4);

    g.addEdge(2, 5);

    g.addEdge(2, 6);

  

    int target = 6, maxDepth = 3, src = 0;

    if (g.IDDFS(src, target, maxDepth) == true)

        cout << "Target is reachable from source "

                "within max depth";

    else

        cout << "Target is NOT reachable from source "

                "within max depth";

    return 0;

}

питон

# Программа Python для печати обхода DFS из заданного
# данный график

from collections import defaultdict

  
# Этот класс представляет ориентированный граф с использованием смежности
# представление списка

class Graph:

  

    def __init__(self,vertices):

  

        # Количество вершин

        self.V = vertices

  

        # словарь по умолчанию для хранения графика

        self.graph = defaultdict(list)

  

    # функция для добавления ребра на график

    def addEdge(self,u,v):

        self.graph[u].append(v)

  

    # Функция для выполнения поиска с ограниченной глубиной

    # из данного источника 'src'

    def DLS(self,src,target,maxDepth):

  

        if src == target : return True

  

        # Если достигнута максимальная глубина, прекратите повторение.

        if maxDepth <= 0 : return False

  

        # Повторить для всех вершин, смежных с этой вершиной

        for i in self.graph[src]:

                if(self.DLS(i,target,maxDepth-1)):

                    return True

        return False

  

    # IDDFS для поиска, если цель достижима из v.

    # Использует рекурсивный DLS ()

    def IDDFS(self,src, target, maxDepth):

  

        # Многократный поиск по глубине до

        # максимальная глубина

        for i in range(maxDepth):

            if (self.DLS(src, target, i)):

                return True

        return False

  
# Создайте график, приведенный на диаграмме выше

g = Graph (7);

g.addEdge(0, 1)

g.addEdge(0, 2)

g.addEdge(1, 3)

g.addEdge(1, 4)

g.addEdge(2, 5)

g.addEdge(2, 6)

  

target = 6; maxDepth = 3; src = 0

  

if g.IDDFS(src, target, maxDepth) == True:

    print ("Target is reachable from source " +

        "within max depth")

else :

    print ("Target is NOT reachable from source " +

        "within max depth")

  
# Этот код предоставлен Neelam Pandey


Выход :

Target is reachable from source within max depth

Иллюстрация:
Там может быть два случая
а) Когда у графа нет цикла: этот случай прост. Мы можем DFS несколько раз с различными ограничениями по высоте.

б) Когда на графике есть циклы. Это интересно, поскольку в IDDFS отсутствует флаг посещения.

Сложность времени: Предположим, что у нас есть дерево, имеющее коэффициент ветвления 'b' (количество дочерних элементов каждого узла) и его глубину 'd', то есть существует b d узлов.

При итеративном углубленном поиске узлы на нижнем уровне расширяются один раз, узлы на нижнем уровне — дважды, и так далее, вплоть до корня дерева поиска, которое расширяется d + 1 раз. Таким образом, общее число расширений в итеративном углублении поиска

 (d)b + (d-1)b2 + .... + 3bd-2 + 2bd-1 + bd

That is,
   Summation[(d + 1 - i) bi], from i = 0 to i = d
Which is same as O(bd)

Оценив вышеприведенное выражение, мы обнаружим, что асимптотически IDDFS занимает то же время, что и DFS и BFS, но оно действительно медленнее обоих, поскольку имеет более высокий постоянный коэффициент в выражении сложности времени.

Рекомендуемые посты:

Итеративный углубленный поиск (IDS) или Итеративный углубленный поиск в глубину (IDDFS)

0.00 (0%) 0 votes