如何计算BFS算法中的移动？ （在迷宫中的最短路径）

Question

所以我尝试实现一个BFS算法，并真正理解它是如何工作的（创建某种“我的版本”，从头开始，只看图形和一些伪代码），这就是我结束了了：

#include<iostream> 
#include<string> 
#include<fstream> 
#include<queue> 

using namespace std; 



    void main(int argc, char *argv[]) 
    { 
     // Deklaracja uchwytu do pliku (tylko do odczytu pliku) 
     ifstream plik(argv[1]); 
     // Tablica stringow - przechowujaca wartosci pol 12x12 
     string labirynt[12]; 
     pair <int, int> start; 
     pair <int, int> koniec; 
     // Wektor par - działa jak tablica, przechowuje pary współrzędnych pól 
     queue <pair<int, int>> kolejka; 
     // Tablica odwiedzin - sprawdza czy pole zostalo odwiedzone, 0 jesli nie, 1 jesli tak 
     bool odwiedzone[12][12] = { 0 }; 
     // Zmienna pomocnicza - bo getline sluzy do umieszczania danych w stringu, nie w tablicy znakow 
     int i = 0; 
     // Pętla wczytująca tekst z pliku do tablicy labirynt 
     while (getline(plik, labirynt[i])) 
     { 
      i++; 
     } 

     // Wyszukanie początku i końca w labiryncie (A i B) 
     for (int i = 0; i < 12; i++) 
     { 
      for (int j = 0; j < 12; j++) 
      { 
       if (labirynt[i][j] == 'A') 
       { 
        start.first = i; 
        start.second = j; 
       } 
       if (labirynt[i][j] == 'B') 
       { 
        koniec.first = i; 
        koniec.second = j; 
       } 
      } 

     } 


     // Ustawiamy pole startowe jako odwiedzone - żadne pole nie może być odwiedzone więcej niż 1 raz 
     odwiedzone[start.first][start.second] = true; 



     // Wiersz i kolumna bieżącego wierzchołka 
     int w, k; 




     kolejka.push(start); 

     // Dopóki kolejka nie jest pusta 
     while (!kolejka.empty()) 
     { 
      // Pobieramy z kolejki wiersz i kolumnę bieżącego wierzchołka 
      w = kolejka.front().first; 
      k = kolejka.front().second; 
      // Usuwamy parę z kolejki 
      kolejka.pop(); 


      // Sprawdzamy czy dotarliśmy do wyjścia 
      if (w == koniec.first && k == koniec.second) 
       break; 

      // Przeglądamy sąsiadów bieżącego wierzchołka 

      for (i = -1; i <= 1; i++) 
      for (int j = -1; j <= 1; j++) 
      { 

       if ((i != j) && (!i || !j)) 
       if (labirynt[w + i][k + j] == ' ' && !odwiedzone[w + i][k + j]) 
       { 
        odwiedzone[w + i][k + j] = true; 
        pair <int, int> para; 
        para.first = w + i; 
        para.second = k + j; 
        kolejka.push(para); 
        cout << kolejka.front().first << endl; 
        cout << kolejka.front().second << endl; 
       } 
      } 



     } 
    system("PAUSE"); 
    } 

这里的例子迷宫我使用（从程序文件读取掉落在.EXE）

xxxxxxxxxxxx 
xxA xxxxxxx 
xx x xxxxxx 
x x xxxxxx 
xx x xxxx 
xx xxx xxxxx 
x xxxxxxxx 
x x xxxxxxx 
x xxx xxxxxx 
x xxxxxxx 
xxx  Bxxx 
xxxxxxxxxxxx 

它的工作原理（显示每个字段的坐标，它通过一个迷宫并发现B），但我不知道如何计算需要通过最短路径的动作。

Answer 1

而不是使用odwiedzone[w + i][k + j] = true;检查坐标之前已经加强，使用类似odwiedzone[w + i][k + j] = now + 1步的数量来算，从开始到那个位置：

// first, declare all odwiedzone[][]=-1 
... 

odwiedzone[start.first][start.second] = 0; 
// first position needs 0 step 
... 
      for (i = -1; i <= 1; i++) 
      for (int j = -1; j <= 1; j++) 
      { 

       if ((i != j) && (!i || !j)) 
       if (labirynt[w + i][k + j] == ' ' && odwiedzone[w + i][k + j]==-1) 
       { 
        odwiedzone[w + i][k + j] = odwiedzone[w][k]+1; 
        //next position = now position + 1 

        pair <int, int> para; 
        para.first = w + i; 
        para.second = k + j; 
        kolejka.push(para); 
        cout << kolejka.front().first << endl; 
        cout << kolejka.front().second << endl; 
       } 
      } 

Answer 2

我看你想要什么2种方式实现的：

1. 使用一个单独的队列来存储每个单元的关联距离，例如开始将有0，每个开始的邻居将有1个等。每次添加一个新邻居时，他的值都是距离当前单元格+ 1的距离。第二个队列中的目标值将为您提供路径长度。

2. 在队列中添加邻居时，记录他的父节点。因此，当您找到源代码时，您可以重建路径并计算步骤数。