day62 Floyd 算法 A * 算法

Floyd 算法

本題是經典的多源最短路問題.

Floyd 算法對邊的權值正負沒有要求，都可以處理。

Floyd算法核心思想是動態規劃。

例如我們再求節點1 到節點9 的最短距離，用二維數組來表示即：grid[1][9]，如果最短距離是10 ，那就是 grid[1][9] = 10。

那節點1 到節點9 的最短距離是不是可以由節點1 到節點5的最短距離 + 節點5到節點9的最短距離組成呢？

即 grid[1][9] = grid[1][5] + grid[5][9]

節點1 到節點5的最短距離是不是可以有節點1 到節點3的最短距離 + 節點3 到節點5 的最短距離組成呢？

即 grid[1][5] = grid[1][3] + grid[3][5]

以此類推，節點1 到節點3的最短距離可以由更小的區間組成。

那么這樣我們是不是就找到了，子問題推導求出整體最優方案的遞歸關系呢。

這里我們用 grid數組來存圖，那就把dp數組命名為 grid。

grid[i][j][k] = m，表示?節點i 到節點j 以[1...k] 集合中的一個節點為中間節點的最短距離為m。

?這里的k不能單獨指某個節點，k 一定要表示一個集合，即[1...k] ，表示節點1 到節點k 一共k個節點的集合。

我們分兩種情況：

節點i 到節點j 的最短路徑經過節點k
節點i 到節點j 的最短路徑不經過節點k

對于第一種情況，grid[i][j][k] = grid[i][k][k - 1] + grid[k][j][k - 1]

節點i 到節點k 的最短距離是不經過節點k，中間節點集合為[1...k-1]，所以表示為grid[i][k][k - 1]

節點k 到節點j 的最短距離也是不經過節點k，中間節點集合為[1...k-1]，所以表示為?grid[k][j][k - 1]

第二種情況，grid[i][j][k] = grid[i][j][k - 1]

如果節點i 到節點j的最短距離不經過節點k，那么中間節點集合[1...k-1]，表示為?grid[i][j][k - 1]

因為我們是求最短路，對于這兩種情況自然是取最小值。

即：?grid[i][j][k] = min(grid[i][k][k - 1] + grid[k][j][k - 1]， grid[i][j][k - 1])

grid[i][j][k] = m，表示節點i 到節點j 以[1...k] 集合為中間節點的最短距離為m。

剛開始初始化k 是不確定的。

例如題目中只是輸入邊（節點2 -> 節點6，權值為3），那么grid[2][6][k] = 3，k需要填什么呢？

把k 填成1，那如何上來就知道節點2 經過節點1 到達節點6的最短距離是多少呢。

所以只能把k 賦值為 0，本題節點0 是無意義的，節點是從1 到 n。

這樣我們在下一輪計算的時候，就可以根據 grid[i][j][0] 來計算 grid[i][j][1]，此時的 grid[i][j][1] 就是節點i 經過節點1 到達節點j 的最小距離了。

遍歷的順序是從底向上一層一層去遍歷。

所以遍歷k 的for循環一定是在最外面，這樣才能一層一層去遍歷。

kama97. 小明逛公園

題目描述
小明喜歡去公園散步，公園內布置了許多的景點，相互之間通過小路連接，小明希望在觀看景點的同時，能夠節省體力，走最短的路徑。?
給定一個公園景點圖，圖中有 N 個景點（編號為 1 到 N），以及 M 條雙向道路連接著這些景點。每條道路上行走的距離都是已知的。
小明有 Q 個觀景計劃，每個計劃都有一個起點 start 和一個終點 end，表示他想從景點 start 前往景點 end。由于小明希望節省體力，他想知道每個觀景計劃中從起點到終點的最短路徑長度。請你幫助小明計算出每個觀景計劃的最短路徑長度。
輸入描述
第一行包含兩個整數 N, M, 分別表示景點的數量和道路的數量。?
接下來的 M 行，每行包含三個整數 u, v, w，表示景點 u 和景點 v 之間有一條長度為 w 的雙向道路。?
接下里的一行包含一個整數 Q，表示觀景計劃的數量。?
接下來的 Q 行，每行包含兩個整數 start, end，表示一個觀景計劃的起點和終點。
輸出描述
對于每個觀景計劃，輸出一行表示從起點到終點的最短路徑長度。如果兩個景點之間不存在路徑，則輸出 -1。
輸入示例
7 3
2 3 4
3 6 6
4 7 8
2
2 3
3 4
輸出示例
4
-1
提示信息
從 2 到 3 的路徑長度為 4，3 到 4 之間并沒有道路。
1 <= N, M, Q <= 1000.
1 <= w <= 10000.

#include <bits/stdc++.h>
using namespace std;
int main()
{int n,m,p1,p2,val;cin>>n>>m;vector<vector<vector<int>>> grid(n+1,vector<vector<int>>(n+1,vector<int>(n+1,10001)));while(m--){cin>>p1>>p2>>val;grid[p1][p2][0] = val;//可以想象為一個三維的空間，我們只初始化空間的底層，后續遍歷的時候從底層一層一層往上遍歷。grid[p2][p1][0] = val;//雙向圖！！！}for(int k = 1;k<=n;k++)//注意這里先遍歷k{for(int i = 1;i<=n;i++){for(int j = 1;j<=n;j++){grid[i][j][k] = min(grid[i][j][k-1],grid[i][k][k-1]+grid[k][j][k-1]);}}}int q,start,end;cin>>q;while(q--){cin>>start>>end;if(grid[start][end][n]==10001)cout<<"-1"<<endl;else cout<<grid[start][end][n]<<endl;}
}

A * 算法

Astar 是一種廣搜的改良版。有的是 Astar是 dijkstra 的改良版。

其實只是場景不同而已我們在搜索最短路的時候，如果是無權圖（邊的權值都是1）那就用廣搜，代碼簡潔，時間效率和 dijkstra 差不多（具體要取決于圖的稠密）

如果是有權圖（邊有不同的權值），優先考慮 dijkstra。

而 Astar 關鍵在于啟發式函數，也就是影響廣搜或者 dijkstra 從容器（隊列）里取元素的優先順序。

大家可以發現?BFS 是沒有目的性的一圈一圈去搜索，而 A * 是有方向性的去搜索。

?啟發式函數要影響的就是隊列里元素的排序！

對隊列里節點進行排序，就需要給每一個節點權值，如何計算權值呢？

每個節點的權值為F，給出公式為：F = G + H

G：起點達到目前遍歷節點的距離

H：目前遍歷的節點到達終點的距離

起點達到目前遍歷節點的距離 + 目前遍歷的節點到達終點的距離就是起點到達終點的距離。

題的圖是無權網格狀，在計算兩點距離通常有如下三種計算方式：

曼哈頓距離，計算方式： d = abs(x1-x2)+abs(y1-y2)
歐氏距離（歐拉距離），計算方式：d = sqrt( (x1-x2)^2 + (y1-y2)^2 )
切比雪夫距離，計算方式：d = max(abs(x1 - x2), abs(y1 - y2))

x1, x2 為起點坐標，y1, y2 為終點坐標，abs 為求絕對值，sqrt 為求開根號，

選擇哪一種距離計算方式也會導致 A * 算法的結果不同。

本題，采用歐拉距離才能最大程度體現點與點之間的距離。

相對了普通BFS，A * 算法只從隊列里取出距離終點最近的節點。

那么問題來了，A * 在一次路徑搜索中，大量不需要訪問的節點都在隊列里，會造成空間的過度消耗。

IDA * 算法對這一空間增長問題進行了優化，關于 IDA * 算法，本篇不再做講解，感興趣的錄友可以自行找資料學習。

另外還有一種場景是 A * 解決不了的。

如果題目中，給出多個可能的目標，然后在這多個目標中選擇最近的目標，這種 A * 就不擅長了， A * 只擅長給出明確的目標然后找到最短路徑。

如果是多個目標找最近目標（特別是潛在目標數量很多的時候），可以考慮 Dijkstra ，BFS 或者 Floyd。

127. 騎士的攻擊

題目描述
在象棋中，馬和象的移動規則分別是“馬走日”和“象走田”。現給定騎士的起始坐標和目標坐標，要求根據騎士的移動規則，計算從起點到達目標點所需的最短步數。
棋盤大小 1000 x 1000（棋盤的 x 和 y 坐標均在 [1, 1000] 區間內，包含邊界）
輸入描述
第一行包含一個整數 n，表示測試用例的數量，1 <= n <= 100。
接下來的 n 行，每行包含四個整數 a1, a2, b1, b2，分別表示騎士的起始位置 (a1, a2) 和目標位置 (b1, b2)。
輸出描述
輸出共 n 行，每行輸出一個整數，表示騎士從起點到目標點的最短路徑長度。
輸入示例
6
5 2 5 4
1 1 2 2
1 1 8 8
1 1 8 7
2 1 3 3
4 6 4 6
輸出示例
2
4
6
5
1
0
提示信息
騎士移動規則如圖，紅色是起始位置，黃色是騎士可以走的地方。

#include <bits/stdc++.h>
using namespace std;
int dir[8][2] = {-2,-1,-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2};
int moves[1001][1001];
int b1, b2;
struct Knight
{int x,y;int f,g,h; //f = g + h;  g為從起點到當前遍歷節點的消耗，h為當前遍歷節點到終點的“預計“消耗bool operator < (const Knight& k) const{return k.f < f;//后續的priority_queue會根據這個來找出f最小的。} 
};
priority_queue<Knight> que;
int calDistance(const Knight& k)
{return (k.x-b1)*(k.x-b1)+(k.y-b2)*(k.y-b2);
}
void astar(const Knight& k)
{Knight cur,next;que.push(k);while(!que.empty()){cur = que.top();que.pop();if(cur.x == b1 && cur.y == b2)break;for(int i = 0;i<8;i++){next.x = cur.x + dir[i][0];next.y = cur.y + dir[i][1];if(next.x<1||next.x>1000||next.y<1||next.y>1000)continue;if(!moves[next.x][next.y]){moves[next.x][next.y] = moves[cur.x][cur.y] +1;next.g = cur.g + 5;//馬走日，2*2+1*1.next.h = calDistance(next);next.f = next.g + next.h;que.push(next);}}}
}
int main()
{int n,a1,a2;cin>>n;while(n--){cin>>a1>>a2>>b1>>b2;memset(moves,0,sizeof(moves));Knight start;start.x = a1;start.y = a2;start.g = 0;start.h = calDistance(start);start.f = start.g + start.h;astar(start);while(!que.empty())que.pop();cout<<moves[b1][b2]<<endl;}return 0;
}