Универсальная реализация алгоритмов BFS, DFS, дейкстры и A*

 Перевод моей статьи с HackerNoon.

 

Оказывается, что известные алгоритмы BFS, DFS, Дейкстры и А* являются, по сути, вариациями одного и того же алгоритма. Я продемонстрирую это на реальной реализации.

Другими словами, можно реализовать универсальную структуру данных, которая может переключаться между этими алгоритмами, не требуя изменений в своих основных компонентах. Хотя существуют некоторые ограничения, исследование этого подхода представляет интерес.

Весь рабочий код этих алгоритмов можно найти в моем репозитории GitHub здесь. Я рекомендую экспериментировать с кодом во время чтения этой статьи, так как практический опыт лучше, чем просто теоретическое понимание.

Представление графа

Рассмотрим граф с 25 узлами, расположенными в виде сетки 5x5, где мы стремимся найти путь от узла 0 в верхнем левом углу до узла 24 в нижнем правом углу:

 ```
( 0  ) - ( 1  ) - ( 2  ) - ( 3  ) - ( 4  )
  |        |        |        |        |
( 5  ) - ( 6  ) - ( 7  ) - ( 8  ) - ( 9  )
  |        |        |        |        |
( 10 ) - ( 11 ) - ( 12 ) - ( 13 ) - ( 14 )
  |        |        |        |        |
( 15 ) - ( 16 ) - ( 17 ) - ( 18 ) - ( 19 )
  |        |        |        |        |
( 20 ) - ( 21 ) - ( 22 ) - ( 23 ) - ( 24 )
```

Каждый из упомянутых алгоритмов способен достичь этого, но у них есть свои ограничения:

• Оба алгоритма BFS и DFS работают на не взвешенных графах, игнорируя веса ребер. Хотя они могут найти любой путь, они не гарантируют оптимальный путь.
• Оба алгоритма Дейкстры и А* работают на взвешенных графах, но не должны использоваться с графами, содержащими отрицательные веса. А* обычно работает быстрее благодаря своей оптимизации, которая учитывает евклидовы координаты при поиске пути.

В этой статье я не рассматриваю базовые концепции, предполагая, что вы уже знакомы с ними. Если используемая выше терминология кажется вам сложной, вероятно, вам стоит изучить основы. Однако экспериментирование с этими примерами кода все равно может быть увлекательным.

Для учета этих ограничений давайте назначим каждому узлу воображаемые координаты (X, Y):

 ```
(0, 0) - (0, 1) - (0, 2) - (0, 3) - (0, 4)
   |        |        |        |       |
(1, 0) - (1, 1) - (1, 2) - (1, 3) - (1, 4)
   |        |        |        |       |
(2, 0) - (2, 1) - (2, 2) - (2, 3) - (2, 4)
   |        |        |        |       |
(3, 0) - (3, 1) - (3, 2) - (3, 3) - (3, 4)
   |        |        |        |       |
(4, 0) - (4, 1) - (4, 2) - (4, 3) - (4, 4)
```

Наконец, давайте назначим некоторый вес для каждого ребра в графе:

 ```
(0, 0) -1- (0, 1) -1- (0, 2) -1- (0, 3) -2- (0, 4)
   |          |          |          |         |
   2          1          1          2         2
   |          |          |          |         |
(1, 0) -2- (1, 1) -1- (1, 2) -2- (1, 3) -1- (1, 4)
   |          |          |          |         |
   2          1          1          1         1
   |          |          |          |         |
(2, 0) -1- (2, 1) -1- (2, 2) -1- (2, 3) -2- (2, 4)
   |          |          |          |         |
   2          1          1          1         2
   |          |          |          |         |
(3, 0) -2- (3, 1) -2- (3, 2) -1- (3, 3) -2- (3, 4)
   |          |          |          |         |
   2          1          1          2         2
   |          |          |          |         |
(4, 0) -2- (4, 1) -1- (4, 2) -2- (4, 3) -2- (4, 4)
```

На C++ эта структура может быть представлена следующим образом:

 ```C++
class GraphNode
{
public:
    int X;
    int Y;
};

class Graph
{
public:
    vector<vector<pair<int, int>>> Edges;
    vector<GraphNode> Nodes;
};
```

Список ребер в Graph представлен массивом массивов, где индекс соответствует номеру выходного узла для каждого ребра в графе. Затем каждый элемент содержит пару значений:

1. Номер входного узла для каждого ребра в графе.
2. Вес ребра.

Используя эту простую конструкцию, мы можем проходить каждый узел в графе и получать всю необходимую информацию о его соединениях:

```C++
int toNode = graph.Edges[fromNode][neighbourIndex].first;
int weight = graph.Edges[fromNode][neighbourIndex].second;
```

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

• Генерация списка узлов
• Создание пользовательских соединений

В качестве альтернативы, также возможно лениво генерировать все соединения и веса в этом графе с использованием еще меньшего количества кода. Однако этот подход может не дать полного понимания реальных различий в том, как алгоритмы проходят граф.

Универсальный алгоритм

В основе универсального алгоритма поиска пути лежит универсальная структура данных, которую мы будем называть "Queue" для целей этого проекта. Однако это не классическая структура данных FIFO (First-In-First-Out). В алгоритмах поиска пути важен порядок обхода узлов, который как правило задается структурой данных. В нашем случае, это абстрактный тип данных, который позволяет нам реализовать очередь узлов (отсюда "Queue") во время обхода, сохраняя возможность изменять механизм очереди в зависимости от используемого алгоритма. Интерфейс для этой "Queue" прост:

 ```C++
class pathFindingBase
{
public:
  virtual void insert(int node) = 0;
  virtual int getFirst() = 0;
  virtual bool isEmpty() = 0;
};
```

Прежде чем углубиться в детали Queue, давайте рассмотрим сам алгоритм обхода.

По сути, он очень похож на типичный алгоритм A* или Дейкстры. Сначала нам нужно инициализировать набор коллекций, которые позволяют:

• Поддерживать список узлов, которые еще не были обработаны (белого цвета), находятся в процессе обработки (серого цвета) и уже обработаны/посещены (черного цвета).
• Отслеживать текущее расстояние кратчайшего пути от начального узла до любого другого узла.
• Осуществлять текущую очередь узлов для обработки.
• Отслеживать путь.

```C++
unordered_map<int, string> nodeColour;
unordered_map<int, int> distance;
pathFindingBase* queue;
unordered_map<int, int> path;
```

Ниже приведен код, представляющий наш универсальный алгоритм:

```C++

void initCollections()
{
    nodeColour.clear();
    distance.clear();
    path.clear();

    for (auto node : graph.Nodes)
    {
        nodeColour[node] = "white";
        distance[node] = INT_MAX;
    }
    distance[startNode] = 0;
}

bool universalPathFindingAlgo(int startNode, int targetNode)
{
    initCollections();

    queue->insert(startNode);

    while (!queue->isEmpty())
    {
        int currentNode = queue->getFirst();
        nodeColour[currentNode] = "grey";

        if (currentNode == targetNode)
        {
            return true;
        }

        for (auto neighbour : graph.Edges[currentNode])
        {
            int neighbourNode = neighbour.first;
            int weight = neighbour.second;

            if (nodeColour[neighbourNode] == "white" ||
                distance[currentNode] + weight < distance[neighbourNode])
            {
                distance[neighbourNode] = distance[currentNode] + weight;
                path[neighbourNode] = currentNode;
                queue->insert(neighbourNode);
            }
        }
        nodeColour[currentNode] = "black";
    }

    return false;
} 

```

Алгоритмы BFS, DFS, Дейкстры и A* различаются только реализацией очереди и инициализацией данных.

Алгоритм BFS

В реализации алгоритма BFS проста важно следить за порядком FIFO:

```C++

class BFSQueue : public pathFindingBase
{
private:
    queue<int> q;

public:
    void insert(int node) override
    {
        q.push(node);
    }

    int getFirst() override
    {
        int front = q.front();
        q.pop();
        return front;
    }

    bool isEmpty() override
    {
        return q.empty();
    }
};

```

Алгоритм DFS

Реализация алгоритма DFS требует уже не FIFO, но LIFO (Last-In-First-Out) очередь:

```C++

class DFSQueue : public pathFindingBase
{
private:
    stack<int> s;

public:
    void insert(int node) override
    {
        s.push(node);
    }

    int getFirst() override
    {
        int top = s.top();
        s.pop();
        return top;
    }

    bool isEmpty() override
    {
        return s.empty();
    }
};

```

Алгоритм Дейкстры

Реализация алгоритма Дейкстры требует уже использования приоритетной очереди, так как по определению алгоритм Дейкстры отбирает локальный оптимум (то есть, жадно находит самое "дешевое" ребро из каждого конкретного узла). Приоритет определяется текущим расстоянием узла от начального узла:

```C++

class DijkstraQueue : public pathFindingBase
{
private:
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

public:
    void insert(int node) override
    {
        pq.push({distance[node], node});
    }

    int getFirst() override
    {
        int node = pq.top().second;
        pq.pop();
        return node;
    }

    bool isEmpty() override
    {
        return pq.empty();
    }
};

```

Алгоритм A*

Реализация алгоритма A* также требует использования приоритетной очереди, но приоритет определяется евклидовым расстоянием между текущим узлом и целевым узлом:

```C++

class AStarQueue : public pathFindingBase
{
private:
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

public:
    void insert(int node) override
    {
        int heuristic = abs(graph.Nodes[node].X - graph.Nodes[targetNode].X) +
                        abs(graph.Nodes[node].Y - graph.Nodes[targetNode].Y);
        pq.push({distance[node] + heuristic, node});
    }

    int getFirst() override
    {
        int node = pq.top().second;
        pq.pop();
        return node;
    }

    bool isEmpty() override
    {
        return pq.empty();
    }
};

```

Таким образом, последовательно усложняя нашу абстрактную структуру данных мы пришли от простейшего BFS к оптимальному A-Star, при этом даже не меняя реализацию самого алгоритма поиска, а только лишь "подкручивая" нашу структуру данных.

Заключение

Итак, на этой ноте мы завершили реализацию универсального алгоритма. Очевидно, что этот алгоритм можно улучшать и оптимизировать, но его основная идея заключается в том, чтобы продемонстрировать, что известные алгоритмы, такие как BFS, DFS, Дейкстры и A*, по сути, являются вариациями одного и того же основного алгоритма.