笔记：代码随想录算法训练营day67:Floyd 算法精讲、A * 算法精讲 （A star算法） 严重超时完结，不过，撒花

学习资料：代码随想录

Floyd 算法精讲

卡码网：97. 小明逛公园

首先明确floyd算法解决的是多源最短路径问题，对边的权的正负值没有要求，而且是动态规划的思想

五部曲：

定义：grid[i][j][k]表示从i出发到j经过[1...k]中某一个节点的最短距离

递推：1、节点i 到 节点j 的最短路径经过节点k，grid[i][j][k] = grid[i][k][k - 1] + grid[k][j][k - 1]（i到k不经过k+k到j不经过k）

2、节点i 到 节点j 的最短路径不经过节点k，grid[i][j][k] = 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])

为什么最后一位是k-1呢，其实模拟一遍是最清楚的，个人浅显地认为，简要来说，还是动态规划中递推的思想：

假设你有节点 1~5，现在计算 grid[1][4][3]

• 意思是：你正在计算 从 1 到 4 的最短路径，中间节点只能是 编号 ≤ 3 的点

所以这里你根本还不能用点 4 和点 5，它们 大于 k=3，不在当前阶段允许的中间节点集合内。

用点4和点5是递推到后面的事

初始化：i到j不经过节点的时候，即grid[i][j][0]，可以通过输入就初始化了，其他值要给一个比10^4大的值，因为递推的过程是取小值；也不能太大，后面还要加，怕溢出。

遍历顺序：根据递推公式，得到grid[i][j][k]需要用到grid[i][k][k - 1]，grid[k][j][k - 1] ，grid[i][j][k - 1]，故吧k放在最外层

打印：略

//五部曲
//定义
//递推公式
//初始化
//遍历顺序
//打印
#include <iostream>
#include <vector>
using namespace std;int main(){int n,m,u,v,w,q,start,end;cin>>n>>m;vector<vector<vector<int>>> roads(n+1,vector<vector<int>>(n+1,vector<int>(n+1,10005)));for(int i=0;i<m;i++){cin>>u>>v>>w;roads[u][v][0]=w;     //初始化roads[v][u][0]=w;}for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){roads[i][j][k]=min(roads[i][j][k-1],roads[i][k][k-1]+roads[k][j][k-1]);  //不经过k点和经过k点}}}cin>>q;while(q--){cin>>start>>end;if(roads[start][end][n]==10005) cout<<-1<<endl;else{cout<<roads[start][end][n]<<endl;}}
}

可以把空间复杂度压缩到O(n^2)

//五部曲
//定义
//递推公式
//初始化
//遍历顺序
//打印
#include <iostream>
#include <vector>
using namespace std;int main(){int n,m,u,v,w,q,start,end;cin>>n>>m;vector<vector<int>> roads(n+1,vector<int>(n+1,10005));for(int i=0;i<m;i++){cin>>u>>v>>w;roads[u][v]=w;     //初始化roads[v][u]=w;}for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){roads[i][j]=min(roads[i][j],roads[i][k]+roads[k][j]);  //不经过k点和经过k点}}}cin>>q;while(q--){cin>>start>>end;if(roads[start][end]==10005) cout<<-1<<endl;else{cout<<roads[start][end]<<endl;}}
}

A * 算法精讲 （A star算法）

卡码网：126. 骑士的攻击

该说不说这道题的题目描述晃到我的，上来说马走日，象飞田，结果题目是求骑士的最少步数。

A*算法其实还是广度优先搜索，不过加上了启发式函数，启发式函数算的是从起点到终点并经过当前点要走的距离。

#include <iostream>
#include <queue>
#include <string.h>
using namespace std;int moves[1001][1001];
int dir[8][2]={2,1,1,2,-1,2,-2,1,-2,-1,-1,-2,1,-2,2,-1};
int b1,b2;struct knight{int x,y;             // 当前坐标int g,h,f;           // g=走过的代价，h=预估代价（启发式函数），f=g+hbool operator < (const knight& k) const{    //这是一个成员函数，重载了 < 运算符。//operator <：表示重载“小于”运算符//(const Knight &k)：要和另一个 Knight 对象 k 进行比较//const：表示这个函数不会修改当前对象的成员变量//返回值是 bool，表示当前对象是否 小于 参数 kreturn k.f<f;      // 小顶堆，f 越小优先级越高}
};priority_queue<knight> que;
int Heuristic(const knight& k){return (k.x-b1)*(k.x-b1)+(k.y-b2)*(k.y-b2);       //启发函数采用的是 欧几里得距离的平方（不开根号），因为这样避免了浮点计算，提高精度与效率
}void astar(const knight& k){        //输入起点 k，然后开始扩展knight cur,next; que.push(k);                    // 起点进队while(!que.empty()){cur = que.top(); que.pop(); //每次从堆里取出 f 最小的节点if(cur.x==b1&&cur.y==b2){   //终点判断break;}for(int i=0;i<8;i++){       //尝试扩展8个方向next.x = cur.x+dir[i][0];next.y = cur.y+dir[i][1];if(next.x<1||next.y>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;                                  // 因为一步是 √5，不开根next.h=Heuristic(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=Heuristic(start);start.f=start.g+start.h;astar(start);while(!que.empty()){                //多组输入，清空 moves 数组que.pop();}cout<<moves[b1][b2]<<endl;}return 0;
}

对于这个重载语法，作用是为了让 priority_queue 成为小顶堆 —— 也就是 f 越小，优先级越高。priority_queue 默认是 大顶堆，它把“最大的”元素放在堆顶。所以你必须让“小的 f 看起来是“更大”的”，于是写成：return k.f < f;

priority_queue 会把 “operator < 为 true 的对象” 排在后面。

还可用lambda：

#include <iostream>
#include <queue>
#include <string.h>
using namespace std;int moves[1001][1001];
int dir[8][2]={2,1,1,2,-1,2,-2,1,-2,-1,-1,-2,1,-2,2,-1};
int b1,b2;struct knight{int x,y;             // 当前坐标int g,h,f;           // g=走过的代价，h=预估代价（启发式函数），f=g+h// bool operator < (const knight& k) const{    //这是一个成员函数，重载了 < 运算符。//                                             //operator <：表示重载“小于”运算符//                                             //(const Knight &k)：要和另一个 Knight 对象 k 进行比较//                                             //const：表示这个函数不会修改当前对象的成员变量//                                             //返回值是 bool，表示当前对象是否 小于 参数 k//     return k.f<f;      // 小顶堆，f 越小优先级越高// }
};//priority_queue<knight> que;
int Heuristic(const knight& k){return (k.x-b1)*(k.x-b1)+(k.y-b2)*(k.y-b2);       //启发函数采用的是 欧几里得距离的平方（不开根号），因为这样避免了浮点计算，提高精度与效率
}void astar(const knight& k){        //输入起点 k，然后开始扩展auto cmp = [](const knight& a, const knight& b) {return a.f > b.f;  // f 小的优先};priority_queue<knight, vector<knight>, decltype(cmp)> que(cmp);knight cur,next; que.push(k);                    // 起点进队while(!que.empty()){cur = que.top(); que.pop(); //每次从堆里取出 f 最小的节点if(cur.x==b1&&cur.y==b2){   //终点判断break;}for(int i=0;i<8;i++){       //尝试扩展8个方向next.x = cur.x+dir[i][0];next.y = cur.y+dir[i][1];if(next.x<1||next.y>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;                                  // 因为一步是 √5，不开根next.h=Heuristic(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=Heuristic(start);start.f=start.g+start.h;astar(start);// while(!que.empty()){                //多组输入，清空 moves 数组//     que.pop();// }cout<<moves[b1][b2]<<endl;}return 0;
}

A * 算法并不能保证一定是最短路，虽然本题求出来是最短路

memset函数：C 库函数 – memset() | 菜鸟教程

重载运算符：C++ 重载运算符和重载函数 | 菜鸟教程

lambda：C++ 函数 | 菜鸟教程

给陪伴我的网易云歌单也做个笔记：网易云音乐

音乐确实承载着太多回忆，可能将来的某一天，听到热河的前奏响起，闭上眼就会回到冬天坐在电脑前的那个晚上