使用BFS找到最短路徑

正如tittle所說，我試圖找到一個單位移動到最近控制點的最短路徑（就好像它是一個寶藏或某物）。我試圖用BFS來找到這條路，但是它並沒有給出最短的路。對於爲例：使用BFS找到最短路徑

如果我們有這樣的事情（其中X是起始位置和K是一個控制點）

· · · · · · · · · · · · 
· · · · · · · · · · · · 
· · · · · · · · · · · · 
· · · X · · · · · · · · 
· · · · · · · · · · · · 
· · · · · · · · · · · · 
· · · · · · · · · · · · 
· · · · · · · · · · · · 
· · · · · K · · · · · · 
· · · · · · · · · · · · 
· · · · · · · · · · · · 
· · · · · · · · · · · ·

我的代碼給出了這樣的路徑：

· · · · · · · · · · · · 
· · · · · · · · · · · · 
· · - - - · · · · · · · 
· · | X | · · · · · · · 
· · | | - · · · · · · · 
· · | · · · · · · · · · 
· · | · · · · · · · · · 
· · · | · · · · · · · · 
· · · | - K · · · · · · 
· · · · · · · · · · · · 
· · · · · · · · · · · · 
· · · · · · · · · · · ·

但我不看不出爲什麼它給了我額外的動作。有人可以知道我做錯了什麼？

typedef pair<int,int> Coord; 
typedef vector< vector<bool> > VIS; 
typedef vector<vector< Coord> > Prev; 
const int X[8] = { 1, 1, 0, -1, -1, -1, 0, 1 }; 
const int Y[8] = { 0, 1, 1, 1, 0, -1, -1, -1 }; 


list<Coord> BFS2(int x, int y, VIS& visited, Prev& p) { 
    queue<Coord> Q; 

    Coord in; 
    in.first = x; in.second = y; 

    Q.push(in); 
    bool found = false; 
    Coord actual; 
    while(not Q.empty() and not found){ 
     actual = Q.front();   
     Q.pop(); 
     int post = who_post(actual.first, actual.second); //It tells if we're in a control point or not(0 == if we are not in the C.point) 
     if(post != 0){ 
      found = true;     
     } 
     else { 
      visited[actual.first][actual.second]=true; 
      for(int i = 0; i < 8; i++){ 
        int nx = X[i] + actual.first;  
        int ny = Y[i] + actual.second; 
       //The maze is 60x60, but the borders are all mountains, so we can't access there 
       if(nx>=1 and nx<59 and ny>=1 and ny<59 and not visited[nx][ny]){ 
        Coord next; 
        next.first = nx; next.second = ny; 
        Q.push(next); 
        p[nx][ny] = actual; 
       } 
      } 
     } 
    } 
    list<Coord> res; 

    while(actual != in){ 
     res.push_back(actual); 
     actual = p[actual.first][actual.second]; 
    } 
    res.reverse(); 
    return res; 
}

來源

2014-11-22 aura

我認爲這與你如何計算我們以前的矩陣有關。具體如下代碼

if(nx>=1 and nx<59 and ny>=1 and ny<59 and not visited[nx][ny]){ 
    ... 
    p[nx][ny] = actual; 
}

每當你遇到一個不請自來的節點與您正在尋求節點更新之前的矩陣。但是，請考慮一下開始時會發生什麼。您將排隊開始的每個點，並將每個節點的前一個矩陣標記爲起點。現在您將探索其他節點。它們的每一個鄰居都將被排隊，除了起點之外，因爲他們都沒有被訪問過。前一個矩陣中的一些條目將被覆蓋。這就是爲什麼你的道路沒有意義。

來源

2014-11-23 03:29:35 Jfietz

使用BFS找到最短路徑

回答

相關問題