学习资料:代码随想录
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++ 函数 | 菜鸟教程
给陪伴我的网易云歌单也做个笔记:网易云音乐
音乐确实承载着太多回忆,可能将来的某一天,听到热河的前奏响起,闭上眼就会回到冬天坐在电脑前的那个晚上