Как восстановить пути с помощью BFS - PullRequest
Новая
       19

Как восстановить пути с помощью BFS

0 голосов
/ 08 июля 2020

Я узнал, что поиск в ширину - это алгоритм, который можно использовать для вычисления кратчайшего расстояния между двумя узлами. Я реализовал алгоритм BFS в приведенном ниже коде: 

#define N 4 
#define M 4 

// QItem for current location and distance 
// from source location 
class QItem {
public:
    int row;
    int col;
    int dist;
    QItem(int x, int y, int w)
        : row(x), col(y), dist(w)
    {
    }
};


int minDistance(char grid[N][M])
{
    QItem source(0, 0, 0);

    // To keep track of visited QItems. Marking 
    // blocked cells as visited. 
    bool visited[N][M];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++)
        {
            if (grid[i][j] == '0')
                visited[i][j] = true;
            else
                visited[i][j] = false;

            // Finding source 
            if (grid[i][j] == 's')
            {
                source.row = i;
                source.col = j;
            }
        }
    }

    // applying BFS on matrix cells starting from source 
    queue<QItem> q;
    q.push(source);
    visited[source.row][source.col] = true;
    while (!q.empty()) {
        QItem p = q.front();
        q.pop();

        if (grid[p.row][p.col] == 'd')
            return p.dist;

        if (p.row - 1 >= 0 && visited[p.row - 1][p.col] == false) {
            q.push(QItem(p.row - 1, p.col, p.dist + 1));
            visited[p.row - 1][p.col] = true;
        }

        if (p.row + 1 < N && visited[p.row + 1][p.col] == false) {
            q.push(QItem(p.row + 1, p.col, p.dist + 1));
            visited[p.row + 1][p.col] = true;
        }

        if (p.col - 1 >= 0 && visited[p.row][p.col - 1] == false) {
            q.push(QItem(p.row, p.col - 1, p.dist + 1));
            visited[p.row][p.col - 1] = true;
        }

        if (p.col + 1 < M && visited[p.row][p.col + 1] == false) {
            q.push(QItem(p.row, p.col + 1, p.dist + 1));
            visited[p.row][p.col + 1] = true;
        }
    }
    return -1;
}

int main()
{
    char grid[N][M] = { { '0', '*', '0', 's' },
                        { '*', '0', '*', '*' },
                        { '0', '*', '*', '*' },
                        { 'd', '*', '*', '*' } };

    cout << minDistance(grid);
    return 0;
}

Мой вопрос: существует ли эффективный способ реконструировать путь между двумя узлами без запуска другого алгоритма? Если нет, существует ли другой алгоритм кратчайшего пути, который может восстанавливать пути?

1 Ответ

1 голос
/ 09 июля 2020

Чтобы реконструировать пути с помощью breadth-first search, вы можете сохранить родительский vector, который отслеживает родительский элемент каждого узла. После завершения работы BFS вы можете проследить назад от конечного узла до начала, чтобы построить свой путь.

Вот пример кода, который это иллюстрирует: 

while(!Q.empty){
    int curr = Q.front();
    Q.pop();

    if(curr == destination){break;}

    for(int item : adj[curr]){ // for every element adjacent to curr
        if(!visited[item]){
            visited[item] = true;
            parent[item] = curr; // connects curr to item
            Q.push(item);
        }
    }
}

// trace from the destination back to the start
int tracer = destination;
vector <int> path = {tracer};

while(tracer != start){
    tracer = parent[tracer];
    path.push_back(tracer);
}

// note that this constructs path in reverse order (from end to start)

В вашем случае parent должно быть map <QItem, QItem>, отслеживая каждого QItem's родителя.

...